问题描述

实现一个完整二叉树c++模板类

为二叉树实现一个完整的C++模板类。要求：包含构造函数、复制构造函数和析构函数，实现四个遍历及前向迭代

解决方案

 #include<iostream>
#include<deque>
using namespace std;

//binary node with parent node
template<typename T>
class node
{
public:
    node(const T &v, node<T> *L=NULL, node<T> *R=NULL, node<T> *P=NULL):left(L),right(R),par(P)
    {
        value = v;
    }

public:
    T value;
    node<T> *left, *right, *par;
};

// binary tree
template<typename T>
class BTree
{
public:
    BTree(node<T> *R=NULL):root(R)
    { }
    ~BTree()
    {
        if(root)
            delall();
    }

    node<T> *findby(const T &v);    // 层次遍历,返回找到第一个结点值为v的结点指针
    void Insert(const T &v);        // 层次遍历二叉树,将值插在遇到的第一个叶子或者子树不全的结点上
    bool delby(const T &v);            // 层次遍历二叉树,删除遇到的第一个结点值为v的结点

    node<T> *findleave(node<T> *cur); // 层次遍历二叉树,返回cur下遇到的第一个叶子结点
    void delall();
    void display(node<T> *r);        // 先序遍历,打印二叉树各结点的值

public:
    node<T> *root;
};

template<typename T>
node<T> *BTree<T>::findby(const T &v)
{
    deque< node<T>* > Q;
    bool isfind; // find v ==> isfind = true; not find ==> isfind = false
    node<T> *tmp;

    if(root)
        Q.push_back(root);
    else
    {
        return NULL;
    }

    isfind = false;
    tmp = NULL;
    while(!Q.empty() && !isfind)
    {
        tmp = Q.front();
        Q.pop_front();

        if(tmp->value == v)
            isfind = true;
        else
        {
            if(tmp->left)
                Q.push_back(tmp->left);
            if(tmp->right)
                Q.push_back(tmp->right);
        }
    }

    if(!isfind)
        tmp = NULL;

    return tmp;
}

template<typename T>
void BTree<T>::Insert(const T &v)
{
    deque< node<T>* > Q;
    node<T> *cur;

    if(root)
        Q.push_back(root);
    else
    {
        root = new node<T>(v, NULL, NULL, NULL);
        return;
    }

    while(!Q.empty()) // 原来是这里出错了.第一次是写了Q.empty(),应该是!Q.empty()
    {
        cur = Q.front();
        Q.pop_front();

        if(cur->left)
            Q.push_back(cur->left);
        else
        {
            cur->left = new node<T>(v, NULL, NULL, cur);
            return;
        }

        if(cur->right)
            Q.push_back(cur->right);
        else
        {
            cur->right = new node<T>(v, NULL, NULL, cur);
            return;
        }
    }
}

template<typename T>
bool BTree<T>::delby(const T &v)
{
    node<T> *cur, *tmp;
    bool isleave; // 判断是不是叶子结点

    isleave = false;
    cur = NULL;
    cur = findby(v);
    if(!cur) // 说明不存在结点值为v的结点
        return false;
    else
    {
        if(cur->left && cur->right) // 左右子树不为空
        {
            tmp = findleave(cur); // 通过层次遍历,找出cur下第一个叶子结点
            tmp->left = cur->left;
            tmp->right = cur->right;

            // 改变左右子树的父结点,不过要判断cur是否为根结点
            if(cur->left)
                cur->left->par = tmp;
            if(cur->right)
                cur->right->par = tmp;
        }
        else if(cur->left) // 右子树为空
            tmp = cur->left;
        else if(cur->right) // 左子树为空
            tmp = cur->right;
        else // 左右子树皆为空,说明要删除的是叶子结点
        {
            (cur == cur->par->left) ? (cur->par->left = NULL) :(cur->par->right = NULL);
            isleave = true;
        }

        if(!isleave)
        {
            tmp->par = cur->par;

            if(cur->par)
                (cur == cur->par->left) ? (cur->par->left = tmp) :(cur->par->right = tmp);

            if(root == cur)
            {
                root = tmp;
                root->par = NULL;
            }
        }
    }

    delete cur;

    return true;
}

