用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c++代码库

数据结构实验3---二叉树的遍历（递归、非递归）

2013-02-21 作者： shiqiang举报

[c++]代码库

view sourceprint?
#include<iostream>
#include<fstream>
#include<string>
#include<string.h>
#include<stdlib.h>
#define Status int
#define OK 1
#define OVERFLOW 0
#define ERROR 0
#define STACK_INIT_SIZE 10
using namespace std;
 
typedef struct BiTNode{//定义二叉树的结点类型；结构体。
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
 
typedef struct{//定义线性栈；用于辅助实现二叉树的非递归先序、中序遍历。
    BiTree *base;
    BiTree *top;
    int stacksize;
}SqStack;
 
typedef struct QNode{//对列的结点类型；结构体。
    BiTree data;
    struct QNode *next;
}QNode, *QueuePtr;
 
typedef struct{//定义队列类型；链式队列；结构体。
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
 
 
BiTree createBiTree(char * &q){//创建二叉链树函数；先序递归算法。
    //对于递归，数组中的值要依次改变
    //只能是传“指针的引用”，或者是指
    //针的指针，但是也可以用c库函数中的一个用于从文件中逐个的读入的函数fgetc实现
    if(*q == '#')
        return NULL;
    BiTree p = new BiTNode;
    p->data = *q;
    q++;
    p->lchild = createBiTree(q);
    q++;
    p->rchild = createBiTree(q);
    return p;
    return NULL;   
}
 
void visit(BiTree bt){//访问结点的函数（结点操作函数）。
    if(bt)
        cout<<bt->data<<endl;
}
 
bool preTraverse(BiTree bt){//二叉树的先序遍历函数；递归算法。
    visit(bt);
    if(bt){
        if(bt->lchild)
            preTraverse(bt->lchild);
        if(bt->rchild)
            preTraverse(bt->rchild);
    }
    return true;
}
 
bool inTraverse(BiTree bt){//二叉树的中序遍历函数；递归算法。
    if(bt){
        if(bt->lchild)
            inTraverse(bt->lchild);
        visit(bt);
        if(bt->rchild)
            inTraverse(bt->rchild);
    }
    return true;
}
//11-29
bool PostTraverse(BiTree bt){//二叉树的后序遍历函数；递归算法。
    if(bt){
        if(bt->lchild)
            PostTraverse(bt->lchild);
        if(bt->rchild)
            PostTraverse(bt->rchild);
        visit(bt);
    }
    return true;
}
 
Status InitStack(SqStack &s){//初始化栈函数。
    s.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));
    if(!s.base)
        exit(OVERFLOW);
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
    return OK;
}
 
Status push(SqStack &s, BiTree &e){//入栈函数。
    if(s.top - s.base >= s.stacksize){
        s.base = (BiTree *)realloc(s.base,
            (s.stacksize + STACK_INIT_SIZE) * sizeof(BiTree));
        if(!s.base)
            exit(OVERFLOW);
        s.top = s.base + s.stacksize;
        s.stacksize += STACK_INIT_SIZE;
    }
    *s.top++ = e;
    return OK;
}
 
Status pop(SqStack &s, BiTree &e){//出栈函数。
    if(s.top == s.base)
        return ERROR;
    e = * --s.top;
    return OK;
}
 
Status emptystack(SqStack s){//判定栈空的函数。
    if(s.base == s.top)
        return OK;
    else
        return ERROR;
}
 
void preordertravese(BiTree bt){//二叉树的先序遍历函数；非递归算法；栈数据结构。
    BiTree p = bt;
    SqStack s;
    InitStack(s);
    while(p||!emptystack(s)){
        if(p){
            visit(p);
            push(s,p);
            p = p->lchild;
        }else{
            pop(s,p);
            p = p->rchild;
        }
    }
}
 
//-----------------------------
void inordertravese(BiTree bt){//二叉树的中序遍历函数；非递归算法；栈数据结构。
    BiTree p = bt;
    SqStack s;
    InitStack(s);
    while(p||!emptystack(s)){
        if(p){ 
            push(s,p);
            p = p->lchild;
        }else{
            pop(s,p);
            visit(p);
            p = p->rchild;
        }
    }
}
 
