敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 int length; }SqBiTree: 3)不足：空间的利用率不高 如：若深度为5且仅含有5个结点的二叉树，必须要占用2425-1空间。 2、二叉树的链式存储结构 parent 1)引入辅助空间表示结点间的相对关系 双亲(1)一一孩子(2)（如右图） data Ichild data rchild parent Ichild data rchild 二叉链表 三叉链表 lchild rchild 若需要找指定结点的双亲，则用三叉链表可在O(1)时间内获得某结点的双亲；而用二 叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode ElemType data: struct BiTNode *lchild,*rchild; /体左右孩子指针*/ }BiTNode,*BiTree; 3)二叉链表的链域 若有n个结点，则共有2n个链域：其中n-1不为空，指向孩子。 4) 二叉树（链式存储）的创建 输入序列与二叉树的映射关系 (1)完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按 自上而下、自左至右进行输入。 (2)二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍 历进行输入。 (3)二叉树的两种遍历序列：先序+中序，后序+中序 6.3树和森林 1、树的存储结构 1)双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX TREE SIZE 100 体树的最大结点数 typedef struct PTNode ElemType data, int parent; PTNode: typedef struct PTNode nodes[MAX TREE_SIZE]; int n; 体结点数 */ PTree; 2)孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第5页程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 5 页 第六章 树和二叉树 基本概念、遍历算法及其应用 int length; }SqBiTree; 3) 不足：空间的利用率不高 如：若深度为 5 且仅含有 5 个结点的二叉树，必须要占用 2 4~2 5-1 空间。 2、二叉树的链式存储结构 1) 引入辅助空间表示结点间的相对关系 双亲(1)——孩子(2) (如右图) lchild data rchild parent lchild data rchild 二叉链表 三叉链表 若需要找指定结点的双亲，则用三叉链表可在 O(1)时间内获得某结点的双亲；而用二 叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ }BiTNode, *BiTree; 3) 二叉链表的链域 若有 n 个结点，则共有 2n 个链域；其中 n-1 不为空，指向孩子。 4) 二叉树(链式存储)的创建 输入序列与二叉树的映射关系 (1) 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按 自上而下、自左至右进行输入。 (2) 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍 历进行输入。 (3) 二叉树的两种遍历序列：先序+中序，后序+中序 6.3 树和森林 1、树的存储结构 1) 双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX_TREE_SIZE 100 /* 树的最大结点数 */ typedef struct PTNode{ ElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; /* 结点数 */ }PTree; 2) 孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的 data parent lchild rchild