// 层次遍历二叉树,返回遇到的第一个叶子.二叉树的叶子特征:左右子树为NULL
template<typename T>
node<T> *BTree<T>::findleave(node<T> *cur)
{
    deque< node<T>* > Q;    // 用于层次遍历的双端队列
    node<T> *tmp;            // 返回的叶子指针
    bool isfind;            // 用来跳出while循环的flag

    if(!cur)                // 假如cur为空,则返回NULL
        return NULL;
    else
        Q.push_back(cur);    // 推进Q中

    isfind = false;
    while(!Q.empty() && !isfind)    // 当队列为空或者找到叶子时终止循环
    {
        tmp = Q.front();
        Q.pop_front();

        if(!tmp->left && !tmp->right)
            isfind = true;
        else if(tmp->left)
            Q.push_back(tmp->left);
        else
            Q.push_back(tmp->right);
    }

    // 处理该叶子的父结点
    if(tmp->par)
        (tmp == tmp->par->left) ? (tmp->par->left = NULL) : (tmp->par->right = NULL);

    return tmp;
}

// 通过层次遍历删除二叉树所有结点
template<typename T>
void BTree<T>::delall()
{
    deque< node<T>* > Q;

    // 假如root为空,则直接返回,不为空,则推进Q中
    if(root)
        Q.push_back(root);
    else
        return ;

    while(!Q.empty())
    {
        root = Q.front();
        Q.pop_front();

        if(root->left)
            Q.push_back(root->left);
        if(root->right)
            Q.push_back(root->right);

        delete root;
        root = NULL;
    }
}

// 通过前序遍历打印二叉树各结点的值
template<typename T>
void BTree<T>::display(node<T> *r)
{
    if(r)
    {
        cout << r->value << ' ';
        display(r->left);
        display(r->right);
    }
}

int main(void)
{
    BTree<int> BT;
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    for(int it = 0; it < sizeof(a) / sizeof(a[0]); it++)
        BT.Insert(a[it]); // 第一次测试,Insert不成功,Insert 已修正

    BT.display(BT.root);
    cout << endl;

    BT.delby(1);
    BT.delby(3);
    BT.delby(6);
    BT.delby(2);
    BT.delby(8);

    BT.display(BT.root);
    cout << endl;

    BT.delall();
    BT.display(BT.root);

    return 0;
}

解决方案二：

http://www.oschina.net/code/snippet_230828_10246

C++二叉树模板类

 #ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__
