数据结构课件6树和二叉树2章节幻灯片.ppt

树和二叉树（ 2） 梁春燕 华北电力大学 信息管理教研室 主要内容 树的存储结构 树与二叉树转换 森林与二叉树转换 树和森林的遍历 Huffman树及其应用 树的存储结构 树的存储结构 双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难 typedef struct node { datatype data; int parent; }JD; JD t[M]; a b c d e f h g i a c d e f g h i b 0 1 2 2 3 5 5 5 1 0 9 6 0 1 2 3 4 5 7 8 9 data parent 0号单元不用或 存结点个数 如何找孩子结点 孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d data child1 child2 ………. childD data degree child1 child2 ………. childd 孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表 孩子结点：typedef struct node { int child; //该结点在表头数组中下标 struct node *next; //指向下一孩子结点 }JD; 表头结点：typedef struct tnode { datatype data; //数据域 struct node *fc; //指向第一个孩子结点 }TD; TD t[M]; //t[0]不用 a b c d e f h g i 6 0 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 ^ 4 5 ^ ^ 9 7 8 ^ 6 ^ ^ ^ ^ ^ 如何找双亲结点 带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 4 5 9 7 8 6 ^ ^ ^ ^ ^ ^ ^ ^ ^ 0 1 2 2 3 5 5 5 1 parent a b c d e f h g i 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点 操作容易 破坏了树的层次 typedef struct node { datatype data; struct node *fch, *nsib; }JD; a b c d e f h g i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 树与二叉树转换 A C B E D 树 A B C D E 二叉树 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 对应 存储 存储 解释 解释 将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45° A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树其右子树一定为空 将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之