C++实现二叉树的创建以及四种遍历方式（递归与非递归）

语言这个东西不用真的会忘， 我记得前前后后C++的基本语法我也看了好几遍了，一直没有动手写过什么东西，所以一遍遍的看，一遍遍的忘... ...

正好最近在看数据结构，想着自己用C++来实现一下，一方面是熟悉整个逻辑过程，加深对数据结构的理解，另一方面，也熟悉一下C++。

下图是我们要创建的二叉树，其中的#代表空字符；

二叉树

为了验证我们程序的正确性，现给出此二叉树的四种遍历结果：

前序遍历（Preorder traversal）： A B C D E F G H I J

中序遍历（Inorder traversal）： C D B F E A I H G J

后序遍历（Postorder traversal）：D C F E B I H J G A

层序遍历（Levelorder traversal）：A B G C E H J D F I

此二叉树中，共有结点10个；深度为4；叶子结点格式为4，分别为D,F,I,J.

二叉树节点的结构体定义

struct Node {
    char data;
    Node* lchild, * rchild;
    Node() = default;
    explicit Node(char data) : data(data) { lchild = nullptr; rchild = nullptr; }
    Node(char data, Node* left, Node* right) : data(data), lchild(left), rchild(right) {}
};

using BiTree = Node*; //起别名

创建二叉树（递归，通过前序遍历创建）

void create(BiTree& node) {
    char ch;
    cin >> ch;
    if (ch == '#') // '#' => null character
        node = nullptr;
    else {
        node = new Node;
        node->data = ch;
        create(node->lchild); //递归
        create(node->rchild);
    }
}

要创建上图所示的二叉树，我们要输入它的前序遍历：ABC#D##EF###GHI###J##

前序遍历、中序遍历以及后序遍历（递归实现）

// 递归：实现前序遍历 DLR

void preTraversal(BiTree root) {
    if (root == nullptr) {
        return;
    }
    cout << root->data << " ";
    preTraversal(root->lchild);
    preTraversal(root->rchild);
}

// 递归：实现中序遍历 LDR

void inTraversal(BiTree root) {
    if (root == nullptr) {
        return;
    }
    inTraversal(root->lchild);
    cout << root->data << " ";
    inTraversal(root->rchild);
}

// 递归：实现后序遍历 LRD

void postTraversal(BiTree root) {
    if (root == nullptr) {
        return;
    }
    postTraversal(root->lchild);
    postTraversal(root->rchild);
    cout << root->data << " ";
}

层序遍历

// 层序遍历

void LevelorderTraversal(BiTree root) {
    if (root == nullptr)
        return;  
    queue<BiTree> que; 
    que.push(root);
    while (!que.empty()) {  
        auto node = que.front();
        que.pop();
        cout << node->data << " ";  ;
        if (node->lchild != nullptr)
            que.push(node->lchild);
        if (node->rchild != nullptr)
            que.push(node->rchild);
    }
}

前序遍历、中序遍历以及后序遍历（非递归实现）

//非递归：实现二叉树的中序遍历

void InOrderTranversal(BiTree root) {
    BiTree cur = root;
    stack<BiTree> cs;
    while (cur || !cs.empty()) {
        if (cur != nullptr) {
            cs.push(cur);
            cur = cur->lchild;
        }
        else {
            cur = cs.top();
            cs.pop();
            cout << cur->data << " ";
            cur = cur->rchild;
        }
    }
}

// 非递归：实现二叉树的前序遍历

void PreOrderTranversal(BiTree root) {
    vector<char> result;
    stack<BiTree> st;
    if (root == nullptr)
        return;
    st.push(root);
    while (!st.empty()) {
        auto node = st.top(); //node类型为BiTree,也就是Node*
        st.pop();
        result.push_back(node->data);
        if (node->rchild != nullptr)
            st.push(node->rchild);
        if (node->lchild != nullptr)
            st.push(node->lchild);
    }
    Print(result);
}

// 非递归：实现二叉树的后序遍历

void PostOrderTranversal(BiTree root) {
    vector<char> result;
    stack<BiTree> st;
    if (root == nullptr)
        return;
    st.push(root);
    while (!st.empty()) {
        auto node = st.top();
        st.pop();
        result.push_back(node->data);
        if (node->lchild != nullptr)
            st.push(node->lchild);
        if (node->rchild != nullptr)
            st.push(node->rchild);
    }
    reverse(result.begin(), result.end());
    Print(result);
}

计算二叉树的深度

int getDepth(BiTree root) {
    if (root == nullptr)
        return 0;
    return max(getDepth(root->lchild), getDepth(root->rchild)) + 1;
}

计算二叉树中的结点个数

int getNodeCount(BiTree root) {
    if (root == nullptr) {
        return 0;
    }
    int l = getNodeCount(root->lchild);
    int r = getNodeCount(root->rchild);
    int count = l + r + 1;
    return count;
}

计算二叉树叶子结点的个数

int getLeafNodeCount(BiTree root) {
    if (root == nullptr)
        return 0;
    if (root->lchild == nullptr && root->rchild == nullptr)
        return 1;
    return getLeafNodeCount(root->lchild) + getLeafNodeCount(root->rchild);
}

测试代码

/*
 * Software:Visual Studio 2022 Community
 * Created by xiaoxin_zh@foxmail.com
 * Implementing Binary Tree with C++
 */

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>

using std::cin;
using std::cout;
using std::endl;
using std::stack;
using std::vector;
using std::queue;
using std::max;

int main() {
    BiTree T;
    cout << "Please enter the data of the node, # stands for empty : "; //ABC#D##EF###GHI###J##
    create(T);
    cout << "Created successfully!" << endl;
    cout << "===========Preorder traversal=========== " << endl;
    preTraversal(T);
    cout << endl;
    cout << "===========Inorder traversal=========== " << endl;
    inTraversal(T);
    cout << endl;
    cout << "===========Postorder traversal=========== " << endl;
    postTraversal(T);
    cout << endl;
    cout << "************Preorder traversal************" << endl;
    PreOrderTranversal(T);
    cout << endl;
    cout << "************Inorder traversal************" << endl;
    InOrderTranversal(T);
    cout << endl;
    cout << "************Postorder traversal************" << endl;
    PostOrderTranversal(T);
    cout << endl;
    cout << "************Leverlorder traversal************" << endl;
    LevelorderTraversal(T);
    cout << endl;
    cout << "The number of nodes in the binary tree is " << getNodeCount(T) << "." << endl;
    cout << "The depth of the binary tree is " << getDepth(T) << "." << endl;
    cout << "The number of leaf nodes in the binary tree is " << getLeafNodeCount(T) << "." << endl;
    return 0;
}

执行结果

执行结果

以上代码均已通过测试，如果有问题请大家指出，我及时修改，以免造成误导~

by xiaoxin_zh

2022/5/23