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

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

新老客户大回馈,云服务器低至5折

        树型结构是一类重要的非线性数据结构。树是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);
        }
    }
}

   其中层次遍历是借助队列来完成的,其中引进队列的头文件和调用队列中的方法。而队列的实现在我之前

文章中已经实现完成了,这里就不再赘述。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:OpenCV学习笔记(一):使用opencv读取摄像头并实时显示

下一篇:Qt 的一些浅知识点