08 树和二叉树PPT演示课件

树和森林,树的存储结构树的遍历操作树(森林)与二叉树的对应关系,1,树的存储结构,三种常用的(链式)存储结构双亲表示法孩子表示法孩子兄弟表示法,2,双亲表示法利用除根以外每个结点只有一个双亲的性质用一组连续空间存储树的结点每个结点中附设其双亲在链表中的位置指示,#defineMAX_TREE_SIZE100TypedefstructPTNnodeTElemTypedata;intparent;/双亲位置域PTNode;TypedefstructPTNodenodesMAX_TREE_SIZE;intn;/结点数Ptree;,3,双亲表示法，如：这种表示法便于寻找某结点的双亲和树根结点，但寻找孩子结点需遍历整个结构HOW?,R,B,A,C,D,E,F,H,G,K,R-1,A0,B0,C0,D1,E1,F3,G6,H6,K6,0,1,2,3,4,5,6,7,8,9,4,孩子表示法法一：每个结点有多个指针域，构成多重链表特点：空间浪费大，操作不便,datachild1child2childd,datadegreechild1child2childd,(结点同构，d为树的度数),(结点不同构，d为结点的度数),或,5,孩子表示法法二：将结点组成顺序表，每个结点一个孩子链表,该结构便于查找孩子结点,6,孩子兄弟表示法以二叉链表作为树的存储结构。又称二叉树表示法，或二叉链表表示法链表中结点的两个链域分别指向其第一个孩子和下一个兄弟,TypedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,7,孩子兄弟表示法，如：,该结构便于查找孩子结点,8,练习分别给出用双亲表示法、孩子表示法和孩子兄弟表示法表示的树的存储结构,A,B,G,C,D,E,F,9,树(森林)与二叉树的转换,二叉链表即可用于表示二叉树的存储结构，又可用于表示树的存储结构。因此，以二叉链表为介，对于给定的树(或森林)，可以确定唯一的一棵二叉树与之对应。反之亦然,10,如,A,C,B,E,D,A,C,B,E,D,11,树二叉树的转换规则树中某结点的第一个孩子成为对应二叉树中该结点的左孩子树中某结点的右兄弟结点成为对应二叉树中该结点的右孩子树对应的二叉树根结点的右子树总为空，即树对应的二叉树中没有右子树自然方法凡兄弟就用线连，然后去掉父母到子女的连线，只剩下父母到第一个孩子的连线，然后倾斜即可,12,树二叉树的转换，如,A,C,B,I,D,A,C,B,I,D,E,F,E,F,13,练习：将树转换为对应的二叉树,14,二叉树树的转换规则若某结点是父母的左孩子，则把该结点的右孩子，右孩子的右孩子，都与该结点的父结点用线相连，最后去掉所有父母到右子女的连线如,A,B,D,C,I,G,F,A,B,D,C,I,G,F,K,K,15,二叉树树的转换，如,16,森林二叉树的转换规则第一棵树的树根为对应的二叉树的根将各树的树根看成是兄弟每各树先各自转换为二叉树将各对应的二叉树集成特点：森林对应的二叉树中有右子树,17,森林二叉树的转换，如,A,C,B,D,E,F,G,I,H,J,18,二叉树森林的转换规则若某结点是父母的左孩子，则把该结点的右孩子，右孩子的右孩子，都与该结点的父结点用线相连，最后去掉所有父母到右子女的连线如,A,B,D,C,E,K,H,F,J,G,19,树(森林)的遍历,先(根次)序遍历操作访问头一棵树的根先(根次)序下遍历头一棵树根的子树先(根次)序下遍历其它树如,A,B,C,K,D,E,F,J,G,H,先(根次)序遍历序列：ABCKDEHFJG,20,后(根次)序遍历操作后(根次)序下遍历第一棵树根的子树访问头一棵树的根后(根次)序下遍历其它树如,A,B,C,K,D,E,F,