//---------------------
Status QueueEmpty(LinkQueue &q){//判定对空函数。
    if(q.front == q.rear)
        return OK;
    else
        return ERROR;
}
 
Status InitQueue(LinkQueue &q){//队列初始化函数。
    q.front = q.rear = (QueuePtr) malloc (sizeof(QNode));
    if(!q.front)
        exit(OVERFLOW);
    q.front->next = NULL;
    return OK;
}
 
Status EnQueue(LinkQueue &q, BiTree e){//入队函数。
    QueuePtr p = (QueuePtr) malloc (sizeof(QNode));
    if(!p)
        exit(OVERFLOW);
    p->data = e;
    p->next = NULL;
    q.rear->next = p;
    q.rear = p;
    return OK;
}
 
Status DeQueue(LinkQueue &q, BiTree &e){//出对函数。
    QueuePtr p;
    if(q.front == q.rear)
        return ERROR;
    p = q.front->next;
    e = p->data;
    q.front->next = p->next;
    if(q.rear == p)
        q.rear = q.front;
    free(p);
    return OK;
}
 
void LevelOrderTraverse(BiTree T) //二叉树的存续遍历函数；非递归算法；队列数据结构。
{
    /* 采用二叉链表存储结构，visit是对数据元素操作的应用函数。*/
    /* 层序遍历二叉树T算法(利用队列)，对每个数据元素调用函数visit */
    LinkQueue q;
    BiTree p;
    if(T)
    {
        InitQueue(q);
        EnQueue(q,T);
        while(!QueueEmpty(q))
        {
            DeQueue(q,p);
            visit(p);
            if(p->lchild!=NULL) EnQueue(q,p->lchild);
            if(p->rchild!=NULL) EnQueue(q,p->rchild);
        }
    }
}
//11-29
 
int main(){//主函数；从文件“xianxu.txt”读取先序字符串序列（以扩展二叉树方式表示）
    //用于创建二叉树，'#'为空结点标记；依次调用各种遍历函数实现二叉树的各种遍历。
    ifstream in("xianxu.txt");
    char a[40];
    string t;
    getline(in, t);
    strcpy_s(a, t.c_str());
    char *p = a;
    BiTree bt = createBiTree(p);
    cout<<"二叉树的先序遍历递归实现:"<<endl;
    preTraverse(bt);
    cout<<endl;
    cout<<"二叉树的中序遍历递归实现:"<<endl;
    inTraverse(bt);
    cout<<endl;
    cout<<"二叉树的后续遍历递归实现:"<<endl;
    PostTraverse(bt);
    cout<<endl;
    cout<<"二叉树的先序遍历非递归实现:"<<endl;
    preordertravese(bt);
    cout<<endl;
    cout<<"二叉树的中序遍历非递归实现:"<<endl;
    inordertravese(bt);
    cout<<endl;
    cout<<"二叉树的层序遍历非递归实现:"<<endl;
    LevelOrderTraverse(bt);
    cout<<endl;
    in.close();
    return 0;
}
 
 
 
3.后序遍历非递归算法
    typedef enum{L,R} tagtype;
typedef struct
{
    Bitree ptr;
    tagtype tag;
}stacknode;
 
typedef struct
{
    stacknode Elem[maxsize];
    int top;
}SqStack;
 
void PostOrderUnrec(Bitree t)
{
    SqStack s;
    stacknode x;
    StackInit(s);
    p=t;
 
    do
    {
        while (p!=null)        //遍历左子树
        {
            x.ptr = p;
            x.tag = L;       //标记为左子树
            push(s,x);
            p=p->lchild;
        }
 
        while (!StackEmpty(s) && s.Elem[s.top].tag==R) 
        {
            x = pop(s);
            p = x.ptr;
            visit(p->data); //tag为R，表示右子树访问完毕，故访问根结点   
        }
 
        if (!StackEmpty(s))
        {
            s.Elem[s.top].tag =R;     //遍历右子树
            p=s.Elem[s.top].ptr->rchild;      
        }
    }while (!StackEmpty(s));
}//PostOrderUnrec


网友评论    (发表评论)


发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...