第6章树与二叉树-ppt课件

1、第第6 6章章 树与二叉树树与二叉树23456789 其中1011121314151617 kii1 ）（层层上上最最大大结结点点数数第第 kii1121819202122232425262728293031323334353637383940414243444546(2)(2)算法描画算法描画4849505152535455PostOrder 非递归算法的时间复杂度非递归算法的时间复杂度 假定二叉树假定二叉树 root 有有 n 个结点，算法中对每个结点个结点，算法中对每个结点都要进展两次入栈和出栈。因此，入栈和出栈都要执都要进展两次入栈和出栈。因此，入栈和出栈都要执行行 2n 次，那么入栈

2、、出栈的时间复杂度为次，那么入栈、出栈的时间复杂度为 O(n)。 此外，每当此外，每当 Data.p 为空时，就弹出栈顶的数据项为空时，就弹出栈顶的数据项 Data，然后根据，然后根据 Data.tag 的值能否为零，或访问刚弹的值能否为零，或访问刚弹出的结点，或使数据项重新进栈。重新入栈的时间曾出的结点，或使数据项重新进栈。重新入栈的时间曾经算在入栈、出栈所需时间之内，访问结点的时间显经算在入栈、出栈所需时间之内，访问结点的时间显然为然为 O(n)。所以，算法总的时间复杂度为。所以，算法总的时间复杂度为 O(n)+O(n)，或者为或者为 O(n)。5657585960616263646566

3、6768697071727374757677p.rchild,r,t.rtag = 0。78int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) / 将新结点将新结点r插入到中序线索树中作为结点插入到中序线索树中作为结点 p的右孩子，并前往的右孩子，并前往 OK(2) 算法描画算法描画79 (3) 算法分析算法分析808182void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序线索树的头结点，指向中序线索树的头结点， 头结点的左链域头结点的左链域 lchild 指向根结点，指向根结点，遍历中序线索树遍历中序

4、线索树 T 的非递归算法，的非递归算法， 对每个数据元素调用函数对每个数据元素调用函数 Visit 。*/ p = Thrt-lchild; / p 指向根结点指向根结点 while ( p != Thrt ) / 当空树或遍历终了时，当空树或遍历终了时，p = = Thrt while ( p-ltag = = 0 ) p = p-lchild; / 顺着顺着 p 的左链域寻觅，直到结点左标志是的左链域寻觅，直到结点左标志是 1 时为止时为止 if ( ! Visit ( p-data ) ) return ERROR; / 访问其左子树为空的结点访问其左子树为空的结点 while ( p-

5、rtag = = 1 & p-rchild ! = Thrt ) / 当当 p 右标志为右标志为 1 且右链域且右链域 rchild 不为头结点时，不为头结点时， 那么访问后继那么访问后继结点结点 p = p-rchild; Visit ( p-data ); / while / InOrderTraverse(2) (2) 算法描画算法描画8485 (1) 算法思想算法思想86 由于线索化的本质是将二叉链表中的空指针改为由于线索化的本质是将二叉链表中的空指针改为指向前驱或后继线索，而前驱或后继的信息只需在遍指向前驱或后继线索，而前驱或后继的信息只需在遍历时才干得到，因此线索化的过程即

6、为在遍历的过程历时才干得到，因此线索化的过程即为在遍历的过程中修正空指针的过程。中修正空指针的过程。 为了记下遍历过程中访问结点的先后关系，需求为了记下遍历过程中访问结点的先后关系，需求附设指针附设指针 pre 一直指向刚刚访问过的结点，假设指针一直指向刚刚访问过的结点，假设指针 p 指向当前访问的结点，那么指向当前访问的结点，那么 pre 指向它的前驱。指向它的前驱。 先线索化以先线索化以 root 为根的二叉树，为根的二叉树， 后线索化头结点后线索化头结点。876.5 树和森林与二叉树的转换树和森林与二叉树的转换树与二叉树的转换树与二叉树的转换森林与二叉树的转换森林与二叉树的转换树和森林的

7、遍历树和森林的遍历888990 加线：假设加线：假设 p 结点是双亲的左孩子，那么将结点是双亲的左孩子，那么将 p 结结点的右孩子，右孩子的右孩子，点的右孩子，右孩子的右孩子，沿着右分支搜索，沿着右分支搜索到的一切右孩子，都分别与到的一切右孩子，都分别与 p 结点的双亲用线连起来；结点的双亲用线连起来； 除线：去除原二叉树中一切双亲结点与右孩子的除线：去除原二叉树中一切双亲结点与右孩子的连线；连线； 旋转：以树的根结点为轴心，按逆时针方向旋转旋转：以树的根结点为轴心，按逆时针方向旋转 45。91929394 抹线：抹掉二叉树根结点右链上一切结点上的抹线：抹掉二叉树根结点右链上一切结点上的连线，

