| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3139 人关注过本帖
标题:建立一个二叉树非递归遍历
只看楼主 加入收藏
milanchearim
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2004-11-7
收藏
 问题点数:0 回复次数:9 
建立一个二叉树非递归遍历
请各位高手帮我解决上述这个问题,能正确运行,多谢!
搜索更多相关主题的帖子: 二叉树 遍历 递归 运行 
2004-11-07 11:41
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 
...
2004-11-07 11:43
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 
其实就是把递归的方式的原理放进循环里面,递归其实就是循环的简单调用。你先试一下怎样写个循环把结点都遍历掉。
2004-11-07 11:48
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 
一个数据/头结点,两个左右结点,当。。。条件时左,。。。时右,关键在于条件,至于怎么写,自己写吧!
2004-11-07 11:49
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 
[转帖]利用栈的非递归遍历算法
  二叉树结点定义

  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; }

2004-11-13 10:14
stnlcd
Rank: 1
等 级:新手上路
帖 子:177
专家分:1
注 册:2004-11-21
收藏
得分:0 

给大家一个效率较高的后序遍历非递归算法(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); /*栈不空*/ }


要让一个男人破产,请给他一架相机,要让一个男人倾家荡产,请给他一架望远镜。
2004-11-22 14:28
yejiansnake
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2005-11-21
收藏
得分: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();//遍历
}


2005-11-21 22:43
ぺЖ楓Ж仐
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2005-11-27
收藏
得分:0 

看不懂啊

2005-11-27 19:23
kissyoufu
Rank: 1
等 级:新手上路
帖 子:32
专家分:0
注 册:2005-12-1
收藏
得分:0 



看不懂

看来我要多多努力

2005-12-01 20:44
编写蓝图
Rank: 1
等 级:新手上路
帖 子:59
专家分:0
注 册:2005-11-28
收藏
得分:0 

写的那么长,我都不能写?
连思路都没有!!!!


2005-12-03 14:25
快速回复:建立一个二叉树非递归遍历
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019426 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved