| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 998 人关注过本帖
标题:二叉树的非递归遍历,中序遍历有些代码看不懂。
只看楼主 加入收藏
apigboy
Rank: 1
等 级:新手上路
帖 子:35
专家分:4
注 册:2011-10-3
结帖率:85.71%
收藏
已结贴  问题点数:20 回复次数:2 
二叉树的非递归遍历,中序遍历有些代码看不懂。
程序代码:
#include "stdio.h"
#include "iostream.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 100
typedef int Status;
typedef int Elemtype;

typedef struct BiNode
{
    Elemtype data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

typedef struct 
{
    BiNode *a[MAXSIZE];
    int top;
}SqStack;
Status TreeCreated=FALSE;

Status CreateBiTree(BiTree *T);
void NRlnOrderTraverse(BiTree T);
void Push(SqStack *s,BiNode *x);
BiNode *Pop(SqStack *s);

void main()
{
    int choice=0,flag;
    Status leave=FALSE;
    BiNode *BT;
    cout<<"========利用栈实现非递归遍历演示程序========"<<endl;
    do {
        cout<<"1.创建一个二叉树,按先序遍历结果输入,空用0表示"<<endl;
        cout<<"2.中序遍历二叉树,非递归方式遍历二叉树"<<endl;
        cout<<"0.Quit"<<endl;
        cout<<"------Input your selection:";
        cin>>choice;
        switch(choice)
        {
        case 1:
            if (TreeCreated)
            {
                cout<<"Sorry,the tree has been already created!"<<endl;
                break;
            }
            cout<<"Please put in number!"<<endl;
            flag=CreateBiTree(&BT);
            if (flag==OK) 
            {
                cout<<"Okey,Now a TREE named BT is created..."<<endl;
                TreeCreated=TRUE;
            }
            break;
        case 2:
            cout<<"In NROrder:";
            NRlnOrderTraverse(BT);
            cout<<endl;
            break;
        case 0:
            leave=TRUE;
            break;
        }
    } while(!leave);
    cout<<"Thanks for using,bye-bye!"<<endl;
}

Status CreateBiTree(BiTree *T)
{
    int ch=0;
    cin>>ch;
    if (ch==0)
        (*T)=NULL;
    else
    {
        (*T)=(BiTree)malloc(sizeof(BiNode));
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    return OK;
}

void NRlnOrderTraverse(BiTree T)
{
    SqStack s;
    BiNode *p;
    s.top=0;
    Push(&s,T);
    while (s.top!=0)
    {
        while (s.a[s.top]!=NULL)
        {
            p=s.a[s.top];
            Push(&s,p->lchild);
        }
        p=Pop(&s);
        if(s.top!=0)
        {
            p=Pop(&s);
            cout<<p->data<<"   ";
            Push(&s,p->rchild);
        }
    }
    cout<<endl;
}    
void Push(SqStack *s,BiNode *x)
{
    if (s->top==MAXSIZE) 
        cout<<"stack overflow!"<<endl;
    else
    {
        s->top++;
        s->a[s->top]=x;
    }
}
BiNode *Pop(SqStack *s)
{
    BiNode *x;
    if (s->top==0)
    {
        cout<<"stack underflow!"<<endl;
        return (NULL);
    }
    else
    {
        x=s->a[s->top];
        s->top--;
        return (x);
    }
}

其中这段代码
void NRlnOrderTraverse(BiTree T)
{
    SqStack s;
    BiNode *p;
    s.top=0;
    Push(&s,T);
    while (s.top!=0)
    {
        while (s.a[s.top]!=NULL)
        {
            p=s.a[s.top];
            Push(&s,p->lchild);
        }
        p=Pop(&s);
        if(s.top!=0)
        {
            p=Pop(&s);
            cout<<p->data<<"   ";
            Push(&s,p->rchild);
        }
    }
    cout<<endl;
}   
不是很懂,求解释啊~~
搜索更多相关主题的帖子: 二叉树 
2011-10-31 21:55
zqllsszhuqi
Rank: 2
等 级:论坛游民
帖 子:26
专家分:45
注 册:2010-3-29
收藏
得分:10 
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType))
 { // 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。算法6.3
   // 中序遍历二叉树T的非递归算法(利用栈),对每个数据元素调用函数Visit
   SqStack S;
   InitStack(S);
   while(T||!StackEmpty(S))
   {
     if(T)
     { // 根指针进栈,遍历左子树
       Push(S,T);
       T=T->lchild;
     }
     else
     { // 根指针退栈,访问根结点,遍历右子树
       Pop(S,T);
       if(!Visit(T->data))
         return ERROR;
       T=T->rchild;
     }
   }
   printf("\n");
   return OK;
 }
里面的栈队代码自己写吧,或者直接利用系统的栈函数,泛型编程看看。。。。
2011-11-01 09:15
小鱼儿c
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:852
专家分:1317
注 册:2011-4-1
收藏
得分:10 
回复 楼主 apigboy
中跟遍历还是好一点。。
后跟有点麻烦。。。。

因为你完全可以用栈按递归中跟遍历的过程出搞。。
方式是一模一样,只要你懂了递归的思想了
这样循环知道遍历完。。。。。。。、
自己用几个数据演示一遍更好理解,这就是我前几天学习后跟遍历的方法。。。

学习数据结构的孩子加油

[ 本帖最后由 小鱼儿c 于 2011-11-1 11:08 编辑 ]

用心做一件事情就这么简单
2011-11-01 11:05
快速回复:二叉树的非递归遍历,中序遍历有些代码看不懂。
数据加载中...
 
   



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

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