首页 > > 程序设计 > C/C++ >

数据结构---树的前、中、后序遍历非递归实现

2018-06-17 20:47:07来源：未知阅读 ()

树型结构是一类重要的非线性数据结构。树是n（n>=0）个结点的有限集。在任意一颗非空树中，有且仅

有一个特定的称为根的结点；当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,...,Tm，其中每

一个集合本身又是一棵树，并且称为根的子树。因此树的数据结构定义为：

#define ElemType char
typedef struct BinTreeNode
{
    ElemType data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
}BinTreeNode;

typedef struct BinTree
{
    BinTreeNode *root;
}BinTree;

因此对树型结构进行前序、中序、后序的遍历的非递归实现有以下方法的声明：

void PreOrder(BinTree *t);
void PreOrder(BinTreeNode *t);
void InOrder(BinTree *t);
void InOrder(BinTreeNode *t);
void PostOrder(BinTree *t);
void PostOrder(BinTreeNode *t);

然后对以上声明的方法进行实现有：

#include<iostream>
#include<assert.h>
#include"Queue.h"
#include"Stack.h"
using namespace std;

#define ElemType char
typedef struct BinTreeNode
{
    ElemType data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
}BinTreeNode;

typedef struct BinTree
{
    BinTreeNode *root;
}BinTree;

void InitBinTree(BinTree *t);
void CreateBinTree(BinTree *t);
void CreateBinTree(BinTreeNode *&t);
void PreOrder(BinTree *t);
void PreOrder(BinTreeNode *t);
void InOrder(BinTree *t);
void InOrder(BinTreeNode *t);
void PostOrder(BinTree *t);
void PostOrder(BinTreeNode *t);

void InitBinTree(BinTree *t)
{
    t->root = NULL;
}

void CreateBinTree(BinTree *t)
{
    CreateBinTree(t->root);
}
void CreateBinTree(BinTreeNode *&t)
{
    ElemType item;
    cin>>item;
    if(item == '#')
        t = NULL;
    else
    {
        t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert(t != NULL);
        t->data = item;
        CreateBinTree(t->leftChild);
        CreateBinTree(t->rightChild);
    }
}

void PreOrder(BinTree *t)
{
    PreOrder(t->root);
}
void PreOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        Stack st;
        InitStack(&st);
        PushStack(&st, t);
        BinTreeNode *p;
        while(!IsEmpty(&st))
        {
            p = GetTop(&st);
            PopStack(&st);
            cout<<p->data<<" ";
            if(p->rightChild != NULL)
                PushStack(&st,p->rightChild);
            if(p->leftChild != NULL)
                PushStack(&st, p->leftChild);
        }
    }
}

void InOrder(BinTree *t)
{
    InOrder(t->root);
}
void InOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        Stack st;
        InitStack(&st);
        PushStack(&st, t);
        BinTreeNode *p;
        while(!IsEmpty(&st))
        {
            while(t->leftChild != NULL)
            {
                t = t->leftChild;
                PushStack(&st, t);
            }
            p = GetTop(&st);
            PopStack(&st);
            cout<<p->data<<" ";
        
            if(p->rightChild != NULL)
            {
                t = p->rightChild;
                PushStack(&st, t);
            }
        }
    }
}

void PostOrder(BinTree *t)
{
    PostOrder(t->root);
}
void PostOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        Stack st;
        InitStack(&st);
        StkNode sn;
        do
        {
            while(t != NULL)
            {
                sn.ptr = t;
                sn.tag = L;
                PushStack(&st, sn);
                t = t->leftChild;
            }
            bool flag = true;
            while(flag && !IsEmpty(&st))
            {
                sn = GetTop(&st);
                PopStack(&st);
                switch(sn.tag)
                {
                case L:
                    sn.tag = R;
                    PushStack(&st,sn);
                    flag = false;
                    t = sn.ptr->rightChild;
                    break;
                case R:
                    cout<<sn.ptr->data<<" ";
                    break;
                }
            }
        }while(!IsEmpty(&st));
    }
}