二叉樹之方法實(shí)現(xiàn)

發(fā)布時(shí)間：2020-06-30 14:19:59 來源：網(wǎng)絡(luò) 閱讀：420 作者：匯天下豪杰欄目：編程語言

1、二叉樹上的操作

均是C++實(shí)現(xiàn)先根序創(chuàng)建二叉樹及其其它方法

我認(rèn)為在二叉樹的創(chuàng)建方法和遍歷以外，以下方法值得我們關(guān)注：

public:
    int size()const;  //求結(jié)點(diǎn)個(gè)數(shù)
    int height()const;  //求樹的高度
    BinTreeNode<Type>* root_1()const; //求根節(jié)點(diǎn)
    BinTreeNode<Type>* leftChild(BinTreeNode<Type>* cur)const;  //求當(dāng)前結(jié)點(diǎn)的左孩子
    BinTreeNode<Type>* rightChild(BinTreeNode<Type>* cur)const; //求當(dāng)前結(jié)點(diǎn)的右孩子
    BinTreeNode<Type>* find(const Type &key)const;              //查找當(dāng)前結(jié)點(diǎn)
    BinTreeNode<Type>* parent(BinTreeNode<Type>* cur)const;     //查找當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)
    void makeEmpty();                                           //將二叉樹置空
    bool equal(const BinTree<Type> &t)const;                    //兩個(gè)二叉樹是否相同的比較
    BinTreeNode<Type>* copy(BinTreeNode<Type> *t)const;         //拷貝構(gòu)造函數(shù)的方法，復(fù)制一個(gè)二叉樹

2、方法一一實(shí)現(xiàn)：

(1)、求結(jié)點(diǎn)個(gè)數(shù)

template<typename Type>
int BinTree<Type>::size(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return 0;
    }

    return size(t->leftChild) + size(t->rightChild) + 1;
}

(2)、求樹的高度

