[互联网]数据结构与算法 树.ppt

3.7.2 二叉排序树 定义： 二叉排序树或者是一棵空树，或者是具有下列性质的 二叉树： 1、若它的左子树非空，则左子树上的所有结点的值均 小于它的根结点的值。 2、若它的右子树非空，则右子树上的所有结点的值均 大于或等于它的根结点的值。 3、它的左右子树分别为二叉排序树。 3.7.3 树的应用—判定树 假定有八枚硬币a、b、c、d、e、f、g、h，已知其中1枚是 伪造的假币，假币的重量与真币不同，或重或轻。要求以 天平为工具，用最少的比较次数挑出假币。 H—假币重于真币；L —假币轻于真币。 算法见P123 a+b+c ? d+e+f a+d ? b+e a+d ? d+e g ? h a?b c?a b?a a?b a?c b?a g?a h?a a H e L c H f L b H d L g H h L h H g L b L d H c L f H a L e H = = = = = = = = = = = 树 先根顺序 中根顺序 后根顺序 层序遍历* 双亲表示法(数组) 孩子表示法(邻接表) 左右链表示(二叉树) 树的ADT 逻辑结构 存储结构 树的存储结构 递归 非递归* 树的应用 哈夫曼树 判定过程 二叉树 逻辑结构 存储结构 基本性质 遍历二叉树 线索二叉树 二元排序树 顺序存储 二叉链表 本章作业： P120-124 12 13 14 16 34，36 线索二叉树 问题的提出： 1、在n个结点的二叉树左右链表示中，有n+1个空链域。 如何利用n+1个空链域，使二叉树的操作更加方便。 2、在二叉树左右链表示中，为求某个结点的（中序）前 驱 $P 或（中序）后继 p$，每次都要从树根开始进行 查找，很不方便。 定义： 若结点p有左孩子，则p-lchild指向其左孩子结点， 否则令其指向其（中序）前驱。 若结点p有右孩子，则p-rchild指向其右孩子结点， 否则令其指向其（中序）后继。 lchild ltag rchild rtag data 结点类型 Node Struct LNode { Elementtype data ; Struct LNode *lchild , *rchild ; int ltag , rtag ; } P-ltag = p-lchild 指向左孩子 0 p-lchild 指向（中序）前驱 P-rtag = p-rchild 指向右孩子 0 p-lchild 指向（中序）后继 讨论：为方便操作利用了 n+1 个结点，但为实现操作却 多用了 2n 个标志位。 Typdef Struct LNode * THTREE; 类似线性链表，为每个线索树增加一个头结点。并设： head-lchild = T (二叉树的根) ; head-rchild = head ; head-ltag = 1 ; head-rtag = 1 ; 当线索树为空时： head-lchild = head ; head-rchild = head ; head-ltag = 0 ; head-rtag = 1 ; 中序线索化： 1、将二叉树的空指针改为指向前驱或后继的线索； 2、前驱或后继的信息只有在遍历时才能得到； 3、线索化：在遍历的过程中修改线索； pre 始终指向刚刚访问过的节点； p 指向当前访问过的节点，pre指向他的前驱； Status InOrderThreading(THTREE Thrt, THTREE T) { if ( !(Thrt = (THTREE)malloc(Sizeof(LNode)))) exit(OVERFLOW); //头结点 Thrt-ltag = 0 ; Thrt-rtag = 1 ; Thrt-rchild = Thrt; //右指针回指 if ( !T ) Thrt-lchild = Thrt ; //若二叉