《数据结构用C语言描述》第六章.j.pptx

第六章树和二叉树;树的概念和基本术语;A;树的基本术语;二叉树 (Binary Tree);性质1 在二叉树的第 i 层上至多有 2i －1个结 点。(i 1) [证明用归纳法];性质2 深度为k 的二叉树至多有 2 k-1个结点(k 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为;性质3;两种特殊形态的二叉树;2;0) 个结点的完全二叉树的 ＋1;性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1, 2, …, n，则有以下关系：;二叉树的存储结构;·链表表示;二叉树链表表示的示例;三叉链表的静态结构;typedef char datatype; //结点数据类型;介绍按完全二叉树的层次顺序，依次输入结点信息建立二叉树的算法。 算法的基本思想： 1、依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。 2、若新结点是第一个结点，则令其为根结点；否 则作为孩子连接到其双亲结点上。 3、重复上述过程，至到输入结束信息为止。;为此，设置一个指针类型的数组队列，保存已输入结点的地址。 1、先输入的结点的孩子必定比后输入的结点的孩子先进 队列，因此可利用队头指针front指向当前必须与其孩子结点建立连接的双亲结点，利用队尾指针rear指向当前输入的结点。 2、若rear为偶数，作为左孩子与双亲连接，否则作为右 孩子与双亲连接。 3、若双亲结点或孩子结点为虚结点，则无须连接。 4、若双亲结点与其两个孩子连接完毕，则做出队操作，使头指针指向下一个等待连接的双亲结点。;bitree *Q[maxsize];;rear + + ; Q[rear] = s ;;二叉树遍历;· 中序遍历二叉树算法的定义： 若二叉树为空，则空操作；否则;void InOrder ( bitree *t) { if ( t != NULL ) { InOrder ( t->lchild ); printf(“\t%c\n”, t->data); InOrder ( t->rchild ); } };否则 访问根结点(D)； 前序遍历左子树(L)； 前序遍历右子树(R)。;·前序遍历二叉树的递归算法 void PreOrder ( bitree *t ) { if ( t != NULL ) { printf(“\t%c\n”,t->data); PreOrder ( t->lchild ); PreOrder ( t->rchild ); } };否则 后序遍历左子树(L)；后序遍历右子树(R)； 访问根结点(D)。;·后序遍历二叉树的递归算法：;int Count ( bitree *T ) { if ( T == NULL ) return 0; else;int Leaf_Count(Bitree *T) {//求二叉树中叶子结点的数目 if(!T) return 0; //空树没有叶子 else if(!T->lchild&&!T->rchild) return 1; //叶子结点 else return Leaf_Count(T.lchild)+Leaf_Count(T.rchild);左子树的叶子数加上右子树的叶子数 };int Height ( bitree * T ) { int m, n ; if ( T == NULL ) return -1; else { m = Height ( T->lchild ); n = Height ( T->rchild ); return (m > n) ? m+1 : n+1; } };4. 复制二叉树(递归算法);5. 判断二叉树等价(递归算法);中序遍历二叉树(非递归算法)用栈实现;void InOrder ( bitree *T ) { stack *S; SETNULL( S ); //递归工作栈 bitree *p = T; //初始化 while ( p != NULL || !Empty(S) ) { if( p != NULL ) { Push(S, p); p = p->lchild; };前序遍历二叉树(非递归算法)用栈实现;void PreOrder( bitree *T );·后序遍历二叉树(非递归算法)用栈实现;·void PostOrder ( BinTree T ) {;while ( continue && !StackEmpty(&S) ) { Pop (&S, w); p = w.ptr;;练习:交换二叉树各结点的左、右子树 (递归算法);void unknown ( bitree * T ) { bitree *p = T, *temp; while ( p != NULL ) { temp = p->lchild; p