数据结构之 二叉树

头文件 BTree.h

#ifndef BTREE_H
#define BTREE_H
#include <iostream>
#include <queue>
using namespace std;

template<class T>                                     //树节点类
class BNode
{
public:
    BNode<T>():left(NULL),right(NULL),data(T()){}
    BNode<T> *left;
    BNode<T> *right;
    T data;
};


template<class T>                                     //二叉树类
class BTree
{
public:
    BNode<T> *root;
    BTree<T>():root(NULL){}
    ~BTree<T>()
    {
        DestoryBTree(root);
    }
    void CreateBTree(BNode<T>* &mBTree);              //构造二叉树
    void PreorderDisplay(BNode<T>* &mBTree);          //前序遍历
    void InorderDisplay(BNode<T>* &mBTree);           //中序遍历
    void PostorderDisplay(BNode<T>* &mBTree);         //后序遍历
    void LevelorderDisplay(BNode<T>* &mBTree);        //层次遍历
    void DestoryBTree(BNode<T>* &mBTree);             //毁灭二叉树
};

template<class T>
void BTree<T>::CreateBTree(BNode<T> *&mBTree)
{
    BNode<T> *tmpNode=new BNode<T>();
    cout<<"Input:\t";
    cin>>tmpNode->data;

    if(tmpNode->data=="#")
    {
        delete tmpNode;
        mBTree=NULL;
        return;
    }
    mBTree=tmpNode;
    CreateBTree(mBTree->left);
    CreateBTree(mBTree->right);
}

template<class T>
void BTree<T>::PreorderDisplay(BNode<T> *&mBTree)     //前序遍历
{
    if(mBTree)
    {
        cout<<mBTree->data<<" ";
        PreorderDisplay(mBTree->left);
        PreorderDisplay(mBTree->right);
    }
}

template<class T>
void BTree<T>::InorderDisplay(BNode<T> *&mBTree)      //中序遍历
{
    if(mBTree)
    {
        InorderDisplay(mBTree->left);
        cout<<mBTree->data<<" ";
        InorderDisplay(mBTree->right);
    }
}

template<class T>
void BTree<T>::PostorderDisplay(BNode<T> *&mBTree)    //后序遍历
{
    if(mBTree)
    {
        PostorderDisplay(mBTree->left);
        PostorderDisplay(mBTree->right);
        cout<<mBTree->data<<" ";
    }
}

template<class T>
void BTree<T>::LevelorderDisplay(BNode<T> *&mBTree)   //层次遍历
{
    if(mBTree)
    {
        BNode<T> *p=NULL;
        queue<BNode<T> *>BNodeQueue;
        BNodeQueue.push(mBTree);
        while(!BNodeQueue.empty())
        {
            p=BNodeQueue.front();
            cout<<p->data<<" ";
            BNodeQueue.pop();
            if(p->left)
                BNodeQueue.push(p->left);
            if(p->right)
                BNodeQueue.push(p->right);
        }
    }
}

template<class T>
void BTree<T>::DestoryBTree(BNode<T> *&mBTree)        //毁灭二叉树
{
    if(mBTree)
    {
        DestoryBTree(mBTree->left);
        DestoryBTree(mBTree->right);
        delete mBTree;
    }

}

#endif // BTREE_H

主函数 main.cpp

#include <iostream>
#include "BTree.h"
using namespace std;

int main()
{
    cout<<"Create A BinaryTree Now :"<<endl;
    BTree<string> mBTree;
    mBTree.CreateBTree(mBTree.root);

    cout<<endl<<"PreorderDisplay"<<endl;
    mBTree.PreorderDisplay(mBTree.root);

    cout<<endl<<"InorderDisplay"<<endl;
    mBTree.InorderDisplay(mBTree.root);

    cout<<endl<<"PostorderDisplay"<<endl;
    mBTree.PostorderDisplay(mBTree.root);

    cout<<endl<<"LevelorderDisplay"<<endl;
    mBTree.LevelorderDisplay(mBTree.root);

    return 0;
}

结果

持续更新。

转载请注明出处！