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

数据结构---树的前、中、后序遍历递归实现以及层…

2018-06-17 20:48:50来源：未知阅读 ()

树型结构是一类重要的非线性数据结构。树是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 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 LevelOrder(BinTree *t);
void LevelOrder(BinTreeNode *t);

因此先对树型结构进行初始化的实现，之后要创建一颗树，有了树型结构才可以对树进行前序、中序、后

序以及层次的遍历。

然后对所声明的方法进行实现：

#include<iostream>
#include<assert.h>
#include"Queue.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 LevelOrder(BinTree *t);
void LevelOrder(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)
    {
        cout<<t->data<<" ";
        PreOrder(t->leftChild);
        PreOrder(t->rightChild);
    }
}

void InOrder(BinTree *t)
{
    InOrder(t->root);
}
void InOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        InOrder(t->leftChild);
        cout<<t->data<<" ";
        InOrder(t->rightChild);
    }
}
void PostOrder(BinTree *t)
{
    PostOrder(t->root);
}
void PostOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        PostOrder(t->leftChild);
        PostOrder(t->rightChild);
        cout<<t->data<<" ";
    }
}

void LevelOrder(BinTree *t)
{
    LevelOrder(t->root);
}
void LevelOrder(BinTreeNode *t)
{
    Queue Q;
    InitQueue(&Q);
    if(t != NULL)
    {
        EnQueue(&Q, t);
        BinTreeNode *p;
        while(!IsEmpty(&Q))
        {
            p = GetTop(&Q);
            cout<<p->data<<" ";
            DeQueue(&Q);
            if(p->leftChild != NULL)
                EnQueue(&Q, p->leftChild);
            if(p->rightChild != NULL)
                EnQueue(&Q, p->rightChild);
        }
    }
}