template<typename Type>
int BinTree<Type>::height(BinTreeNode<Type> *t)const{
    if(t == NULL){
        return 0;
    }
    int leftHeight = height(t->leftChild);
    int rightHeight = height(t->rightChild);

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

(3)、查找當(dāng)前結(jié)點(diǎn)

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::find(const Type &key, BinTreeNode<Type> *t)const{
    if(t == NULL){
        return NULL;
    }
    if(t->data == key){
        return t;
    }

    BinTreeNode<Type> *p = find(key, t->leftChild);
    if(p != NULL){
        return p;
    }

    return find(key, t->rightChild);
}

(4)、查找當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::parent(BinTreeNode<Type>* cur, BinTreeNode<Type> *t)const{
    if(t == NULL || cur == NULL || cur == t){
        return NULL;
    }
    if(t->leftChild == cur || t->rightChild == cur){
        return t;
    }        //思路：利用父的孩子節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)比較
    BinTreeNode<Type> *p = parent(cur, t->leftChild);
    if(p != NULL){
        return p;
    }

    return parent(cur, t->rightChild);
}

(5)、將二叉樹置空

template<typename Type>
void BinTree<Type>::makeEmpty(BinTreeNode<Type> *t){
    if(t != NULL){
        makeEmpty(t->leftChild);
        makeEmpty(t->rightChild);
        delete t;
    }
}

(6)、兩個(gè)二叉樹是否相同的比較

template<typename Type>
bool BinTree<Type>::equal(BinTreeNode<Type> *t, BinTreeNode<Type> *t1)const{
    if(t == NULL && t1 == NULL){  //取反判斷與這個(gè)是一個(gè)道理
        return true;
    }
    if(t != NULL && t1!= NULL && t->data == t1->data && equal(t->leftChild, t1->leftChild)
        && equal(t->rightChild, t1->rightChild)){
        return true;
    }else{

        return false;
    }
}

(7)、拷貝一個(gè)二叉樹

template<typename Type>
BinTreeNode<Type>* BinTree<Type>::copy(BinTreeNode<Type> *t)const{
    BinTreeNode<Type>* tmp;

    if(t == NULL){
        return NULL;
    }else{
        tmp = new BinTreeNode<Type>(t->data);
        tmp->leftChild = copy(t->leftChild);
        tmp->rightChild = copy(t->rightChild);
    }

    return tmp;
}

以上的這些方法都是利用二叉樹的性質(zhì)遞歸實(shí)現(xiàn)，比較好想清楚，就不做解釋了，實(shí)在有問題，畫畫圖就會(huì)好很多。

3、二叉樹的所有方法，測(cè)試，及測(cè)試結(jié)果如下：

(1)、所有關(guān)于二叉樹的代碼：

#ifndef _BIN_TREE_H_
#define _BIN_TREE_H_

#include<iostream>
#include<stack>  //非遞歸遍歷引入棧
#include<queue>  //層次遍歷引入隊(duì)列
using namespace std;

template<typename Type> //為的是聲明友元類，調(diào)用BinTreeNode<Type>的私有數(shù)據(jù)
class BinTree;

template<typename Type>  //BinTreeNode類
class BinTreeNode{   
    friend class BinTree<Type>;
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}
    BinTreeNode(Type value, BinTreeNode<Type> *left = NULL, BinTreeNode<Type> *right = NULL) :
    data(value), leftChild(left), rightChild(right){}
    ~BinTreeNode(){}
private:
    Type data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
};
///////////////////////////////////////////////////////////////////////////////
template<typename Type>   //BinTree類
class BinTree{
public:
    BinTree() : root(NULL){}
    BinTree(Type ref) : root(NULL), refval(ref){}
    BinTree(const BinTree &t){
        root = copy(t.root);  //調(diào)用拷貝方法
    }
    ~BinTree(){
        makeEmpty();  //析構(gòu)函數(shù)這里將二叉樹置空
        root = NULL;    
    }
public:                 //創(chuàng)建二叉樹
    void createBinTree();
    void createBinTree(const char *str);
    void createBinTree(const char *VLR, const char *LVR, int n);
    void createBinTree_1(const char *LVR, const char *LRV, int n);
public:                //遞歸遍歷
    void prevOrder()const;
    void inOrder()const;
    void endOrder()const;
public:               //各種方法的聲明
    int size()const;
    int height()const;
    BinTreeNode<Type>* root_1()const; //以下的三個(gè)方法比較簡(jiǎn)單，就不在進(jìn)行調(diào)用保護(hù)方法了；
    BinTreeNode<Type>* leftChild(BinTreeNode<Type>* cur)const;
    BinTreeNode<Type>* rightChild(BinTreeNode<Type>* cur)const;
    BinTreeNode<Type>* find(const Type &key)const;
    BinTreeNode<Type>* parent(BinTreeNode<Type>* cur)const;
    void makeEmpty();
    bool equal(const BinTree<Type> &t)const;
    BinTreeNode<Type>* copy(BinTreeNode<Type> *t)const;
public:              //非遞歸遍歷
    void prevOrder_1()const;
    void inOrder_1()const;
    void endOrder_1()const;
    void levelOrder()const; //puublic:供外界提供的接口，
////////////////////////////////////////////////////////////////////////////////
protected:                 //protected:供自己函數(shù)內(nèi)部調(diào)用，寫保護(hù)方法
    void prevOrder_1(BinTreeNode<Type>* t)const;
    void inOrder_1(BinTreeNode<Type>* t)const;
    void endOrder_1(BinTreeNode<Type>* t)const;
    void levelOrder(BinTreeNode<Type>* t)const;
protected:
    int size(BinTreeNode<Type> *t)const;
    int height(BinTreeNode<Type> *t)const;
    BinTreeNode<Type>* find(const Type &key, BinTreeNode<Type> *t)const;
    BinTreeNode<Type>* parent(BinTreeNode<Type>* cur, BinTreeNode<Type> *t)const;
    void makeEmpty(BinTreeNode<Type>* t);
    bool equal(BinTreeNode<Type> *t, BinTreeNode<Type> *t1)const;
protected:
    void prevOrder(BinTreeNode<Type> *t)const;
    void inOrder(BinTreeNode<Type> *t)const;
    void endOrder(BinTreeNode<Type> *t)const;
protected :
    void createBinTree(BinTreeNode<Type> *&t);
    BinTreeNode<Type>* createBinTree_1();
    void createBinTree(const char *&str, BinTreeNode<Type> *&t);
    BinTreeNode<Type>* createBinTree_1(const char *&str);
    void createBinTree(BinTreeNode<Type> *&t, const char *VLR, const char *LVR, int n);
    void createBinTree_1(BinTreeNode<Type> *&t, const char *LVR, const char *LRV, int n);
                         //以上都只是在類內(nèi)聲明；
private:
    BinTreeNode<Type> *root;
    Type               refval;  //'#'
};
///////////////////////////////////////////////////////////////////////////////
template<typename Type>  //類外實(shí)現(xiàn)公有方法的調(diào)用
void BinTree<Type>::createBinTree(){  //創(chuàng)建二叉樹
    //createBinTree(root);
    root = createBinTree_1();
}
template<typename Type>
void BinTree<Type>::prevOrder()const{ //先序遞歸遍歷
    cout<<"先根序如下: "<<endl;
    prevOrder(root);
}
template<typename Type>
void BinTree<Type>::inOrder()const{ //中序遞歸遍歷
    cout<<"中根序如下: "<<endl;
    inOrder(root);
}
template<typename Type>
void BinTree<Type>::endOrder()const{  //后序遞歸遍歷
    cout<<"后根序如下: "<<endl;
    endOrder(root);
}

