| 词条 | 后序遍历 |
| 释义 | 后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和非递归算法两种。 递归算法算法描述： （1）若二叉树为空，结束 （2）后序遍历左子树 （3）后序遍历右子树 （4）访问根结点 遍历结果：DEBFCA 伪代码 PROCEDURE POSTRAV(BT) IF BT<>0 THEN { POSTRAV(L(BT)) POSTRAV(R(BT)) OUTPUT V(BT) } RETURN c语言描述 struct btnode { int d; struct btnode *lchild; struct btnode *rchild; }; void postrav(struct btnode *bt) { if(bt!=NULL) { postrav(bt->lchild); postrav(bt->rchild); printf("%d ",bt->d); } } 非递归算法算法1（c语言描述）： void postrav1(struct btnode *bt) { struct btnode *p; struct { struct btnode *pt; int tag; }st[MaxSize]; } int top=-1; top++; st[top].pt=bt; st[top].tag=1; while(top>-1) /*栈不为空*/ { if(st[top].tag==1) /*不能直接访问的情况*/ { p=st[top].pt; top--; if(p!=NULL) { top++; /*根结点*/ st[top].pt=p; st[top].tag=0; top++; /*右孩子结点*/ st[top].pt=p->p->rchild; st[top].tag=1; top++; /*左孩子结点*/ st[top].pt=p->lchild; st[top].tag=1; } } if(st[top].tag==0) /*直接访问的情况*/ { printf("%d ",st[top].pt->d); top--; } } } 算法2： void postrav2(struct btnode *bt) { struct btnode *st[MaxSize],*p; int flag,top=-1; if(bt!=NULL) { do { while(bt!=NULL) { top++; st[top]=bt; bt=bt->lchild; } p=NULL; flag=1; while(top!=-1 && flag) { bt=st[top]; if(bt->rchild==p) { printf("%d ",bt->d); top--; p=bt; } else { bt=bt->rchild; flag=0; } } }while(top!=-1) printf("\"); } } |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。