8、分成假设干个以右链上结点为根结点的子二叉树；连线，分成假设干个以右链上结点为根结点的子二叉树； 转换：将分好的子二叉树转换成树；转换：将分好的子二叉树转换成树； 调整：将转换好的树的根结点陈列成一排。调整：将转换好的树的根结点陈列成一排。959697森林的先序序列对森林的先序序列对应转换之后二叉树应转换之后二叉树的先序序列。的先序序列。9899100101 nkkklwWPL11021031041056.5.2 哈夫曼树的构造哈夫曼树的构造 举例：5，11，26，18，34，15，6构成一棵哈夫曼树6 5111518263411223348771256.5.2 哈夫曼树的构造哈夫曼树的构造 整

9、理上面的哈夫曼树如图：6 511151826341122334877125哈夫曼树的构造算法哈夫曼树的构造算法 哈夫曼树的类型定义：用静态三叉链表实现哈夫曼哈夫曼树的类型定义：用静态三叉链表实现哈夫曼树类型定义如下：树类型定义如下： #define N 20 /*叶子结点最大值叶子结点最大值*/ #define M 2*N-1 /*一切结点的最大值一切结点的最大值*/ typedef struct int weight; /*结点的权值结点的权值*/ int parent; /*双亲的下标双亲的下标*/ int Lchild; /*左孩子结点的下标左孩子结点的下标*/ int Rchild;

10、/*右孩子结点的下标右孩子结点的下标*/ HTNode,HuffmanTreeM+1; 哈夫曼树的构造哈夫曼树的构造 哈夫曼树构造算法分为两步：哈夫曼树构造算法分为两步： 第一步对初始形状的设置。在该步骤中，让第第一步对初始形状的设置。在该步骤中，让第1到到n的单位的权值为所給权值，从第的单位的权值为所給权值，从第n+1到第到第m=2n-1的单的单元的权值都为元的权值都为0.让一切结点的双亲和孩子值都为让一切结点的双亲和孩子值都为0.即即创建创建n个子树，每棵树只需根结点。个子树，每棵树只需根结点。 第二步开场实现构造过程，即选取权值最小的两棵第二步开场实现构造过程，即选取权值最小的两棵树根双

11、亲为树根双亲为0进展合并，构造一棵新的树产生进展合并，构造一棵新的树产生新的结点，该树的根结点权值为所选的两棵树的新的结点，该树的根结点权值为所选的两棵树的权值之和，且左右孩子分别为上述所选的两棵树，权值之和，且左右孩子分别为上述所选的两棵树，即所选出的两棵树的双亲为新构造的结点。构造出即所选出的两棵树的双亲为新构造的结点。构造出来的新结点依次存放在第来的新结点依次存放在第n+1到第到第m的单元上。的单元上。 哈夫曼树的构造哈夫曼树的构造void CrtHuffmanTree(HuffmanTree ht, int w , int n) / 第一步：对初始形状的设置。第一步：对初始形状的设置。

