第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)凹入表示法