《数据结构实用第五章PPT演示课件》由会员分享，可在线阅读，更多相关《数据结构实用第五章PPT演示课件（94页珍藏版）》请在金锄头文库上搜索。
1、.,1,树的定义和基本术语 二叉树 (Binary Tree) 二叉树的存储结构 遍历二叉树 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 树与森林 (Tree SqBiTree bt;,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,单支树,.,15,2.链式存储结构,typedef struct BiTNode /二叉链表的定义 TElemType data; Struct BiTNode *lchild,*rchild; BiTNode, *BiTree;,.,16,二叉树链表表示的
2、示例,.,17,3. 静态二叉链表和静态三叉链表,预先开辟空间，用数组表示 leftChild, rightChild数组元素的下标,.,18,6.3 遍历二叉树 (Traversing Binary Tree) p128,所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 遍历的结果：产生一个关于结点的线性序列。 设访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 先序 DLR DRL 逆先序 中序 LDR RDL 逆中序 后序 LRD RLD 逆后序,.,19,先序遍历 (Preorder Traversal),先序遍历二叉
3、树算法的框架是 若二叉树为空，则空操作； 否则 访问根结点 (D)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。,.,20,遍历结果（前缀表达式） - + a * b - c d / e f,在波兰式中，自左到右依次扫描：连续出现2个操作数时，将其前面的运算符退出，对该两操作数进行这两个操作数前面的运算符的运算，运算的中间结果进栈，然后再进行上述的操作。,.,21,先序遍历二叉树的递归算法 void PreOrderTraverse(BiTree T) if (T) printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTrave
4、rse(T-rchild); ,.,22,中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。 遍历结果（中缀表达式） a + b * c - d - e / f,中序遍历 (Inorder Traversal),表达式语法树,.,23,中序遍历二叉树的递归算法 void InOrderTraverse(BiTree T) if (T) InOrderTraverse(T-lchild); printf(%c,T-data); InOrderTraverse(T-rchild); ,.,24,后序遍历 (Post
5、order Traversal),后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。,.,25,在逆波兰式中，自左到右依次扫描：是操作数，则依次进栈；遇到运算符。则退出两个操作数，对该两操作数进行该运算符的运算，运算的中间结果进栈；然后再继续重复上述的操作。,遍历结果（后缀表达式） a b c d - * + e f / -,.,26,后序遍历二叉树的递归算法 void PostOrderTraverse(BiTree T) if (T) PostOrderTraverse(T-lchild); PostOrde
6、rTraverse(T-rchild); printf(%c,T-data); ,.,27,由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例, 先序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,.,28,遍历二叉树的非递归算法,先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈 中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树 后序遍历： 1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它
7、的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。 2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈,.,29,需用到栈，顺序栈的定义如下： typedef BiTNode* SElemType; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,.,30,先序遍历的非递归算法 void preorder(BiTree T) SqStack S; BiTree P=T; InitStack(S);Push(S,NULL); while
8、 (P) printf(%c,P-data); if (P-rchild) Push(S,P-rchild); if (P-lchild) P=P-lchild; else Pop(S,P); ,.,31,先序遍历的非递归算法2 void preorder(BiTree T) int top=0; BiTree stack20, P=T; do while (P) printf(%c,P-data); stacktop=P; top+; P=P-lchild; if (top) top-;P=stacktop; P=P-rchild; while (top | P); ,.,32,中序遍历的非
9、递归算法1 void inorder(BiTree T) SqStack S; BiTree P=T; InitStack(S); dowhile(P) * (S.top) = P;S.top+; P=P-lchild; if (S.top) S.top-;P=*(S.top); printf(%c,P-data); P=P-rchild; while(S.top!=S.base) | P); ,.,33,中序遍历的非递归算法2（p131算法6.3) void inorder(BiTree T) SqStack S; BiTree P=T; InitStack(S); while( P | !
10、Empty(S) if (P) Push(S,P); P=P-lchild; else Pop(S,P); printf(%c,P-data); P=P-rchild; ,.,34,后序遍历时，每遇到一个结点，先把它推入栈中，让PopTim=0。在遍历其左子树前，改结点的PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改结点的PopTim=2，并把其右孩子推入栈中。在遍历完右子树后，结点才退栈访问。,.,35,后序遍历的非递归算法1 void Postorder(BiTree T) BiTree p=T,q=NULL; SqStack S;In
11、itStack(S); Push(S,p); while (!StackEmpty(S) if (p ,.,36,后序遍历的非递归算法2 void postorder(BiTree T) BiTree P=T,q; int flag;SqStack S;InitStack(S); do while (P) *(S.top)=P;S.top+;P=P-lchild; q=NULL; flag=1; while (S.top!=S.base) ,.,37,先序建立二叉树的递归算法(p131,算法6.4) Status CreateBiTree(BiTree ,.,38,二叉树的显示输出,void
12、PrintBiTree(BiTree T,int n) int i; char ch= ; if (T) PrintBiTree(T-rchild,n+1); for (i=1;idata); PrintBiTree(T-lchild,n+1); ,.,39,说明：,1）遍历的第一个和最后一个结点 第一个结点： 先序：根结点； 中序：沿着左链走，找到一个没有左孩子的结点； 后序：从根结点出发，沿着左链走，找到一个既没有左孩子又没有右孩子的结点。 最后一个结点： 中序：从根结点出发，沿着右链走，找到一个没有右孩子的结点； 后序：根结点。,.,40,先序：从根结点出发，沿着右链走，找到一个没有右孩
13、子的结点；如果该结点有左孩子，再沿着其左孩子的右链走，以此类推，直到找到一个没有孩子的结点 求中序的第一个结点的算法： P=T; while (P-lchild) P=P-lchild; printf(P-data); 求中序的最后一个结点的算法： P=T； while(P-rchild) P=P-rchild; Printf(P-data);,.,41,2）先序+中序 或 后序+中序均可唯一地确定一棵二叉树 3）二叉树的二叉链表存储结构中，有n+1个指针域未利用，已经使用的有n-1个指针域，共有2n个指针域,.,42,利用二叉树后序遍历计算二叉树的深度,int Depth(BiTree T)
14、 int depl,depr; if (T) depl=Depth(T-lchild); depr=Depth(T-rchild); if (depl=depr) return (depl+1); else return (depr+1); return 0; ,遍历二叉树的应用,.,43,求二叉树结点个数 int Size(BiTree T) if (T=NULL) return 0; else return 1 + Size (T-lchild ) + Size ( T-rchild); ,.,44,按层次遍历二叉树 从根开始逐层访问，用FIFO队列实现。 typedef BiTNode*
15、 ElemType; typedef struct QElemType *base; int front,rear; SqQueue;,遍历顺序,.,45,void LevelOrderTraverse(BiTree T) BiTree p; SqQueue Q; InitQueue(Q); if (T) Q.baseQ.rear=T; Q.rear=(Q.rear+1)%MAXQSIZE; while (Q.front !=Q.rear) p=Q.baseQ.front; printf(%c,p-data); Q.front=(Q.front+1)%MAXQSIZE; if (p-lchil
16、d) Q.baseQ.rear=p-lchild; Q.rear=(Q.rear+1)%MAXQSIZE; if (p-rchild) Q.baseQ.rear=p-rchild; Q.rear=(Q.rear+1)%MAXQSIZE; ,.,46,左右子树互换 void Exchange(BiTree ,.,47,复制二叉树 void CopyTree(BiTree T,BiTree ,.,48,线索二叉树（穿线树、线索树） (Threaded Binary Tree),线索 (Thread): 指向结点前驱和后继的指针 若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前驱结点的指针； 若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针 实质：对一个非线性结构进行线性化操作，使每个结点（除第
