第8章树和二叉树 树 二叉树 二叉树设计 主要知识点 二叉树遍历 线索二叉树 哈夫曼树 等价问题 树与二叉树的转换 树的遍历
第8章 树和二叉树 树 二叉树 二叉树设计 二叉树遍历 线索二叉树 哈夫曼树 等价问题 树与二叉树的转换 树的遍历 主 要 知 识 点
81树 1树的定义 树是由m(≥0个结点组成的有限集合T。n=0的树称为空 树;对n>0的树,有:(1)仅有一个特殊的结点称为根结点,根结 点没有前驱结点;(2)当m>1时,除根结点外其余的结点分为 m(m>0)个互不相交的有限集合T,T2,…,Tm,其中每个集合 T本身又是一棵结构和树类似的子树。 注:树的定义具有递归性,即“树中还有树
8.1 树 1.树的定义 树是由n(n≥0)个结点组成的有限集合T。n=0的树称为空 树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点，根结 点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为 m(m>0)个互不相交的有限集合T1 ,T2，…，Tm，其中每个集合 Ti本身又是一棵结构和树类似的子树。 注：树的定义具有递归性，即“树中还有树
若干术语 结点:由数据元素和构造数据元素之 间关系的指针组成 结点的度:结点所拥有的子树的个数 叶结点:度为0的结点,也称作 A 终端结点 B C D 分支结点:度不为0的结点 E F八(G(H(I (K F
若干术语 结点：由数据元素和构造数据元素之 间关系的指针组成 A B C E G I D F H J K L F 结点的度：结点所拥有的子树的个数 叶结点：度为0的结点，也称作 终端结点 分支结点：度不为0的结点
孩子结点:树中一个结点的子树的根结点 双亲结点:若树中某结点有孩子结点,则这个结点就 称作它的孩子结点的双亲结点 兄弟结点:具有相同的双亲结点的结点 树的度:树中所有结点的度的最大值 结点的层次:从根结点到树中某结点所经路径上的分支数 树的深度:树中所有结点的层次的最大值
孩子结点：树中一个结点的子树的根结点 双亲结点：若树中某结点有孩子结点，则这个结点就 称作它的孩子结点的双亲结点 兄弟结点：具有相同的双亲结点的结点 树的度：树中所有结点的度的最大值 结点的层次：从根结点到树中某结点所经路径上的分支数 树的深度：树中所有结点的层次的最大值
无序树:树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树 有序树:树中任意一个结点的各孩子结点有严格排列 次序的树 森林:m(m≥0)棵树的集合 2树的表示方法 (1)直观表示法 (2)形式化表示法 (3)凹入表示法
无序树：树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树 有序树：树中任意一个结点的各孩子结点有严格排列 次序的树 森林：m（m≥0）棵树的集合 2.树的表示方法 (1)直观表示法 (2)形式化表示法 (3)凹入表示法
T=(DR) DE=D,UD2U.UDm(Isi,jsm, D, nD=c) R={,i=1,2,,n-1} E F G
T=（D，R） DF = D1∪D2∪…∪Dm （1≤i,j≤m, Di∩Dj =￠） R={, i=1,2,…,n-1} A B C D E F G H I J K L
3.树的抽象数据类型 数据集合:树的结点集合,每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: (1)创建 Make tree(T) (2)撒消 Destroytree(T) (3)双亲结忘 Parent(T,curr) (4)左孩子结忘 LeftChild(T,curr) (5)右兄弟结点 RightSibling(T,curr) (6)遍历树 Traverse(T, Visito)
3.树的抽象数据类型 数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）双亲结点Parent(T, curr) （4）左孩子结点LeftChild(T, curr) （5）右兄弟结点RightSibling(T, curr) （6）遍历树Traverse(T, Visit())
4树的存储结构 树的结点之间的逻辑关系主要有双亲孩子关系,兄 弟关系。因此,从结点之间的逻辑关系分,树的存储 结构主要有:双亲表示法、孩子表示法、双亲孩子表 示法和孩子兄弟表示法四种组合。 指针有常规指针和仿真指针
4.树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄 弟关系。因此，从结点之间的逻辑关系分，树的存储 结构主要有：双亲表示法、孩子表示法、双亲孩子表 示法和孩子兄弟表示法四种组合。 指针有常规指针和仿真指针
data parent (1)双亲表示法 12345 ABCDEF 100 1 D(EF 6G2 4 8 HI 4 (a)一棵树 (b)仿真指针的双亲表示法存储结构 树及其使用仿真指针的双亲表示法
H 4 G 2 F 1 E 1 D 1 C 0 B 0 A -1 I 4 data parent 0 1 2 3 4 5 6 7 8 A B D E F H I C G (1)双亲表示法 (a)一棵树 （b)仿真指针的双亲表示法存储结构 树及其使用仿真指针的双亲表示法
root (2)孩子表示法 A、 B ∧∧ DAAA E/小F∧A人GAA 常规指针的孩子表示法
(2)孩子表示法 常规指针的孩子表示法 root B A ∧ C D E F G H I ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