数据结构第八树和二叉树副本分析.ppt

* 8.4 线索二叉树 本题的线索维护操作如下：请标出其操作示意图。 s-lchild=p; s-ltag=1; s-rchild=p-rchild; s-rtag=1; p-rchild=s; p-rtag=1; if (s-rchild-ltag==1) s-rchild-lchild=s; 习题：设计算法将s结点作为A的右子树的最右下的叶子结点的左孩子插入到先序线索二叉树中，并维护其线索关系。 先序线索二叉树 A B C D G F E H I P s * 8.5 树和森林 8.5.1树/森林的存储结构 1. 双亲表示法 存储每个结点的双亲结点的位置信息。 例如： 优点：简洁， 形式一致； 搜索父结点、祖先容易 缺点：搜索孩子结点费时； 插入删除时需注意维护关系 A B C D E F G H I J K A B C G F E H I J K D data parents 0 1 2 3 4 5 6 7 8 9 10 -1 0 0 0 1 1 2 3 3 3 4 struct tsnode { elementtype data; int parent; }; struct tsnode treelist[maxnum]; * 8.5 树和森林 2. 孩子链表表示法 存储每个结点的孩子信息，因而是链表形式。 优点：找孩子结点/后代容易 缺点：重复，结构不一致，不便于找双亲结点 B C D ^ E F ^ G ^ K ^ H I J ^ A B C G F E H I J K D A B C D E F ^ G ^ H ^ I ^ J ^ K ^ data children_link 0 1 2 3 4 5 6 7 8 9 10 * 8.5 树和森林 3. 孩子-兄弟链表表示法 表示方法：采用链表结构来存储树， 链表中结点与树中结点一一对应， 每个结点存储其第一个孩子结点 和下一个兄弟结点的指针。 由此而得名。 也叫二叉链表表示法，或二叉树表示法。 firstson data nextbrother 指向其第一个孩子结点 指向其下一个兄弟结点 typedef struct Treenode { elementtype data; struct Treenode * firstson,*nextbrother; }tnode; * 8.5 树和森林 前述树所对应的存储结构如下： A ^ ^ F ^ B ^ G ^ C ^ K ^ D ^ ^ J ^ ^ I ^ H E A B C G F E H I J K D * 8.5 树和森林 将前述孩子兄弟链表顺时针旋转45。， 对应到一个二叉链表， 因此也对应到一棵二叉树。 ^ H ^ G ^ D ^ ^ F ^ A ^ B C E ^ I ^ K ^ ^ J ^ A B C G F E H I J K D 8.5 树和森林 * A F E D C B I H G K J 1.把树中所有的兄弟之间用树枝相连； 2.每个结点仅保留与长子的连线，删除结点与其余孩子的连线； 3.以树根为圆心，顺时针转45度。 A K J D C B I H G F E 一般树转化为二叉树 * 8.5 树和森林 如果是森林，其存储如何？ 森林 二叉链表（二叉树） 由图可知，这其实是二叉链表结构， 所以，任意一棵树（森林）必然与唯一的一棵二叉树一一对应。 A B C G F