typedef struct BitreeNode { TreeDataType data; struct BitreeNode * leftChild, * rightChild; } BitreeNode, * Bitree;
(1)传统方法:利用栈的前序(中序)遍历非递归算法
Template<class Type>void BinaryTree<Type>:: PreOrInOrder(){ stack<TreeNode<Type>*>st; BinTreeNode<Type>*p=root; do { while (p!=NULL) { Cout<<current->data //前序遍历使用 st.Push(p); p=p->leftChild; } if (!st.IsEmpty()) //栈不空时退栈 { p=st.getTop();st.Pop(); Cout<<current->data //中序遍历使用词句 p=p->rightChild; } }while (p!=NULL||!st.IsEmpth()); } (2)传统方法:利用栈的后序遍历非递归算法
后序遍历时使用的栈的结点定义 template<class Type> struct StkNode { enum tag{ L, R }; BinTreeNode * ptr; stkNode(BinTreeNode<Type>*N=NULL):ptr(N),tag(L){} //构造函数 }
后序遍历根为 T 的二叉树, 存储结构为二叉链表,S是存储所经过二叉树结点的工作栈。其中, tag是结点标记。当tag=L时, 表示刚才是在左子树//中, 从左子树退出时, 还要去遍历右子树。当tag=R时, 表示刚才是在右子树中,在从右子树中退出时, 去访问位于栈顶的结点。
Template<class Type>void BinaryTree<Type> ::PostOrderTraverse(){ stack<stkNode<Type>>st;stkNode<Type>w; BinTreeNode<Type>*p=root; do { while(p!=NULL) { w.ptr=p;w.tag=L;Push(w); p=p->leftChild; } int continue=1; while (continue && !st.IsEmpth()) { w=st.getTop();st.Pop(); p=w.ptr; switch(w.tag) { case L:w.tag=R;st.push(w); continue=0; p=p->rightChild; break; case R:cout<<p->data<<endl; break } } }while(p!=NULL||!st.IsEmpty()); cout<<endl; }
给大家一个效率较高的后序遍历非递归算法(c语言编写,本算法不需要改变二叉树的结点结构):
typedef struct node { /*二叉树的结点存储类型为链式*/ char data; struct node *lchild,*rchild; }node,*btree;
void backordertraverse(btree t) { /*用栈标记法(本人喜欢这样叫)*/ btree* stack[max_size]; int tag[max_size],top=0; do { while(t) { /*由于非地址调用,所以不会改变数根t*/ top++; stack[top]=t; tag[top]=0; t=t->lchild; } if(top>0) { /*栈不空,为了简洁下面采用了逗号表达式*/ if(tag[top]==1) printf("%c ",stack[top].data),top--; else t=stack[top],t=t->rchild,tag[top]=1; } }while(top>0); /*栈不空*/ }
这个~~~我只写出了个非递归中序的遍历。。。。。后序我还写不出。。。。前序就很简单了。。。
#include<iostream.h>
class list
{
public:
int i;
list *l1; //左
list *l2; //右
list(int );
static void create(list *&); //建立二叉树表
static void f1(list *);//前序
static void f2(list *);//中序
static void f3(list *);//后序
static void f4(list *);//层次遍历
static void bianli();//遍历
static void inorder(list *);//非递归中序
protected:
static list *head;
};
list *list::head=NULL;
list::list(int a)
{
i=a;
}
void list::create(list *&t)
{
int a;
list *ps;
cout<<"请输入一个数字但是要大于0,如果要把孩子节点置为空请输入0: ";
cin>>a;
if(a==0) t=NULL;
else
{
ps=new list(a); //生成根节点
t=ps;
create(t->l1);//构造左子树
create(t->l2);//构造右子树
}
}
/* list *ps;
list *pend;
ps=new list(1);
head=ps;
pend=ps;
ps=new list(2);
pend->l1=ps;
ps=new list(4);
pend->l1->l1=ps;
pend->l1->l1->l1=NULL;
pend->l1->l1->l2=NULL;
ps=new list(5);
pend->l1->l2=ps;
ps=new list(8);
pend->l1->l2->l1=ps;
pend->l1->l2->l1->l1=NULL;
pend->l1->l2->l1->l2=NULL;
ps=new list(9);
pend->l1->l2->l2=ps;
ps=new list(10);
pend->l1->l2->l2->l1=ps;
pend->l1->l2->l2->l1->l1=NULL;
pend->l1->l2->l2->l1->l2=NULL;
ps=new list(11);
pend->l1->l2->l2->l2=ps;
pend->l1->l2->l2->l2->l1=NULL;
pend->l1->l2->l2->l2->l2=NULL;
ps=new list(3);
pend->l2=ps;
ps=new list(6);
pend->l2->l1=ps;
pend->l2->l1->l1=NULL;
pend->l2->l1->l2=NULL;
ps=new list(7);
pend->l2->l2=ps;
pend->l2->l2->l1=NULL;
pend->l2->l2->l2=NULL;
*/
void list::f1(list *t)//前序
{
if(t)
{
cout<<t->i<<" ";
f1(t->l1);
f1(t->l2);
}
}
void list::f2(list *t)//中序
{
if(t)
{
f2(t->l1);
cout<<t->i<<" ";
f2(t->l2);
}
}
void list::f3(list *t)//后序
{
if(t)
{
f3(t->l1);
f3(t->l2);
cout<<t->i<<" ";
}
}
void list::f4(list *t)//层次遍历
{
list *b=t;
list *a[40];
int ta=0;
int tb=0;
if(b!=NULL)
{
a[ta]=b;
tb++;
while(ta<tb)
{
if(a[ta]->l1!=NULL)
{
a[tb]=a[ta]->l1;
tb++;
}
if(a[ta]->l2!=NULL)
{
a[tb]=a[ta]->l2;
tb++;
}
ta++;
}
for(int i=0;i<tb;i++)
{
cout<<a[i]->i<<" ";
}
}
else cout<<"空树"<<endl;
}
void list::inorder(list *t)//非递归中序
{
list *a[20];
int ta=0,tb=0;
list *b=t;
if(b!=NULL)
{
a[ta]=b;
tb++;
while(a[ta]!=NULL)
{
while(a[ta]->l1!=NULL) //左
{
a[tb]=a[ta]->l1;
tb++;
ta=tb-1;
}
while(a[ta]->l2==NULL) //右
{
cout<<a[ta]->i<<" ";
a[ta]=NULL;
ta--;
if(ta<0)
{
break;
}
tb--;
}
if(ta<0) break;
if(a[ta]->l2!=NULL)
{
cout<<a[ta]->i<<" ";
a[ta]=a[ta]->l2;
}
}
}
cout<<endl;
}
void list::bianli()//遍历
{
list *t=head;
cout<<"请按前序遍历方式输入。"<<endl<<endl;
list::create(t);
int a;
cout<<"1.前序; 2.中序; 3.后序; 4.层次; 5.非递归中序; 6退出"<<endl;
cout<<"请选择选项: ";
cin>>a;
while(a!=6) //按钮
{
if(a==1)
{
list::f1(t);
cout<<endl;
}
if(a==2)
{
list::f2(t);
cout<<endl;
}
if(a==3)
{
list::f3(t);
cout<<endl;
}
if(a==4)
{
list::f4(t);
cout<<endl;
}
if(a==5)
{
list::inorder(t);
}
cout<<endl;
cout<<"1.前序; 2.中序; 3.后序; 4.层次; 5.非递归中序; 6退出"<<endl;
cout<<"请选择选项: ";
cin>>a;
}
}
void main()
{
list::bianli();//遍历
}