二叉树操作的C++实现

这几天做数据结构的作业，苦于C++没有现成的二叉树的类，书本上的实现方法是c语言的，而且一点都不好看，太郁闷了。 于是，我就去找，上网搜，国内外的，各种编译语言的，各种类型的二叉树的操作，以及实现的方法。

于是，我决定总结一下。

二叉树的种类是很多的
如二叉查找树，平衡二叉树（AVL），红黑树，B-树，B+树，字典树，后缀树，广义后缀树

我这次总结的只是普通的二叉树的操作：

下面是这个二叉树的类设计

结点的单元

struct BTNode
{
    int data;
    BTNode *leftChild;
    BTNode *rightChild ;
};

二叉树的类

class BinTree
{
public:
    BinTree();//构造函数
    ~BinTree();//析构函数

    //根结点的set，get函数
    void setRoot(BTNode* r){ root=r;}
    BTNode* getRoot(){ return root;}
    BTNode* insertLeftNode(BTNode *cur, int item);//添加左子树
    BTNode* insertRightNode(BTNode *cur, int item);//添加右子树
    void inOrder(BTNode* cur = root);//中序遍历(递归)
    void preOrder(BTNode* cur = root);//前序遍历(递归)
    void postOrder(BTNode* cur = root);//后序遍历(递归)
    void NotReInOrder();//中序遍历(非递归)
    void NotRePreOrder();//前序遍历(非递归)
    int BTreeSize(BTNode* cur = root); //结点个数
    int BTreeLeaves(BTNode* cur = root);//叶子结点
    int BTreeHeight(BTNode* cur = root);//树高
    void Destory(BTNode **root = &this->root);//撤销
private:
    BTNode* root;//这颗二叉树的根结点
};

构造函数的实现

BinTree::BinTree()
{
    root = nullptr;
}

析构函数的实现

BinTree::~BinTree()
{
    this->Destory();//撤销一棵树的函数
}

添加左子树的函数

BTNode *BinTree::insertLeftNode(BTNode *cur, int item)
{
    BTNode *s, *temp;
    if (cur == nullptr)return nullptr;
    temp = cur->leftChild;//暂为保管地址
    s = new BTNode;//新节点
    s->data = item;
    s->leftChild = temp;
    s->rightChild = nullptr;
    cur->leftChild = s;//链接成功

    return cur->leftChild;
}

添加右子树的函数

BTNode *BinTree::insertRightNode(BTNode *cur, int item)
{
    BTNode *s, *temp;
    if (!cur)return nullptr;
    temp = cur->rightChild;//暂为保管地址
    s = new BTNode;//新节点
    s->data = item;
    s->rightChild = temp;
    s->leftChild = nullptr;
    cur->rightChild = s;//链接成功

    return cur->rightChild;
}

中序遍历(递归)

void BinTree::inOrder(BTNode *cur)
{
    if (cur != nullptr)
    {
        inOrder(cur->leftChild); //递归访问
        cout << cur->data << " ";
        inOrder(cur->rightChild); //递归访问
    }
}

前序遍历(递归)

void BinTree::preOrder(BTNode *cur)
{
    if (cur)
    {
        cout << cur->data << " ";
        preOrder(cur->leftChild); //递归访问
        preOrder(cur->rightChild); //递归访问
    }
}

后序遍历(递归)

void BinTree::postOrder(BTNode *cur)
{
    if (cur)
    {
        postOrder(cur->leftChild); //递归访问
        postOrder(cur->rightChild); //递归访问
        cout << cur->data << " ";
    }
}

中序遍历(非递归)

void BinTree::NotReInOrder()
{
    stack<BTNode *> s;

    BTNode *cur = getRoot();

    while (!s.empty() || cur)
    {
        while (cur)
        {
            s.push(cur);
            cur = cur->leftChild;
        }

        if (!s.empty())
        {
            cur = s.top();
            s.pop();
            cout << cur->data << " ";
            cur = cur->rightChild;
        }
    }
}

前序遍历(非递归)

void BinTree::NotRePreOrder()
{
    stack<BTNode *> s;
    BTNode *cur = getRoot();
    s.push(cur);

    while (!s.empty())
    {
        cur = s.top();
        s.pop();

        cout << cur->data << " ";

        if (cur->rightChild)
        {
            s.push(cur->rightChild);
        }
        if (cur->leftChild)
        {
            s.push(cur->leftChild);
        }
    }
}

求二叉树结点个数的函数

int BinTree::BTreeSize(BTNode *cur)
{
    //二叉树的结点个数为左右子树的高度之和再+1
    if (!cur) return 0;
    else
        return 1 + BTreeSize(cur->leftChild) + BTreeSize(cur->rightChild);
}

求二叉树叶子结点个数的函数

int BinTree::BTreeLeaves(BTNode *cur)
{
    //当为空时，返回0；当找到叶子时返回1
    if (!cur) return 0;
    else if (!cur->leftChild && !cur->rightChild)
        return 1;
    else
        return BTreeLeaves(cur->leftChild) + BTreeLeaves(cur->rightChild);
}

求二叉树高度的函数

int BinTree::BTreeHeight(BTNode *cur)
{
    if (!cur) return 0;
    else
    {
        //二叉树的高度为左右子树的最大者+1
        int leftHei = BTreeHeight(cur->leftChild);
        int rightHei = BTreeHeight(cur->rightChild);
        return (leftHei > rightHei) ? leftHei + 1 : rightHei + 1;
    }
}

函数

void BinTree::Destory(BTNode **root)
{
    if ((*root) && (*root)->leftChild)
    {
        Destory(&(*root)->leftChild);
    }

    if ((*root) && (*root)->rightChild)
    {
        Destory(&(*root)->rightChild);
    }

    cout << (*root)->data << " ";
    delete (*root);
}

这代码虽然还是很low，而且子

---

哇，今天事情特别多。
是的，我回家了，回家了解了我家里各种状况之后，倍感生活之艰辛。

更多消息，请关注路人甲的学习记录