二叉树常见操作的 C++ 实现(一)

本节主要讲述二叉树中常见操作的 C++ 实现，重点是代码的实现，不拘泥于一种方法。
后续会根据做的一些题增加树的其他操作，并在个人的 github 持续更新中。

---

---

本部分基本涵盖了二叉树的基本操作，后续新增内容会在个人的 github 上持续更新。
此处对于二叉树的基本概念就不做赘述了，聚焦于代码上的实现。

二叉树的创建

首先，c++ 文件的基本结构走起来。

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    return 0;
}

之后，考虑二叉树的节点，为了泛用性，可以使用 typedef。

typedef string ElemType;

这里我们使用 string 类型作为节点类型，当然你也可以自定义其他类型。

然后定义树的节点，显然，根据树的定义，我们需要一个数据域 data 和两个节点类型的指针域 left 和 right，分别指向其左子树和右子树，使用 struct 类型即可。
完成这些后，我们在结构体里创建一个给节点数据域赋值的构造函数，其指针域都默认为空。
结构如下：

typedef string ElemType;

//定义树的节点
typedef struct BinaryNode{
    //节点
    ElemType data;
    //左子树
    BinaryNode* left;
    //右子树
    BinaryNode* right;
    BinaryNode(ElemType value){
        data = value;
        left = NULL;
        right = NULL;
    }
}BinaryNode,*BiTree;

接下来，我们定义一个二叉树类，其私有成员部分有树根节点 mRoot ，节点总数(可有可无) size ，相关成员函数，共有成员部分也有相关成员函数。
二叉树的类如下：

//二叉树
class BinaryTree{
private:
    //根节点
    BiTree mRoot;
    //节点总数
    int size;
    //按前序遍历方式递归创建二叉树
    BiTree create();
    //递归实现前序遍历
    void preOrder(BiTree root);
    //非递归实现前序遍历
    void nonRec_preOrder(BiTree root);
    //递归实现中序遍历
    void inOrder(BiTree root);
    //非递归实现中序遍历
    void nonRec_inOrder(BiTree root);
    //递归实现后序遍历
    void postOrder(BiTree root);
    //非递归实现后序遍历
    void nonRec_postOrder(BiTree root);
    //非递归实现层次遍历
    void nonRec_levelOrder(BiTree root);
    //递归实现摧毁树(前序遍历)
    void destroy(BiTree root);
    //递归得到树的节点数
    int getSize(BiTree root);
    //递归得到树的高度
    int getHeight(BiTree root);
    //得到叶子节点的个数
    int getLeafs(BiTree root);
    //得到度为1的节点个数
    int getOneLeafs(BiTree root);
    //得到满节点个数
    int getFullLeafs(BiTree root);
    //获取第 k 层的节点数
    int getLevelSize(BiTree root,int level);
    //查找指定值的节点
    BiTree findNode(BiTree root,ElemType value);

public:
    //按前序遍历方式递归创建二叉树
    void createTree();
    //递归实现前序遍历
    void preOrder();
    //非递归实现前序遍历
    void nonRec_preOrder();
    //递归实现中序遍历
    void inOrder();
    //非递归实现中序遍历
    void nonRec_inOrder();
    //递归实现后序遍历
    void postOrder();
    //非递归实现后序遍历
    void nonRec_postOrder();
    //递归实现层次遍历
    void nonRec_levelOrder();
    //递归实现摧毁树(前序遍历)
    void destroy();
    //递归得到树的节点数
    int getSize();
    //递归得到树的高度
    int getHeight();
    //得到叶子节点的个数
    int getLeafs();
    //得到度为1的节点个数
    int getOneLeafs();
    //得到满节点个数
    int getFullLeafs();
    //获取第 k 层的节点数
    int getLevelSize(int level);
    //判断是否为完全二叉树
    bool isCompleteTree();
    //查找指定值的节点
    BiTree findNode(ElemType value);

};

后续继续增加一些功能，本系列的任务先实现上面给出所有的操作。

我们先来看按前序遍历方式递归创建二叉树，
私有函数部分：

void preOrder(BiTree root);

共有函数部分：

