二叉树之方法实现

1、二叉树上的操作

江门网站制作公司哪家好，找成都创新互联！从网页设计、网站建设、微信开发、APP开发、响应式网站设计等网站项目制作，到程序开发，运营维护。成都创新互联于2013年创立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联。

  均是C++实现先根序创建二叉树及其其它方法

  我认为在二叉树的创建方法和遍历以外，以下方法值得我们关注：

public:
    int size()const;  //求结点个数
    int height()const;  //求树的高度
    BinTreeNode* root_1()const; //求根节点
    BinTreeNode* leftChild(BinTreeNode* cur)const;  //求当前结点的左孩子
    BinTreeNode* rightChild(BinTreeNode* cur)const; //求当前结点的右孩子
    BinTreeNode* find(const Type &key)const;              //查找当前结点
    BinTreeNode* parent(BinTreeNode* cur)const;     //查找当前结点的父结点
    void makeEmpty();                                           //将二叉树置空
    bool equal(const BinTree &t)const;                    //两个二叉树是否相同的比较
    BinTreeNode* copy(BinTreeNode *t)const;         //拷贝构造函数的方法，复制一个二叉树

2、方法一一实现：

  (1)、求结点个数

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

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

  (2)、求树的高度

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

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

  (3)、查找当前结点

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

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

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

  (4)、查找当前结点的父结点