12、 for(i=1;i=n;i+) hti=wi,0,0,0 ; m=2*n-1; for(i=n+1;i=m;i+) hti=0,0,0,0; /第二步第二步:创建非叶子结点，开场实现构造过程创建非叶子结点，开场实现构造过程. for(i=n+1;ikey=key; s-Lchild=NULL; s-Rchild=NULL; *bst=s; void InsertBSTBSTree *bst , DataType e)/*假设在二叉排序树假设在二叉排序树bst中不存在关键字等于中不存在关键字等于key的元的元素，插入该元素素，插入该元素*/else if(keykey) InsertBST(&

13、amp;(*(bst)-Lchild),key); void InsertBSTBSTree *bst , DataType e)/*假设在二叉排序树假设在二叉排序树bst中不存在关键字等于中不存在关键字等于key的元的元素，插入该元素素，插入该元素*/else if(keykey) InsertBST(&(*(bst)-Lchild),key); else if(key(*bst)-key) InsertBST(&(*(bst)-Rchild),key); 二叉排序树创建算法描画：二叉排序树创建算法描画：void CreateBSTBSTree *bst)/*从键盘输入元素的

14、值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key; *bst=NULL; 键盘输入元素值键盘输入元素值key； while当当key值满足条件值满足条件 InsertBST(bst , key); /插入插入 键盘输入元素值键盘输入元素值key; void CreateBSTBSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key; *bst=NULL; 键盘输入元素值键盘输入元素值key； while当当key值满足条件值满足条件 InsertBST(bst , key

15、); /插入插入 键盘输入元素值键盘输入元素值key; 练习：练习： 设关键字的输入顺序为：设关键字的输入顺序为：12，24，28，53，90，45，画出所生成的二叉排序树。，画出所生成的二叉排序树。 二叉排序树查找二叉排序树查找算法思想：算法思想：首先将待查关键字与根结点关键字首先将待查关键字与根结点关键字t进展比较，进展比较，假设：假设： 1key=t: 那么前往根结点地址；那么前往根结点地址； 2keyt: 那么进一步查找右子树；那么进一步查找右子树； 算法实现递归算法实现递归BSTree SearchBST(BSTree bst , KeyType key) if(!bst) retu

16、rn NULL; else if(bst-key=t)return bst; /假设查找胜利，那么前往假设查找胜利，那么前往 else if(bst-keykey ) return SearchBST(bst-Lchild , key); else return SearchBST(bst-Rchild , key);二叉排序树的删除二叉排序树的删除从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二从二叉排序树中删除一个结点，要保证删除后的二叉树还是一棵二叉排序树。叉排序树。算法思想：首先查找要删除结点，假设查找失败，那么不作任何删算法思想：首先查找要删除结点，假设查找失败，那么不作任

17、何删除操作，否那么，假设要删除的结点为除操作，否那么，假设要删除的结点为p，其双亲结点为，其双亲结点为f，并假设，并假设p是是f的左孩子右孩子情况类似，那么删除过程分为三种情况讨的左孩子右孩子情况类似，那么删除过程分为三种情况讨论：论：1假设假设p为叶子结点，那么直接删除该结点，其双亲的左孩子为为叶子结点，那么直接删除该结点，其双亲的左孩子为空：空： f-Lchild=NULL;free(p);2假设假设p为单分支结点，即为单分支结点，即p只需左子树，或者只需右子树，那只需左子树，或者只需右子树，那么可将么可将p的左子树或者右子树直接改为其双亲结点的左子树或者右子树直接改为其双亲结点f的左子树

18、：的左子树： f-Lchild=p-Lchild;(或者或者 f-Lchild=p-Rchild;) free(p); 二叉排序树的删除二叉排序树的删除3假设假设p为双分支结点，那么有两种处置方法：为双分支结点，那么有两种处置方法：方法方法1：找到：找到p结点在中序遍历序列中的直接前驱结点在中序遍历序列中的直接前驱s，将，将p的左子树的左子树改为改为f的左子树，将的左子树，将p的右子树改为的右子树改为s的右子树：的右子树：f-Lchild=p-Lchild; s-Rchild=p-Rchild;free(p);方法方法2：找到：找到p结点在中序遍历序列中的直接前驱结点在中序遍历序列中的直接前驱

19、s，然后用，然后用s结点替结点替代代p结点的值，再将结点的值，再将s结点删除，原结点删除，原s结点的左子树改为其双亲结点结点的左子树改为其双亲结点假设为假设为q的右子树：的右子树：p-key=s-key ; q-Rchild=s-Lchild; free(s);上述的两种方法中还可以将寻觅上述的两种方法中还可以将寻觅p结点的中序遍历前驱改成寻觅中结点的中序遍历前驱改成寻觅中序遍历后继，请同窗们思索一下。序遍历后继，请同窗们思索一下。二叉排序树的删除算法描画二叉排序树的删除算法描画BSTNode * DelBST(BSTree t , KeyType k)BSTNode *p , *q , *f

20、 , *s ; /*查找关键字为查找关键字为k的待删除结点位置的待删除结点位置*/ p=t; f=NULL ; /从根结点开场查找从根结点开场查找 while(p) if(p-key=k)break ; f=p; /记录双亲结点位置记录双亲结点位置 if(p-keyk)p=p-Lchild; else p=p-Rchild ; if(p=NULL)return t ; /查找不胜利，不作任何操作，直接前往查找不胜利，不作任何操作，直接前往 /假设查找胜利，那么查看假设查找胜利，那么查看p的情况的情况 if(p-Lchild=p-Rchild=NULL) /p是叶子结点是叶子结点 if(f=NU

21、LL)t=f ; return t; else if(p=f-Lchild)f-Lchild=NULL; free(p); else if(p=f-Rchild)f-Rchild=NULL;free(p); 二叉排序树的删除算法描画二叉排序树的删除算法描画else /假设假设p是单分支结点是单分支结点 if(p-Lchild=NULL) /p无左子树无左子树 if(f=NULL)t=p-Rchild; else if (f-Lchild=p) /假设假设p是是f的左孩子的左孩子 f-Lchild=p-Rchild; /p的右子树作为的右子树作为f的左子树的左子树 else f-Rchild=p

22、-Rchild ; /p的右子树作为的右子树作为f的右子树的右子树 free(p); if(p-Rchild=NULL) /p无右子树无右子树 if(f=NULL)t=p-Lchild; else if(f-Lchild=p) f-Lchild=p-Lchild; else f-Rchild=p-Lchild; 二叉排序树的删除算法描画二叉排序树的删除算法描画 /假设假设p是双分支结点是双分支结点 if(p-Lchild!=NULL & p-Rchild!=NULL) /寻觅寻觅p的左子树的最右端结点的左子树的最右端结点 q=p; s=p-Lchild; while(s-Rchild) q=s ; s=s-Rchild; if(q=p)q-Lchild=s-Lchild; else q-Rchild=s-Lchild; p-key=s-key; free(s); /if /else return t; /DelBST 举例：如图是一棵二叉排序树，分别删除举例：如图是一棵二叉排序树，分