//按前序遍历方式递归创建二叉树
void createTree();

之后的操作基本上都分为相应的私有函数部分和共有函数部分，
同时一个功能的实现先给出私有函数部分，再给出其共有函数部分。

来看创建，我们使用的是前序遍历的方式，空节点使用 "#" (因为输入的是字符串类型)。
首先呢，我们创建型节点 newNode ，若输入的值为 "#" ，则返回为空，因为是空节点。
然后将输入的值 value 赋予新节点的数据域，最后递归创建该节点 newNode 的左子树和右子树。
代码如下：

//按前序遍历方式递归创建二叉树
BiTree BinaryTree::create(){
    BiTree newNode = NULL;
    ElemType value;
    //此处 ElemType 应该是基本类型数据,若为自定义类型,请重载输入流
    cin>>value;
    //# 表示当前子树为空
    if(value == "#"){
        return NULL;
    }else{
        //递归创建左右子树,使用 size 记录下树的节点树
        size++;
        newNode = new BinaryNode(value);
        newNode->left = create();
        newNode->right = create();
        return newNode;
    }
}
void BinaryTree::createTree(){
    size = 0;
    mRoot = create();
}

这样一棵树就已经创建好了，当然树的创建方式有很多，这里只列举了一种，之后还会增加其他方式。
来测试下吧：

int main(){
    BinaryTree tree;
    cout<<"Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:"<<endl;
    //"A B D G # # H # # # C E # I # # F # #";
    tree.createTree();
    cout<<&tree<<endl;
    return 0;
}

打印的结果为：

Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:
A B D G # # H # # # C E # I # # F # #
0x62fe10

&tree 的内容可能有所不同，有结果，说明这棵树已经创建成功了！

树的遍历(递归 + 非递归)

在创建一棵树后，我们总想看看树里面有什么内容，那就遍历嘛。
树的遍历常见的有四种，前序遍历，中序遍历，后序遍历，层次遍历。
前三种既可以使用递归方法，也可以使用非递归。
层序遍历就是非递归了。
非递归过程中会用到 栈与队列 ，DFS 和 BFS 等概念。

前序遍历(递归 + 非递归)

先来看前序遍历的，前序遍历的顺序是根节点，左子树，右子树。
递归方法很简单，代码如下：

