二叉树的非递归遍历:
中序遍历非递归遍历算法
非递归算法实现的基本思路:使用堆栈:
void InOrderTraversal( BinTree BT ) { BinTree T=BT; Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ while( T || !IsEmpty(S) ) { while(T) /*一直向左并将沿途结点压入堆栈*/ { Push(S,T); T = T->Left; } if(!IsEmpty(S)) { T = Pop(S); /*结点弹出堆栈*/ printf(“%5d”,T->Data); /*(访问)打印结点*/ T = T->Right; /*转向右子树*/ } } }
void InOrderTraversal( BinTree BT ) { BinTree T=BT; Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ while( T || !IsEmpty(S) ) { while(T) /*一直向左并将沿途结点压入堆栈*/ { Push(S,T); printf(“%5d”,T->Data); /*(访问)打印结点*/ T = T->Left; } if(!IsEmpty(S)) { T = Pop(S); /*结点弹出堆栈*/ T = T->Right; /*转向右子树*/ } } }
void PostOrder_NoRecurse(BinTree BT,void (*Do)(BinTree))//非递归实现后序遍历 { BinTree T = BT; Stack s = CreateStack(20); int Tag[20]; //Tag用来标记第几次遇到堆栈内的元素,本身是一个整形堆栈 while(T || !Stack_IsEmpty(s)) { while(T) //每遇到一个新元素,则到控制到此处 { Stack_Push(s,T); //放入堆栈并循环至其最左 Tag[s->size - 1] = 0; T = T->Left; } while (!T && !Stack_IsEmpty(s)) { T = Stack_Pop(s); //取出堆栈中的一个元素,并判断它的Tag if(Tag[s->size]) { (*Do)(T); //Tag != 0 说明是第三次遇见该节点,对它进行操作 T = 0; //将T设为0以触发While条件,继续循环 } else //Tag = 0 说明是第二次遇见(第一次是将Tag设为0) { if (!T->Right) (*Do)(T); //如果右儿子不存在,则直接输出 else { Stack_Push(s,T); //如果右儿子存在,则将它放回堆栈 Tag[s->size - 1]++; //并累加相应的Tag } T = T->Right; //返回右儿子。注意,如果右儿子不存在,则会触发While继续循环 } //否则会判定为遇见新元素跳出循环,继续外部外部的大While循环 } } }由两种遍历序列确定二叉树?
已知三种遍历中的任意两种遍历序列,能否唯一确定一棵二叉树呢?我们知道,无论哪一种,必须要先知道先序遍历。
比如:先序和中序遍历序列来确定一棵二叉树
〖分析〗
1根据先序遍历序列第一个结点确定根结点;
2根据根结点在中序遍历序列中分割出左右两个子序列
3对左子树和右子树分别递归使用相同的方法继续分解。
题目练习:过几天再贴上。