[工学]数据结构讲义-树和二叉树.ppt

6.1 树的定义和基本术语 6.1 树的定义和基本术语 双亲(parent)结点：子结点的直接前驱结点。 兄弟(sibling)结点：同一双亲的子结点互称兄弟结点。 结点的层次(level)：根为第一层；子结点的层次比双亲结点的层次加1。 树的深度(depth)：树中结点的最大层次。 有序树：子树从左到右有序。 无序树：子树无序。 森林(forest)：m（m=0）棵互不相交的树的集合。 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.2 二叉树 6.3 遍历二叉树和线索二叉树 typedef struct BiThrNode { TELemType data; struct BiThrNode *lchild; struct BiThrNode *rchild; unsigned ltag; unsigned rtag; } BitThrNode, * BiThrTree; 本节课后作业 “数据结构题集（C 语言版）” P38 6.4 P39 6.13 P42 6.42 单周周一交作业！ 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.4 树和森林 6.6 赫夫曼树及其应用 6.6 赫夫曼树及其应用 6.6 赫夫曼树及其应用 本节课后作业 “数据结构题集（C 语言版）” P41 6.21、 P41 6.23 P41 6.25 P42 6.26 ……… A B C D F G H I J E A 1 2 3 -1 B 4 5 -1 0 C 6 -1 -1 0 D 7 8 -1 0 E -1 -1 -1 1 F -1 -1 -1 1 G -1 -1 -1 2 H 9 -1 -1 3 I -1 -1 -1 3 J -1 -1 -1 7 0 1 2 3 4 5 6 7 8 9 用数组（静态链式存储）表示左图的树，-1 表示空。 缺点：空指针域太多，有( K -1 )× n + 1 个。 例: 度数 K ＝ 3 的树 6.4.1 树的存储结构 1 孩子(双亲）表示法：由数据域、 K 个子结点指针域（父结点 指针域）组成。 data child1 child2 childk parents A B C D F G H I J E A ∧ B C D ∧ F ∧ ∧ G ∧ H ∧ I ∧ ∧ E ∧ J ∧ 2 孩子兄弟表示法：由数据域、指向它的第一棵子树树根的指针域、指向它的兄弟结点的指针域组成。实质上是用二叉树表示一棵树。 （右子树为空） firstchild data nextsibling A B C D F G H I J E A B C D F G H I J E A B C D F G H I J E 6.4.2 树、森林与二叉树的转换 1 树转换成相对应的二叉树：（右子树必为空） 1）保留每个结点的最左面的分支，其余分支都被删除。 2）同一父结点下面的结点成为它的左方结点的兄弟。 B C D F G H I J E B C D F G H I J E A B C D F G H I J E A 2 森林转换成相对应的二叉树： 增加一个虚拟的根结点，它的子结点为各棵树的根。 那么，就变成了树转换成二叉树的问题。 N B C D F G H I J E A T1 T2 …… T3 L R 先根：A B E F C G D H J I 后根：E F B G C J H I D A 6.4.3 树、森林的遍历 1 树的先根、后根遍历： 1）先根：类似于二叉树的先序遍历（NLR） N:根；L：第一棵子树，R：其余的子树，遍历方向由第二棵子树至最后一棵子树。 2）后根：类似于二叉树的中序遍历（LRN） L：第一棵子树，R：其余的子树，遍历方向由第二棵子树至最后一棵子树， N:根。 先序：B E F C G D H J I 后序：E F B G C J H I D