#include<string>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
template<class Elem>
class BinaryTree
{
protected:
    typedef struct Node
    {
    public:
        Node(){ left = right = parent =-1;}
        Elem element;
        unsigned int left;
        unsigned int right;
        unsigned int parent;
    }Node;
    std::vector<Node> data;
    virtual unsigned int Depth(unsigned int index)const
    {
        if(index < data.size()){
            unsigned int l,r,ld = 0,rd = 0;
            l = data[index].left;
            r = data[index].right;
            if(l < data.size()){
                ld = Depth(l);
            }
            if(r < data.size()){
                rd = Depth(r);
            }
            return ld > rd ? (ld+1) : (rd+1);
        }
        return 0;
    }
public:
    typedef enum ChildEnum
    {
        Left=0,Right=1,None=-1,
    }ChildEnum;
protected:
    virtual void MarkChildren(unsigned int index,vector<unsigned int>& marks)
    {
        if(index < data.size()){
            marks.push_back(index);
            if(data[index].left < data.size()){
                MarkChildren(data[index].left,marks);
            }
            if(data[index].right < data.size()){
                MarkChildren(data[index].right,marks);
            }
        }
    }
public :
    //typedef typename Elem Elem;
    BinaryTree<Elem>(){}
    BinaryTree<Elem>(const BinaryTree<Elem>& T)
    {
        data.insert(T.data.begin(),T.data.end());
    }
    BinaryTree<Elem>(const Elem& value,unsigned int totalNo)
    {
        if(totalNo >0 ){
            unsigned int depth = (unsigned int)(log((double)(totalNo+1))/log(2.0));
            Root(value);
            if(depth > 1){
                vector<unsigned int> leafs;
                unsigned int u= depth,i;
                while(u > 0){
                    if(data.size() == totalNo){
                        break;
                    }
                    leafs.clear();
                    MarkLeaf(leafs);
                    for(i = 0; i < leafs.size(); ++i){
                        if(data.size() < totalNo){
                            InsertChild(leafs[i],Left,value);
                        }else{
                            break;
                        }
                        if(data.size() < totalNo){
                            InsertChild(leafs[i],Right,value);
                        }else{
                            break;
                        }
                    }
                    u--;
                }
            }
        }
        //(totalNo+1)
    }
    BinaryTree<Elem>(const Elem& value,unsigned int depth,unsigned int leafNo)
    {
        vector<unsigned int> leafs;
        unsigned int i,j,other;
        Root(value);
        for(i = 1 ; i < depth-1; i++){
            MarkLeaf(leafs);
            for(j = 0; j < leafs.size(); ++j){
                InsertChild(leafs[j],Left,value);
                InsertChild(leafs[j],Right,value);
            }
            leafs.clear();
        }
        MarkLeaf(leafs);
        other = leafNo - leafs.size();
        for(j = 0  ; j < other; j++ ){
            InsertChild(leafs[j],Left,value);
            InsertChild(leafs[j],Right,value);
        }
        for(j = other  ; j < leafs.size(); j++ ){
            InsertChild(leafs[j],Left,value);
        }
    }
    virtual bool IsEmpty(void)const{return data.empty();}
    virtual unsigned int Depth(void) const
    {
        if(data.size()>0){
            unsigned int l,r,ld = 0,rd = 0;
            l = data[0].left;
            r = data[0].right;
            if(l < data.size()){
                ld = Depth(l);
            }
            if(r < data.size()){
                rd = Depth(r);
            }
            return ld > rd ? (ld+1) : (rd+1);
        }else{
            return 0;
        }
    }
    virtual void Assign(unsigned int index,const Elem& value)
    {
        if(index < data.size()){
            data[index].element = value;
        }else if(index == data.size()){
            Node node = Node();
            node.element = value;
            data.push_back(node);
        }
    }
    virtual void Root(const Elem& value)
    {
        Clear();
        Node node = Node();
        node.element = value;
        data.push_back(node);
    }
    virtual Elem* Root(void)
    {
        if(data.size() >0)
            return &(data[0].element);
        return NULL;
    }
    virtual Elem* Value(unsigned int index)
    {
        if(index < data.size())
            return &(data[index].element);
        return NULL;
    }
    virtual Elem* Parent(unsigned int index)
    {
        if(index >= data.size())
            return NULL;
        unsigned int p = data[index].parent;
        if(p < data.size())
            return &(data[p].element);
        return NULL;
    }
    virtual Elem* LeftChild(unsigned int index)
    {
        if(index >= data.size())
            return NULL;
        unsigned int l = data[index].left;
        if(l < data.size())
            return &(data[l].element);
        return NULL;
    }
    virtual Elem* RightChild(unsigned int index)
    {
        if(index >= data.size())
            return NULL;
        unsigned int r = data[index].right;
        if(r < data.size())
            return &(data[r].element);
        return NULL;
    }
    virtual Elem* LeftSibling(unsigned int index)
    {
        if(index >= data.size())
            return NULL;
        unsigned int p = data[index].parent;
        if(p >= data.size())
            return NULL;
        unsigned int l = data[p].left;
        if(l < data.size())
            return &(data[l].element);
        return NULL;
    }
    virtual Elem* RightSibling(unsigned int index)
    {
        if(index >= data.size())
            return NULL;
        unsigned int p = data[index].parent;
        if(p >= data.size())
            return NULL;
        unsigned int r = data[p].right;
        if(r < data.size())
            return &(data[r].element);
        return NULL;
    }
    virtual void Clear(void)
    {
        data.clear();
    }
    virtual bool InsertChild(unsigned int index,int flag,const BinaryTree<Elem>& t)
    {
        unsigned int offset = data.size();
        unsigned int append = t.data.size();
        unsigned int i;
        if(index < data.size()){
            if(t.data.size() >0){
                if(flag == Left){
                    if(data[index].left >= data.size()){
                        for(i=0; i < append; i++){
                            data.push_back(t.data[i]);
                            data[offset+i].parent = index;
                            if(t.data[i].left < append){
                                data[offset+i].left += offset;
                            }
                            if(t.data[i].right < append){
                                data[offset+i].right += offset;
                            }
                        }
                    }
                }else if(flag == Right){
                    if(data[index].right >= data.size()){
                        for(i=0; i < append; i++){
                            data.push_back(t.data[i]);
                            data[offset+i].parent = index;
                            if(t.data[i].left < append){
                                data[offset+i].left += offset;
                            }
                            if(t.data[i].right < append){
                                data[offset+i].right += offset;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
    virtual unsigned int InsertChild(unsigned int index,int flag,const Elem& value)
    {
        if(index < data.size()){
            if(flag == Left && data[index].left >= data.size() ){
                Node node;
                node.element = value;
                node.left = -1;
                node.right = -1;
                node.parent = index;
                data[index].left = data.size();
                data.push_back(node);
                return data.size()-1;
            }else if(flag == Right && data[index].right >= data.size()){
                Node node;
                node.element = value;
                node.left = -1;
                node.right = -1;
                node.parent = index;
                data[index].right = data.size();
                data.push_back(node);
                return data.size()-1;
            }
        }
        return -1;
    }
    virtual bool DeleteChild(unsigned int index,int flag)
    {
        unsigned int i,j,k;
        if(index < data.size()){
            vector<unsigned int> marks;
            if(flag == Left && data[index].left < data.size()){
                MarkChildren(data[index].left,marks);
                data[index].left = -1;
            }else if(flag == Right && data[index].right < data.size()){
                MarkChildren(data[index].right,marks);
                data[index].right = -1;
            }
            if(marks.size()>0){//have elem to delete;
                unsigned int newSize = data.size() - marks.size();
                std::sort(marks.begin(),marks.end());//排序，从小到大
                set<unsigned int> dels;
                vector<unsigned int> swaps;
                for(i = 0 ;i < marks.size(); ++i){
                    if(marks[i] >= newSize ){
                        dels.insert(marks[i]);
                    }
                }
                for(j = newSize; j < data.size(); ++j){
                    if(dels.find(j) == dels.end()){
                        swaps.push_back(j);
                    }
                }
                //最关键的，交换开始
                map<unsigned int,unsigned int> swapMap;
                for(k = 0; k < swaps.size(); ++k){
                    swapMap[swaps[k]] = marks[k];
                }
                for(k = 0; k < swaps.size(); ++k){
                    data[marks[k]] = data[swaps[k]];
                }
                for(i = 0; i < newSize; ++i){
                    unsigned int l = data[i].left,r =data[i].right;
                    if(l < data.size() && swapMap.find(l) != swapMap.end()){
                        data[i].left = swapMap[l];
                    }
                    if(r < data.size() && swapMap.find(r) != swapMap.end()){
                        data[i].right = swapMap[r];
                    }
                }
                for(i = 0 ; i < marks.size(); ++i){
                    data.pop_back();
                }
                return true;
            }
        }
        return false;
    }
    virtual void MarkLeaf(vector<unsigned int>& marks)
    {
        for(unsigned int i=0; i < data.size();i++){
            if(data[i].left > data.size() && data[i].right > data.size() ){
                marks.push_back(i);
            }
        }
    }
};

#endif

解决方案三：

http://blog.csdn.net/apaolove/article/details/1866204

解决方案四：

二叉树完整实现C++
求二叉树中节点间的最大距离（c++代码完整实现）