//递归实现前序遍历
void BinaryTree::preOrder(BiTree root){
    if(root != NULL){
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}
void BinaryTree::preOrder(){
    cout<<"The result of the preorder traversal is "<<endl;
    preOrder(mRoot);
    cout<<endl;
}

非递归需要用到 栈 的思想，和非递归遍历思想类似。我们还需要用栈保存节点，并访问数据域。
具体的代码如下：

//非递归实现前序遍历
void BinaryTree::nonRec_preOrder(BiTree root){
    if(root == NULL){
        return ;
    }
    stack<BiTree> s;
    BiTree p = root;
    s.push(p);
    while(!s.empty()){
        BiTree node = s.top();
        cout<<node->data<<" ";
        s.pop();
        if(node->right){
            s.push(node->right);
        }
        if(node->left){
            s.push(node->left);
        }
    }
}
void BinaryTree::nonRec_preOrder(){
    cout<<"The result of the non-recursive preorder traversal is "<<endl;
    nonRec_preOrder(mRoot);
    cout<<endl;
}

测试部分等四种遍历讲完后统一给出。

中序遍历(递归 + 非递归)

先来看中序遍历的，中序遍历的顺序是左子树，根节点，右子树。
递归方法很简单，代码如下：

//递归实现中序遍历
void BinaryTree::inOrder(BiTree root){
    if(root != NULL){
        inOrder(root->left);
        cout<<root->data<<" ";
        inOrder(root->right);
    }
}
void BinaryTree::inOrder(){
    cout<<"The result of the in-order traversal is "<<endl;
    inOrder(mRoot);
    cout<<endl;
}

在之前的非递归前序遍历的基础上，中序遍历也就不难了。
具体代码如下：

//非递归实现中序遍历
void BinaryTree::nonRec_inOrder(BiTree root){
    if(root == NULL){
        return ;
    }
    stack<BiTree> myStack;
    BiTree rt = root;
    while(rt != NULL || !myStack.empty()){
        while(rt != NULL){
            myStack.push(rt);
            rt = rt->left;
        }
        rt = myStack.top();
        myStack.pop();
        cout<<rt->data<<" ";
        rt = rt->right;
    }
}
void BinaryTree::nonRec_inOrder(){
    cout<<"The result of the non-recursive in-order traversal is "<<endl;
    nonRec_inOrder(mRoot);
    cout<<endl;
}

后序遍历(递归 + 非递归)

先来看后序遍历的，后序遍历的顺序是左子树，右子树，根节点。
递归方法很简单，代码如下：

//递归实现后序遍历
void BinaryTree::postOrder(BiTree root){
    if(root != NULL){
        postOrder(root->left);
        postOrder(root->right);
        cout<<root->data<<" ";
    }
}
void BinaryTree::postOrder(){
    cout<<"The result of the postorder traversal is "<<endl;
    postOrder(mRoot);
    cout<<endl;
}

仿照之前的非递归遍历，后序遍历的非递归的具体代码如下：

//非递归实现后序遍历,双栈法
/*
    栈 s1 入栈顺序：根节点-> 左节点-> 右节点
    栈 s2 入栈顺序：右节点-> 左节点-> 根节点
    出栈顺序：根节点-> 左节点-> 右节点
*/
void BinaryTree::nonRec_postOrder(BiTree root){
    if(root == NULL){
        return ;
    }
    stack<BiTree> s1;
    stack<BiTree> s2;
    s1.push(root);
    while(!s1.empty()){
        BiTree p = s1.top();
        s1.pop();
        s2.push(p);
        if(p->left){
            s1.push(p->left);
        }
        if(p->right){
            s1.push(p->right);
        }
    }
    while(!s2.empty()){
        cout<<s2.top()->data<<" ";
        s2.pop();
    }
}
void BinaryTree::nonRec_postOrder(){
    cout<<"The result of the non-recursive postorder traversal is "<<endl;
    nonRec_postOrder(mRoot);
    cout<<endl;
}

层次遍历

层次遍历需要用到队列保存每一层的节点，一层层地访问，它不需要用到递归。
具体代码如下：

//非递归实现层次遍历
void BinaryTree::nonRec_levelOrder(BiTree root){
    queue<BiTree> q;
    q.push(root);
    while(!q.empty()){
        //每层的节点
        int num_level = q.size();
        while(num_level--){
            BiTree node = q.front();
            q.pop();
            cout<<node->data<<" ";
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
    }
}
void BinaryTree::nonRec_levelOrder(){
    cout<<"The result of the non-recursive sequence traversal is "<<endl;
    nonRec_levelOrder(mRoot);
    cout<<endl;
}

汇总

我们来创建一棵树，并使用上面的方法分别遍历这棵树。
测试代码如下：

int main(){
    BinaryTree tree;
    cout<<"Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:"<<endl;
    //"A B D G # # H # # # C E # I # # F # #";
    tree.createTree();
    cout<<&tree<<endl;
    //前序遍历
    tree.preOrder();
    //非递归前序遍历
    tree.nonRec_preOrder();
    //中序遍历
    tree.inOrder();
    //非递归中序遍历
    tree.nonRec_inOrder();
    //后序遍历
    tree.postOrder();
    //非递归后序遍历
    tree.nonRec_postOrder();
    //非递归层次遍历
    tree.nonRec_levelOrder();
    return 0;
}

打印的结果如下：

Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:
A B D G # # H # # # C E # I # # F # #
0x62fe10
The result of the preorder traversal is
A B D G H C E I F
The result of the non-recursive preorder traversal is
A B D G H C E I F
The result of the in-order traversal is
G D H B A E I C F
The result of the non-recursive in-order traversal is
G D H B A E I C F
The result of the postorder traversal is
G H D B I E F C A
The result of the non-recursive postorder traversal is
G H D B I E F C A
The result of the non-recursive sequence traversal is
A B C D E F G H I

结果和我们画的树是一致的。

本节的内容就到这里了，之后继续实现其他的功能。