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

接着之前的内容，本节继续讲述二叉树中常见操作的 C++ 实现。

---

---

上节，我们介绍并实现了二叉树的按前序遍历创建和递归与非递归的各种遍历操作，本节我们继续实现之前二叉树类中其他的成员函数。
回顾之前的二叉树类：

//二叉树
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 BinaryTree::destroy(BiTree root){
    if(root != NULL){
        destroy(root->left);
        destroy(root->right);
        free(root);
        size = 0;
    }
}
void BinaryTree::destroy(){
    size = 0;
    destroy(mRoot);
}

我们先把这些操作都实现了，再统一测试吧。

统计二叉树的节点

在统计二叉树的节点时，当一个节点为空，说明它数据域的内容为 "#" ，也就是空，就不算一个节点了，返回为0；如果不为空，此处是一个节点，加一之后继续递归其左子树和右子树的和。
具体代码如下：

//递归得到树的节点数
int BinaryTree::getSize(BiTree root){
    int num = 0;
    if(root == NULL){
        return 0;
    }else{
        num = 1 + getSize(root->left) + getSize(root->right);
    }
    return num;
}
int BinaryTree::getSize(){
    //或者  return getSize(mRoot);
    return size;
}

计算二叉树的高度

计算高度，如果一个节点为空，高度就为 0 了；反之，递归其左子树和右子树，返回两者最大值加一即可。
具体的代码如下：

//递归得到树的高度
int BinaryTree::getHeight(BiTree root){
    if(root == NULL){
        return 0;
    }
    int l = getHeight(root->left);
    int r = getHeight(root->right);
    return max(l,r)+1;
}
int BinaryTree::getHeight(){
    return getHeight(mRoot);
}

统计叶子节点个数

当一个节点为空时，返回为 0 ；当左节点和右节点都为空时，是叶子节点，返回为 1 ；否则继续递归统计其左子树和右子树的和。
具体代码如下：

//得到叶子节点的个数
int BinaryTree::getLeafs(BiTree root){
    int num = 0;
    if(root == NULL){
        return 0;
    }else if(root->left == NULL && root->right == NULL){
        return 1;
    }else{
        num = getLeafs(root->left) + getLeafs(root->right);
    }
    return num;
}
int BinaryTree::getLeafs(){
    return getLeafs(mRoot);
}

统计度为1的节点个数

当节点为空，或者其左右子树都为空时，返回为0；若有一个子树不为空，加一，同时递归另一个子树；若都不为空，递归其左右子树的和。
具体代码如下：

//得到度为1的节点个数
int BinaryTree::getOneLeafs(BiTree root){
    int num = 0;
    if(root == NULL){
        return 0;
    }else if(root->left == NULL && root->right == NULL){
        return 0;
    }else if((root->left != NULL)&&(root->right == NULL)){
        num = 1 + getOneLeafs(root->left);
    }else if((root->left == NULL)&&(root->right != NULL)){
        num = 1 + getOneLeafs(root->right);
    }else{
        num = getOneLeafs(root->left) + getOneLeafs(root->right);
    }
    return num;
}
int BinaryTree::getOneLeafs(){
    return getOneLeafs(mRoot);
}

统计满节点个数

只有节点的左右子树都不为空时，才加一，继续递归其左右子树的和。
具体代码如下：

//得到满节点个数,和统计一度节点个数类似,也可以通过节点数计算出来
int BinaryTree::getFullLeafs(BiTree root){
    int num = 0;
    if(root == NULL){
        return 0;
    }else if(root->left == NULL && root->right == NULL){
        return 0;
    }else if(root->left != NULL && root->right == NULL){
        num = getFullLeafs(root->left);
    }else if(root->left == NULL && root->right != NULL){
        num = getFullLeafs(root->right);
    }else{
        num = 1 + getFullLeafs(root->left) + getFullLeafs(root->right);
    }
    return num;
}
int BinaryTree::getFullLeafs(){
    return getFullLeafs(mRoot);
}

获取第 k 层的节点数

当节点为空时，返回为 0 ；当层数减为一时，表示该节点在相应的层，返回为 1 ；否则继续递归其左子树下一层和右子树下一层的节点数和。
具体代码如下：

//获取第 k 层的节点数
int BinaryTree::getLevelSize(BiTree root,int level){
    if(root == NULL){
        return 0;
    }
    if(level == 1){
        return 1;
    }
    return getLevelSize(root->left,level-1) + getLevelSize(root->right,level-1);
}
int BinaryTree::getLevelSize(int level){
    return getLevelSize(mRoot,level);
}

判断是否为完全二叉树

完全二叉树没有一度节点，此时需要一个队列来保存节点信息，判断每个节点的左右子树是否都存在或者都为空，满足节点的入队列，继续判断。
具体代码如下：

//判断是否为完全二叉树
bool BinaryTree::isCompleteTree(){
    queue<BiTree> q;
    if(mRoot){
        q.push(mRoot);
    }
    bool res = true;

    while(!q.empty()){
        BiTree front = q.front();
        q.pop();
        if(front->left){
            if(!res){
                return res;
            }
            q.push(front->left);
        }else{
            res = false;
        }
        if(front->right){
            if(!res){
                return res;
            }
            q.push(front->right);
        }else{
            res = false;
        }
    }
    return true;
}

查找指定值的节点

若当前节点为空，返回为空；若该节点的数据域与待查找的值一致，返回该节点；否则递归左子树，右子树，在节点不为空的情况下，判断节点的值与带查找的值是否一致。
具体代码如下：

//查找指定值的节点
BiTree BinaryTree::findNode(BiTree root,ElemType value){
    BiTree node = NULL;
    if(root == NULL){
        return root;
    }
    if(root->data == value){
        return root;
    }else{
        node = findNode(root->left,value);
        if(node != NULL){
            if(node->data == value){
                return node;
            }
        }
        node = findNode(root->right,value);
    }
    return node;
}
BiTree BinaryTree::findNode(ElemType value){
    return findNode(mRoot,value);
}

汇总

我们来测试所有的功能吧。
具体代码如下：

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<<"The height of the tree is "<<tree.getHeight()<<endl;
    cout<<"The number of nodes in the tree is "<<tree.getSize()<<endl;
    cout<<"The number of leaf nodes in the tree is "<<tree.getLeafs()<<endl;
    cout<<"The number of nodes with a tree degree of 1 is "<<tree.getOneLeafs()<<endl;
    cout<<"The number of full nodes in the tree is "<<tree.getFullLeafs()<<endl;
    cout<<"Please input the value : ";
    ElemType value;
    cin>>value;
    if(tree.findNode(value)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    cout<<"Whether the tree is fully binary?"<<endl;
    if(tree.isCompleteTree()){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    //前序遍历
    tree.preOrder();
    //非递归前序遍历
    tree.nonRec_preOrder();
    //中序遍历
    tree.inOrder();
    //非递归中序遍历
    tree.nonRec_inOrder();
    //后序遍历
    tree.postOrder();
    //非递归后序遍历
    tree.nonRec_postOrder();
    //非递归层次遍历
    tree.nonRec_levelOrder();
    //摧毁树
    tree.destroy();
    cout<<"destory the tree......"<<endl;
    cout<<"The number of nodes in the tree is "<<tree.getSize()<<endl<<endl;
    return 0;
}

测试的结果如下:

图片.png 图片.png

所有的代码位于个人的 github 上。
至此，二叉树常见操作的实现就暂告一段落了，后续还会继续更新。