遍历二叉树的递归算法 先序遍历的非递归算法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;} } }