template
BinTreeNode* BinTree::parent(BinTreeNode* cur, BinTreeNode *t)const{
    if(t == NULL || cur == NULL || cur == t){
        return NULL;
    }
    if(t->leftChild == cur || t->rightChild == cur){
        return t;
    }        //思路：利用父的孩子节点和当前节点比较
    BinTreeNode *p = parent(cur, t->leftChild);
    if(p != NULL){
        return p;
    }

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

  (5)、将二叉树置空

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

  (6)、两个二叉树是否相同的比较

template
bool BinTree::equal(BinTreeNode *t, BinTreeNode *t1)const{
    if(t == NULL && t1 == NULL){  //取反判断与这个是一个道理
        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)、拷贝一个二叉树

template
BinTreeNode* BinTree::copy(BinTreeNode *t)const{
    BinTreeNode* tmp;

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

    return tmp;
}

以上的这些方法都是利用二叉树的性质递归实现，比较好想清楚，就不做解释了，实在有问题，画画图就会好很多。

3、二叉树的所有方法，测试，及测试结果如下：

  (1)、所有关于二叉树的代码：

#ifndef _BIN_TREE_H_
#define _BIN_TREE_H_

#include
#include  //非递归遍历引入栈
#include  //层次遍历引入队列
using namespace std;

template //为的是声明友元类，调用BinTreeNode的私有数据
class BinTree;

template  //BinTreeNode类
class BinTreeNode{   
    friend class BinTree;
public:
    BinTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}
    BinTreeNode(Type value, BinTreeNode *left = NULL, BinTreeNode *right = NULL) :
    data(value), leftChild(left), rightChild(right){}
    ~BinTreeNode(){}
private:
    Type data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
};
///////////////////////////////////////////////////////////////////////////////
template   //BinTree类
class BinTree{
public:
    BinTree() : root(NULL){}
    BinTree(Type ref) : root(NULL), refval(ref){}
    BinTree(const BinTree &t){
        root = copy(t.root);  //调用拷贝方法
    }
    ~BinTree(){
        makeEmpty();  //析构函数这里将二叉树置空
        root = NULL;    
    }
public:                 //创建二叉树
    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* root_1()const; //以下的三个方法比较简单，就不在进行调用保护方法了；
    BinTreeNode* leftChild(BinTreeNode* cur)const;
    BinTreeNode* rightChild(BinTreeNode* cur)const;
    BinTreeNode* find(const Type &key)const;
    BinTreeNode* parent(BinTreeNode* cur)const;
    void makeEmpty();
    bool equal(const BinTree &t)const;
    BinTreeNode* copy(BinTreeNode *t)const;
public:              //非递归遍历
    void prevOrder_1()const;
    void inOrder_1()const;
    void endOrder_1()const;
    void levelOrder()const; //puublic:供外界提供的接口，
////////////////////////////////////////////////////////////////////////////////
protected:                 //protected:供自己函数内部调用，写保护方法
    void prevOrder_1(BinTreeNode* t)const;
    void inOrder_1(BinTreeNode* t)const;
    void endOrder_1(BinTreeNode* t)const;
    void levelOrder(BinTreeNode* t)const;
protected:
    int size(BinTreeNode *t)const;
    int height(BinTreeNode *t)const;
    BinTreeNode* find(const Type &key, BinTreeNode *t)const;
    BinTreeNode* parent(BinTreeNode* cur, BinTreeNode *t)const;
    void makeEmpty(BinTreeNode* t);
    bool equal(BinTreeNode *t, BinTreeNode *t1)const;
protected:
    void prevOrder(BinTreeNode *t)const;
    void inOrder(BinTreeNode *t)const;
    void endOrder(BinTreeNode *t)const;
protected :
    void createBinTree(BinTreeNode *&t);
    BinTreeNode* createBinTree_1();
    void createBinTree(const char *&str, BinTreeNode *&t);
    BinTreeNode* createBinTree_1(const char *&str);
    void createBinTree(BinTreeNode *&t, const char *VLR, const char *LVR, int n);
    void createBinTree_1(BinTreeNode *&t, const char *LVR, const char *LRV, int n);
                         //以上都只是在类内声明；
private:
    BinTreeNode *root;
    Type               refval;  //'#'
};
///////////////////////////////////////////////////////////////////////////////
template  //类外实现公有方法的调用
void BinTree::createBinTree(){  //创建二叉树
    //createBinTree(root);
    root = createBinTree_1();
}
template
void BinTree::prevOrder()const{ //先序递归遍历
    cout<<"先根序如下: "<
void BinTree::inOrder()const{ //中序递归遍历
    cout<<"中根序如下: "<
void BinTree::endOrder()const{  //后序递归遍历
    cout<<"后根序如下: "<
void BinTree::createBinTree(const char *str){ //创建二叉树
//    createBinTree(str, root);
    root = createBinTree_1(str);
}
template
int BinTree::size()const{  //求结点个数
    return size(root);
}
template
int BinTree::height()const{ //求树的高度
    return height(root);
}
template
BinTreeNode* BinTree::root_1()const{ //求根节点
    return root;
}
template
BinTreeNode* BinTree::leftChild(BinTreeNode* cur)const{ //求当前结点的左孩子
    return cur->leftChild;
}
template
BinTreeNode* BinTree::rightChild(BinTreeNode* cur)const{  //求当前结点的右孩子
    return cur->rightChild;
}
template
BinTreeNode* BinTree::find(const Type &key)const{  //查找当前结点
    return find(key, root);
}
template
BinTreeNode* BinTree::parent(BinTreeNode* cur)const{ //查找当前结点的父结点
    return parent(cur, root);
}
template
void BinTree::makeEmpty(){ //将二叉树置空
    makeEmpty(root);
}
template
bool BinTree::equal(const BinTree &t)const{ //两个二叉树是否相同的比较
    return equal(t.root, root);
}
template
void BinTree::prevOrder_1()const{  //非递归先序
    prevOrder_1(root);
}
template
void BinTree::inOrder_1()const{   //非递归中序
    inOrder_1(root);
}
template
void BinTree::endOrder_1()const{   //非递归后序
    endOrder(root);
}
template
void BinTree::levelOrder()const{   //层次遍历
    levelOrder(root);
}
template
void BinTree::createBinTree(const char *VLR, const char *LVR, int n){ //创建二叉树
    createBinTree(root, VLR, LVR, n);
}
template 
void BinTree::createBinTree_1(const char *LVR, const char *LRV, int n){ //创建二叉树
    createBinTree_1(root, LVR, LRV, n);
}
//////////////////////////////////////////////////////////////////////////////////////////
template  //以下的都是写保护的方法，供自己使用
void BinTree::createBinTree_1(BinTreeNode *&t, const char *LVR, const char *LRV, int n){  //中序和后序创建二叉树
    if(n == 0){
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != LRV[n-1]){
        k++;
    }
    t = new BinTreeNode(LVR[k]);
    
    createBinTree_1(t->rightChild, LVR+k+1, LRV+k, n-k-1);
    createBinTree_1(t->leftChild, LVR, LRV, k);
}
template
void BinTree::createBinTree(BinTreeNode *&t, const char *VLR, const char *LVR, int n){   //先序和中序创建二叉树
    if(n == 0){
        t = NULL;
        return;
    }
    int k = 0;
    while(LVR[k] != VLR[0]){
        k++;
    }
    t = new BinTreeNode(LVR[k]);
    createBinTree(t->leftChild, VLR+1, LVR, k);
    createBinTree(t->rightChild, VLR+k+1, LVR+k+1, n-k-1);
}
template
void BinTree::levelOrder(BinTreeNode* t)const{  //层次遍历
    queue *> qu;
    BinTreeNode *p;

    if(t != NULL){
        qu.push(t);
        while(!qu.empty()){
            p = qu.front();
            qu.pop();
            cout<data<<" ";
            if(p->leftChild){
                qu.push(p->leftChild);
            }
            if(p->rightChild){
                qu.push(p->rightChild);
            }
        }
    }
}
typedef enum{L, R}Tag;
template
class stkNode{
public:
    stkNode(BinTreeNode *p = NULL) : ptr(p), tag(L){}
public:
    BinTreeNode *ptr;
    Tag                   tag; //L R
};
template
void BinTree::endOrder_1(BinTreeNode* t)const{  //非递归后序
    stkNode n;
    stack> st;
    BinTreeNode *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<data<<" ";
                break;
            }
        }
    }while(!st.empty());//不用p1=NULL,因为当栈空时，最后一个节点刚好被访问完成。
}
template
void BinTree::inOrder_1(BinTreeNode* t)const{  //非递归中序
    stack *> st;
    BinTreeNode *p = t;

    do{
        while(p != NULL){
            st.push(p);
            p = p->leftChild;
        }
        if(!st.empty()){
            p = st.top();
            st.pop();
            cout<data<<" ";
            p = p->rightChild;
        }//中序遍历时，当root出栈时，此时占空，
    }while(p != NULL || !st.empty()); //为根的时候右边还要入栈。
}

template
void BinTree::prevOrder_1(BinTreeNode* t)const{  //非递归先序
    stack *> st;
    BinTreeNode *tmp;

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

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

    return tmp;
}
template
bool BinTree::equal(BinTreeNode *t, BinTreeNode *t1)const{  //两个二叉树是否相同的比较
    if(t == NULL && t1 == NULL){  //取反判断与这个是一个道理
        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
void BinTree::makeEmpty(BinTreeNode *t){  //将二叉树置空
    if(t != NULL){
        makeEmpty(t->leftChild);
        makeEmpty(t->rightChild);
        delete t;
    }
}
template
BinTreeNode* BinTree::parent(BinTreeNode* cur, BinTreeNode *t)const{  //查找当前结点的父结点
    if(t == NULL || cur == NULL || cur == t){
        return NULL;
    }
    if(t->leftChild == cur || t->rightChild == cur){
        return t;
    }        //思路：利用父的孩子节点和当前节点比较
    BinTreeNode *p = parent(cur, t->leftChild);
    if(p != NULL){
        return p;
    }

    return parent(cur, t->rightChild);
}
template
BinTreeNode* BinTree::find(const Type &key, BinTreeNode *t)const{   //查找当前结点
    if(t == NULL){
        return NULL;
    }
    if(t->data == key){
        return t;
    }

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

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

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
template
int BinTree::size(BinTreeNode *t)const{  //求结点个数
    if(t == NULL){
        return 0;
    }

    return size(t->leftChild) + size(t->rightChild) + 1;
}
template
BinTreeNode* BinTree::createBinTree_1(const char *&str){  //创建二叉树
    BinTreeNode *t;

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

template
void BinTree::createBinTree(const char *&str, BinTreeNode *&t){  //创建二叉树
    if(*str == refval){
        t = NULL;
    }else{
        t = new BinTreeNode(*str);
        createBinTree(++str, t->leftChild);  //前加，后加不一样！！！在这里，就是传引用，保证每次字符串都是往后走的
        createBinTree(++str, t->rightChild);
    }
}
template
BinTreeNode* BinTree::createBinTree_1(){  //创建二叉树
    Type createData;
    cin>>createData;
    BinTreeNode *t;

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

    return t;
}
template
void BinTree::endOrder(BinTreeNode *t)const{  //后序递归遍历
    if(t == NULL){
        return;
    }else{
        endOrder(t->leftChild);
        endOrder(t->rightChild);
        cout<data<<" ";
    }
}

template 
void BinTree::inOrder(BinTreeNode *t)const{  //中序递归遍历
    if(t == NULL){
        return;
    }else{
        inOrder(t->leftChild);
        cout<data<<" ";
        inOrder(t->rightChild);
    }
}

template
void BinTree::prevOrder(BinTreeNode *t)const{  //先序递归遍历
    if(t == NULL){
        return;
    }else{
        cout<data<<" ";
        prevOrder(t->leftChild);
        prevOrder(t->rightChild);
    }
}
//根据先根序创建二叉树
template
void BinTree::createBinTree(BinTreeNode *&t){  //创建二叉树
    Type createData;
    cin>>createData;

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

#endif

以上代码我采用折叠的方式进行写的。类外公有调用下面紧跟保护方法的实现；

  (2)、测试代码

#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 bt; //对象初始化不写'#'；
//    int n = strlen(VLR);
//    bt.createBinTree(VLR, LVR, n); //在这里创建二叉树不用'#'结束，因为是由先序和中序创建，不看结束标志'#';
//    bt.createBinTree_1(LVR, LRV, n);
//    bt.prevOrder();
//    cout< bt('#');
    char *str = "ABC##DE##F##G#H##";
//    char *str = "ABC##DE###G#H##";
    bt.createBinTree(str);
    BinTree bt1(bt);
    bt1.levelOrder();
    cout< bt('#');
    BinTree bt1('#');
    char *str = "ABC##DE##F##G#H##";
    bt.createBinTree(str);
    bt1.createBinTree(str);  //构建的是一颗空树,引用传递构建，原先字符串已经为空！

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

    bt.prevOrder();
    cout<
这是所有测试要用的代码，在编写时，写一个方法测试一个，将测试过的就注释起来了；        
  (3)、部分测试结果
        
    
至于其它的测试结果就不在给出了，有兴趣可以在测测其它的方法。
            
            
                        

            当前标题：二叉树之方法实现            

            文章分享：http://cdiso.cn/article/jhihhi.html