《数据结构与算法》数据结构补充

遍历二叉树的递归算法 先序遍历的非递归算法2 先序遍历二叉树的递归算法 void preorder( BiTree D)i void PreOrder Traverse( BiTree T) BiTree stack[20], P=T, if (D)i while(P)i rinf("%c",T->data) printf("%c", P->data) PreOrder Traverse(T->lchild) stack[ top]=P; top++ PreOrder Traverse(T->rchild) P=P->lchild; i if(top)i op--, P=stacktopl 中序遍历二叉树的递归算法 P=P->rchild void In Order Traverse( BiTree T while(top‖P) if (T)i 中序遍历:在遍历左子树之前,先把根结点入栈, InOrder Traverse(T->lchild) 当左子树遍历结束后,从栈中弹出,访问,再遍历 printf("%c",T->data); 右子树 In Order Traverse(T->rchild) 中序遍历的非递归算法1 void inorder( BiTree T)i Sqstack S: BiTree P=t 后序遗历二叉树的递归算法 void PostOrder Traverse( BiTree T) doi while(P) if (T)i P=P->lchild; i PostOrder Traverse(T->lchild) if(S top) PostOrder Traverse(T->rchild) S.top-, P=*(S top) printf("%c",T->data) printf("%c", P->data); P=P->rchild; i while((S top! =S base)lIP 非递归算法 中序遍历的非递归算法2 先序通历:算法1,将右子树根结点入栈,(栈所需 void inorder(BiTree 最大容量为n2+1);算法2将根结点入栈 i SqStack S: BiTree P=T; 先序遍历的非递归算法1 InitStack(S) void preorder( BiTree T) whle(P‖! Empty(S) i SqStack S; BiTree P=T, f if(P) Push(S, P) InitStack(S): Push(S, NULL); P=P->lchild; i while(P) else Pop(S, P) i printf("%c", P->data); if (P->rchild P=P->rchild; i Push(s, P->rchild) if (P->lchild) P=P->lchild else Pop(s, P)

遍历二叉树的递归算法 先序遍历二叉树的递归算法 void PreOrderTraverse(BiTree T) { if (T){ printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } 中序遍历二叉树的递归算法 void InOrderTraverse(BiTree T) { if (T) { InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild); } } 后序遍历二叉树的递归算法 void PostOrderTraverse(BiTree T) { if (T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); } } 非递归算法 先序遍历：算法 1，将右子树根结点 入栈，(栈所需 最大容量为 n/2+1)；算法 2 将根结点入栈 先序遍历的非递归算法 1 void preorder(BiTree T) { SqStack S; BiTree P=T; InitStack(S); Push(S,NULL); while (P) { printf("%c",P->data); if (P->rchild) Push(S,P->rchild); if (P->lchild) P=P->lchild; else Pop(S,P); } } 先序遍历的非递归算法 2 void preorder(BiTree T){ int top=0; BiTree stack[20], P=T; do { while (P){ printf("%c",P->data); stack[top]=P; top++; P=P->lchild; } if (top){ top--; P=stack[top]; P=P->rchild;} }while (top || P); } 中序遍历：在遍历左子树之前，先把根结点入栈， 当左子树遍历结束后，从栈中弹出，访问，再遍历 右子树 中序遍历的非递归算法 1 void inorder(BiTree T){ SqStack S; BiTree P=T; InitStack(S); do{ while(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); } 中序遍历的非递归算法 2 void inorder(BiTree T) { SqStack S; BiTree P=T; InitStack(S); while( P || !Empty(S)) { if (P) { Push(S,P); P=P->lchild; } else { Pop(S,P); printf("%c",P->data); P=P->rchild;} } }

后序非递归遍历时,每遇到一个结点,先把它推入栈中,让 Poplin=0。在遍历其左子树前,改结点的 PopTim=1,将其左孩子推入栈中。在遍历完左子树后,还不能访问该结点,必须继续遍历右子树,此时改 结点的 Poplin=2,并把其右孩子推入栈中。在遍历完右子树后,结点才退栈访问。 60161162626262 d 6 e 后序遍历的非递归算法1 void Postorder( BiTree T) i BiTree p=T,q=NULL; SqStack S; InitStack(S); Push(S, P); while( Stack Empty (s) i if(p & p!=q) Push(s, p): p=p->lchild; j else( Pop(S, p) if(StackEmpty()) if(p->rchild & p->rchild!=g) i Push(s, p); p=p->rchild; j else printf("%c",p->data); q=p i 后序遍历的非递归算法2 void postorder(BiTree T) i BiTree P=T, g, int flag, SqStack S: InitStack(s) while(P)i'(s top)=P; Stop++; P=P->lchild; while((S top!=S base)&& flag) i P=*(Stop-1); i printf("%c", P->data); S.top-, q=p; 3 else P=P->rchild; flag=0, 1 i while((S top!=S base)

后序非递归遍历时，每遇到一个结点，先把它推入栈中，让 PopTim=0。在遍历其左子树前，改结点的 PopTim=1，将其左孩子推入栈中。在遍历完左子树后，还不能访问该结点，必须继续遍历右子树，此时改 结点的 PopTim=2，并把其右孩子推入栈中。在遍历完右子树后，结点才退栈访问。 后序遍历的非递归算法 1 void Postorder(BiTree T) { BiTree p=T,q=NULL; SqStack S;InitStack(S); Push(S,p); while (!StackEmpty(S)) { if (p && p!=q) { Push(S,p); p=p->lchild; } else { Pop(S,p); if (!StackEmpty(S)) if (p->rchild && p->rchild!=q) { Push(S,p); p=p->rchild; } else {printf("%c",p->data); q=p;} } } } 后序遍历的非递归算法 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) && flag) { P=*(S.top-1); if (P->rchild == q) { printf("%c",P->data); S.top--; q=p;} else { P=P->rchild; flag=0;} } }while ((S.top!=S.base)); }

先序建立二叉树的递归算法 说明: Status Create BiTree(BiTree &T) 1)遍历的第一个和最后一个结点 i char ch; scanf("%c", &ch); 第一个结点: if(ch==)T=NULL 先序:根结点; else if((T=(BiTNode*)malloc(sizeof( BiTNode)) 中序:沿着左链走,找到一 exit(OVERFLOW); 个没有左孩子的结点; 后序:从根结点出发,沿着 Create BiTree(T->lchild); 左链走,找到一个既没有左 Create BiTree(T->rchild); 孩子又没有右孩子的结点。 最后一个结点: return OK: 中序:从根结点出发,沿着 右链走,找到一个没有右孩 二叉树的显示输出 子的结点 void Print BiTree( BiTree T, int n) 后序:根结点。 先序:从根结点出发,沿着 nti; char ch=’ 右链走,找到一个没有右孩 if()i 子的结点;如果该结点有左 Print BiTree(T->rchild, n+1) 孩子,再沿着其左孩子的右 for(i=l; idata) 个没有孩子的结点 Print BiTree(T->Child, n+1); 求中序的第一个结点的算法 遍历二叉树的应用 printf(P->data) 利用二叉树后序历计算二叉树的深度 求中序的最后一个结点的算法 int Depth( BiTree T) int depl, depr while(P->rchild)P=P->rchild if(D) Printf(P->data) depl=Depth(T->lchild) depr=Depth(T->rchild 复制二叉树 if(depl>=depr)return(depl+l) void Copy Tree(BiTree T, BiTree &Tl) else return(depr+1) f if (T) return o fT1=(BiTree)malloc(sizeof(Bi TNode)); if (T1)i printf("Overflown"); it(1);} 求二叉树结点个数 TI->data=T->data: int Size( Bi Tree T) T1->lchild=T1->rchild=NULI Copy Tree(T-lchild, T1->lchild); if(T-NULL) return 0 Copy Tree(T->rchild,Tl->rchild); else return 1 Size(T->lchild)+ Size( T->rchild);

先序建立二叉树的递归算法 Status CreateBiTree(BiTree &T) { char ch;scanf("%c",&ch); if (ch==' ') T=NULL; else { if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } 二叉树的显示输出 void 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); } } 遍历二叉树的应用 利用二叉树后序遍历计算二叉树的深度 int Depth(BiTree T){ 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; } 求二叉树结点个数 int Size(BiTree T) { if (T==NULL) return 0; else return 1 + Size (T->lchild ) + Size ( T->rchild); } 说明： 1）遍历的第一个和最后一个结点 第一个结点： ▪ 先序：根结点； ▪ 中序：沿着左链走，找到一 个没有左孩子的结点； ▪ 后序：从根结点出发，沿着 左链走，找到一个既没有左 孩子又没有右孩子的结点。 最后一个结点： ▪ 中序：从根结点出发，沿着 右链走，找到一个没有右孩 子的结点； ▪ 后序：根结点。 先序：从根结点出发，沿着 右链走，找到一个没有右孩 子的结点；如果该结点有左 孩子，再沿着其左孩子的右 链走，以此类推，直到找到 一个没有孩子的结点 求中序的第一个结点的算法： P=T; while (P->lchild) P=P->lchild; printf(P->data); 求中序的最后一个结点的算法： P=T； while(P->rchild) P=P->rchild; Printf(P->data); 复制二叉树 void CopyTree(BiTree T,BiTree &T1) { if (T) { T1=(BiTree)malloc(sizeof(BiTNode)); if (!T1) { printf("Overflow\n"); exit(1); } T1->data=T->data; T1->lchild=T1->rchild=NULL; CopyTree(T->lchild,T1->lchild); CopyTree(T->rchild,T1->rchild); } }