template<typename Type>
void BinTree<Type>::createBinTree(const char *str){ //創(chuàng)建二叉樹
//    createBinTree(str, root);
    root = createBinTree_1(str);
}
template<typename Type>
int BinTree<Type>::size()const{  //求結(jié)點(diǎn)個(gè)數(shù)
    return size(root);
}
template<typename Type>
int BinTree<Type>::height()const{ //求樹的高度
    return height(root);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::root_1()const{ //求根節(jié)點(diǎn)
    return root;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::leftChild(BinTreeNode<Type>* cur)const{ //求當(dāng)前結(jié)點(diǎn)的左孩子
    return cur->leftChild;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::rightChild(BinTreeNode<Type>* cur)const{  //求當(dāng)前結(jié)點(diǎn)的右孩子
    return cur->rightChild;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::find(const Type &key)const{  //查找當(dāng)前結(jié)點(diǎn)
    return find(key, root);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::parent(BinTreeNode<Type>* cur)const{ //查找當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)
    return parent(cur, root);
}
template<typename Type>
void BinTree<Type>::makeEmpty(){ //將二叉樹置空
    makeEmpty(root);
}
template<typename Type>
bool BinTree<Type>::equal(const BinTree<Type> &t)const{ //兩個(gè)二叉樹是否相同的比較
    return equal(t.root, root);
}
template<typename Type>
void BinTree<Type>::prevOrder_1()const{  //非遞歸先序
    prevOrder_1(root);
}
template<typename Type>
void BinTree<Type>::inOrder_1()const{   //非遞歸中序
    inOrder_1(root);
}
template<typename Type>
void BinTree<Type>::endOrder_1()const{   //非遞歸后序
    endOrder(root);
}
template<typename Type>
void BinTree<Type>::levelOrder()const{   //層次遍歷
    levelOrder(root);
}
template<typename Type>
void BinTree<Type>::createBinTree(const char *VLR, const char *LVR, int n){ //創(chuàng)建二叉樹
    createBinTree(root, VLR, LVR, n);
}
template<typename Type> 
void BinTree<Type>::createBinTree_1(const char *LVR, const char *LRV, int n){ //創(chuàng)建二叉樹
    createBinTree_1(root, LVR, LRV, n);
}
//////////////////////////////////////////////////////////////////////////////////////////
template<typename Type>  //以下的都是寫保護(hù)的方法，供自己使用
void BinTree<Type>::createBinTree_1(BinTreeNode<Type> *&t, const char *LVR, const char *LRV, int n){  //中序和后序創(chuàng)建二叉樹
    if(n == 0){
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != LRV[n-1]){
        k++;
    }
    t = new BinTreeNode<Type>(LVR[k]);
    
    createBinTree_1(t->rightChild, LVR+k+1, LRV+k, n-k-1);
    createBinTree_1(t->leftChild, LVR, LRV, k);
}
template<typename Type>
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t, const char *VLR, const char *LVR, int n){   //先序和中序創(chuàng)建二叉樹
    if(n == 0){
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != VLR[0]){
        k++;
    }
    t = new BinTreeNode<Type>(LVR[k]);
    createBinTree(t->leftChild, VLR+1, LVR, k);
    createBinTree(t->rightChild, VLR+k+1, LVR+k+1, n-k-1);
}
template<typename Type>
void BinTree<Type>::levelOrder(BinTreeNode<Type>* t)const{  //層次遍歷
    queue<BinTreeNode<Type> *> qu;
    BinTreeNode<Type> *p;

    if(t != NULL){
        qu.push(t);
        while(!qu.empty()){
            p = qu.front();
            qu.pop();
            cout<<p->data<<" ";
            if(p->leftChild){
                qu.push(p->leftChild);
            }
            if(p->rightChild){
                qu.push(p->rightChild);
            }
        }
    }
}
typedef enum{L, R}Tag;
template<typename Type>
class stkNode{
public:
    stkNode(BinTreeNode<Type> *p = NULL) : ptr(p), tag(L){}
public:
    BinTreeNode<Type> *ptr;
    Tag                   tag; //L R
};
template<typename Type>
void BinTree<Type>::endOrder_1(BinTreeNode<Type>* t)const{  //非遞歸后序
    stkNode<Type> n;
    stack<stkNode<Type>> st;
    BinTreeNode<Type> *p = t;
    
    do{
        while(p != NULL){
            n.ptr = p;
            n.tar = L;
            st.push(n);
            p = p->leftChild;
        }
        bool isRun = true;
        while(isRun && !st.empty()){
            n = st.top();
            st.pop();

            switch(n.tag){
            case L:
                p = n.ptr;
                n.tag = R;
                st.push(n);
                p = p->rightChild;
                isRun = false;
                break;
            case R:
                cout<<n.ptr->data<<" ";
                break;
            }
        }
    }while(!st.empty());//不用p1=NULL,因?yàn)楫?dāng)?？諘r(shí)，最后一個(gè)節(jié)點(diǎn)剛好被訪問完成。
}
template<typename Type>
void BinTree<Type>::inOrder_1(BinTreeNode<Type>* t)const{  //非遞歸中序
    stack<BinTreeNode<Type> *> st;
    BinTreeNode<Type> *p = t;

    do{
        while(p != NULL){
            st.push(p);
            p = p->leftChild;
        }
        if(!st.empty()){
            p = st.top();
            st.pop();
            cout<<p->data<<" ";
            p = p->rightChild;
        }//中序遍歷時(shí)，當(dāng)root出棧時(shí)，此時(shí)占空，
    }while(p != NULL || !st.empty()); //為根的時(shí)候右邊還要入棧。
}

template<typename Type>
void BinTree<Type>::prevOrder_1(BinTreeNode<Type>* t)const{  //非遞歸先序
    stack<BinTreeNode<Type> *> st;
    BinTreeNode<Type> *tmp;

    if(t != NULL){
        st.push(t);
        while(!st.empty()){
            tmp = st.top();
            st.pop();
            cout<<tmp->data<<" ";
            if(tmp->rightChild){
                st.push(tmp->rightChild);
            }
            if(tmp->leftChild){
                st.push(tmp->leftChild);
            }
        }
    }
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::copy(BinTreeNode<Type> *t)const{  //拷貝函數(shù)
    BinTreeNode<Type>* tmp;

    if(t == NULL){
        return NULL;
    }else{
        tmp = new BinTreeNode<Type>(t->data);
        tmp->leftChild = copy(t->leftChild);
        tmp->rightChild = copy(t->rightChild);
    }

    return tmp;
}
template<typename Type>
bool BinTree<Type>::equal(BinTreeNode<Type> *t, BinTreeNode<Type> *t1)const{  //兩個(gè)二叉樹是否相同的比較
    if(t == NULL && t1 == NULL){  //取反判斷與這個(gè)是一個(gè)道理
        return true;
    }
    if(t != NULL && t1!= NULL && t->data == t1->data && equal(t->leftChild, t1->leftChild)
        && equal(t->rightChild, t1->rightChild)){
        return true;
    }else{

        return false;
    }
}
template<typename Type>
void BinTree<Type>::makeEmpty(BinTreeNode<Type> *t){  //將二叉樹置空
    if(t != NULL){
        makeEmpty(t->leftChild);
        makeEmpty(t->rightChild);
        delete t;
    }
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::parent(BinTreeNode<Type>* cur, BinTreeNode<Type> *t)const{  //查找當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)
    if(t == NULL || cur == NULL || cur == t){
        return NULL;
    }
    if(t->leftChild == cur || t->rightChild == cur){
        return t;
    }        //思路：利用父的孩子節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)比較
    BinTreeNode<Type> *p = parent(cur, t->leftChild);
    if(p != NULL){
        return p;
    }

    return parent(cur, t->rightChild);
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::find(const Type &key, BinTreeNode<Type> *t)const{   //查找當(dāng)前結(jié)點(diǎn)
    if(t == NULL){
        return NULL;
    }
    if(t->data == key){
        return t;
    }

    BinTreeNode<Type> *p = find(key, t->leftChild);
    if(p != NULL){
        return p;
    }

    return find(key, t->rightChild);
}
template<typename Type>
int BinTree<Type>::height(BinTreeNode<Type> *t)const{  //求樹的高度
    if(t == NULL){
        return 0;
    }
    int leftHeight = height(t->leftChild);
    int rightHeight = height(t->rightChild);

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
template<typename Type>
int BinTree<Type>::size(BinTreeNode<Type> *t)const{  //求結(jié)點(diǎn)個(gè)數(shù)
    if(t == NULL){
        return 0;
    }

    return size(t->leftChild) + size(t->rightChild) + 1;
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::createBinTree_1(const char *&str){  //創(chuàng)建二叉樹
    BinTreeNode<Type> *t;

    if(refval == *str){
        t = NULL;
    }else{
        t = new BinTreeNode<Type>(*str);
        t->leftChild = createBinTree_1(++str);
        t->rightChild = createBinTree_1(++str);
    }
    return t;
}

template<typename Type>
void BinTree<Type>::createBinTree(const char *&str, BinTreeNode<Type> *&t){  //創(chuàng)建二叉樹
    if(*str == refval){
        t = NULL;
    }else{
        t = new BinTreeNode<Type>(*str);
        createBinTree(++str, t->leftChild);  //前加，后加不一樣！?。≡谶@里，就是傳引用，保證每次字符串都是往后走的
        createBinTree(++str, t->rightChild);
    }
}
template<typename Type>
BinTreeNode<Type>* BinTree<Type>::createBinTree_1(){  //創(chuàng)建二叉樹
    Type createData;
    cin>>createData;
    BinTreeNode<Type> *t;

    if(refval == createData){
        t = NULL;
    }else{
        t = new BinTreeNode<Type>(createData);
        t->leftChild = createBinTree_1();
        t->rightChild = createBinTree_1();
    }

    return t;
}
template<typename Type>
void BinTree<Type>::endOrder(BinTreeNode<Type> *t)const{  //后序遞歸遍歷
    if(t == NULL){
        return;
    }else{
        endOrder(t->leftChild);
        endOrder(t->rightChild);
        cout<<t->data<<" ";
    }
}

template<typename Type> 
void BinTree<Type>::inOrder(BinTreeNode<Type> *t)const{  //中序遞歸遍歷
    if(t == NULL){
        return;
    }else{
        inOrder(t->leftChild);
        cout<<t->data<<" ";
        inOrder(t->rightChild);
    }
}

template<typename Type>
void BinTree<Type>::prevOrder(BinTreeNode<Type> *t)const{  //先序遞歸遍歷
    if(t == NULL){
        return;
    }else{
        cout<<t->data<<" ";
        prevOrder(t->leftChild);
        prevOrder(t->rightChild);
    }
}
//根據(jù)先根序創(chuàng)建二叉樹
template<typename Type>
void BinTree<Type>::createBinTree(BinTreeNode<Type> *&t){  //創(chuàng)建二叉樹
    Type createData;
    cin>>createData;

    if(refval == createData){
        t = NULL;
    }else{
        t = new BinTreeNode<Type>(createData);
        createBinTree(t->leftChild);
        createBinTree(t->rightChild);
    }
}

#endif

以上代碼我采用折疊的方式進(jìn)行寫的。類外公有調(diào)用下面緊跟保護(hù)方法的實(shí)現(xiàn)；

(2)、測(cè)試代碼

#include"BinTree.h"
//ABC##DE##F##G#H##
/*
先根序如下:
A B C D E F G H
中根序如下:
C B E D F A G H
后根序如下:
C E F D B H G A
*/
int main(void){
//    char *VLR = "ABCDEFGH";
//    char *LVR = "CBEDFAGH";
//    char *LRV = "CEFDBHGA";

//    BinTree<char> bt; //對(duì)象初始化不寫'#'；
//    int n = strlen(VLR);
//    bt.createBinTree(VLR, LVR, n); //在這里創(chuàng)建二叉樹不用'#'結(jié)束，因?yàn)槭怯上刃蚝椭行騽?chuàng)建，不看結(jié)束標(biāo)志'#';
//    bt.createBinTree_1(LVR, LRV, n);
//    bt.prevOrder();
//    cout<<endl;

    //bt.createBinTree(VLR, LRV, n); 不能創(chuàng)建

/*
    BinTree<char> bt('#');
    char *str = "ABC##DE##F##G#H##";
//    char *str = "ABC##DE###G#H##";
    bt.createBinTree(str);
    BinTree<char> bt1(bt);
    bt1.levelOrder();
    cout<<endl;
    
*/
      
/*    
    
//    st.createBinTree();
    BinTree<char> bt('#');
    BinTree<char> bt1('#');
    char *str = "ABC##DE##F##G#H##";
    bt.createBinTree(str);
    bt1.createBinTree(str);  //構(gòu)建的是一顆空樹,引用傳遞構(gòu)建，原先字符串已經(jīng)為空！

    if(bt.equal(bt1)){
        cout<<"相等"<<endl;
    }else{
        cout<<"不相等"<<endl;
    }
*/    
    BinTree<char> bt('#');
    char *str = "ABC##DE##F##G#H##";
    bt.createBinTree(str);
    cout<<bt.size()<<endl;
    cout<<bt.height()<<endl;
    BinTreeNode<char> *p = bt.find('H');
    BinTreeNode<char> *t = bt.find('G');
    printf("%p\n", t);
    BinTreeNode<char> *q = bt.parent(p);
    printf("%p\n", q);

    bt.prevOrder();
    cout<<endl;
    bt.inOrder();
    cout<<endl;
    bt.endOrder();
    cout<<endl;
    
    return 0;
}

這是所有測(cè)試要用的代碼，在編寫時(shí)，寫一個(gè)方法測(cè)試一個(gè)，將測(cè)試過的就注釋起來了；

(3)、部分測(cè)試結(jié)果

二叉樹之方法實(shí)現(xiàn)