非递归后序遍历二叉树版本二88bf必发娱乐:

如题:

思路:

Pn(x)

标记一个结点的左右子树是否已经被访问过,叶子节点也进行标记

  • n=0的情况下为0
  • n=1的情况下为2x
  • n>1的情况下为2xPn-1(x)-2(n-1)Pn-2(x)

拓展:

思路:博主想了半天不知道咋说,但是这是一种递归思想。还请读者好好体会

遍历过程中读者会发现,某一时刻,从栈底到栈顶的元素刚好构成当前访问节点的到根节点的路径。利用这一特性可以实现两个算法:(1)根到某节点的路径(2)两个节点的最近公共祖先

func(Tree T){

typeDef struct{

//本程序需要的数据结构
struct Stack{
    int n;
    int val;
}
fv1=0, fv2=2x;
Stack s;
//保存n
for(n;n>=2;n--)
    push(S,n);
while(!IsEmpty(S)){

    s.n.val = 2xfv2-2(n-1)fv1;
    fv1=fv2;
    fv2=s.n.val;
}
if(n==0)
    return 0;
return fv2;
BiTree t;
int tag;

}

}Stack

您可能感兴趣的

void f(BiTree bt, ElemType x){

Stack s[];
top = 0;
while(bt!=null||top>0)
    while(bt!=null){
        s[++top].t = bt;
        s[top].tag = 0;
        bt=bt->lchild;
    }
//注意这里是while   不是if
while(top!=0&&s[top].tag==1)
    print(visit(s[top--]));

if(top!=0){
    s[top].tag = 1;
    bt = s[top].t->rchild;
}

}

您可能感兴趣的