C++ 二叉树的构建和遍历-JZTXT

二叉树算是一个常见的数据结构了。从纸面上理解二叉树不难，关键是二叉树如何再代码中实现？比如如何构建二叉树？二叉树的递归与非递归遍历？如何根据遍历的顺序确定一个二叉树？

//二叉树节点的定义 一个结构体外加左右子树，存储一个int类型的数据，还有别忘了初始化。
typedef struct list_tree
{
    int val;
     list_tree* left_ch;
     list_tree* right_ch;
     list_tree(int x) :val(x),left_ch(nullptr),right_ch(nullptr){}
};

二叉树单独的节点有了，下面就是在计算里面构造出来这个结构。

我们向计算机输入的是一组这样的二叉树数据，比如{1，2，3，4，5，6，7} ，我们的脑海中，二叉树是这样的

但对计算机而言，这就是一个数组{1，2，3，4，5，6，7}，存储在数组结构中的，计算机怎么知道哪个数据对应哪个节点呢？这就需要我们自己定义一个根据输入数组确定二叉树的函数。

（默认我们输入的数据按照二叉树层级的关系排序。就是广度优先遍历的顺序，广度优先遍历简称BFS)

代码：

list_tree* build_tree(std::vector<int>& nums)//-1为空
{
    if (nums.empty()) return nullptr;
    list_tree* root = new list_tree(nums.front());//根为数组内第一个元素

    std::queue<list_tree*> q;
    q.push(root);//临时存放树节点的数组
    int i = 1;//元素计数

    while (i < nums.size())//构造树
    {
        list_tree* cur = q.front();
        
        if (i < nums.size())
        {
            cur->left_ch = new list_tree(nums[i++]);
            q.push(cur->left_ch);
        }
        if (i < nums.size())
        {
            cur->right_ch = new list_tree(nums[i++]);
            q.push(cur->right_ch);
        }
        q.pop();
    }

    return root;
}
//补充个细节，这里没有销毁临时使用的queue容器，如果想要清空，请把在最后把它赋值为空或者在他为空之前不停的pop（）
//这么做的原因是在你构建了一个超级超级大的二叉树的时候，queue存储了树最后一层的所有元素，虽然函数执行完之后会自动释放queue里面的东西，但是多函数同时运行就会占用超大量的内存空间。
//而且，假如我么将queue定义为静态的，构造多个树的时候，就不用不停的开辟出新的queue然后销毁，再开辟，再销毁。这时候手动释放其内存就很有必要。不过若多函数同时运行的话，就需要加上互斥锁了，不然会乱的

解释下原理，首先，判断是不是空树，是就返回nullptr，不是就开始造二叉树，造二叉树过程我们需要借助一个叫做队列的结构（STL内的queue）。

造树第一步，找根节点。这里我们的根节点就是数组里的第一个数1，好了，根节点root有了。

把这个根节点压入队列。现在队列里面有一个节点了，我们就要对这个队列内的第一个节点进行操作，就是补充此第一个节点的左孩子和右孩子，补充的同时也把补充进去的节点压入队列里面，然后出队第一个元素，无限重复这个操作直到所有数据均已进入二叉树（即数组内的数据遍历完成）。

举个例子，假设我们构造的树为{1，2，3}，根节点就是1，那么节点1进入队列；开始补充1的左孩子2，节点2入队列，补充1的右孩子3，3进入队列，出队节点1；

假如2有孩子，下一个补充的就会是2的左右孩子，出队节点2，这个顺序是不会乱的。

有了构造二叉树的函数，我们就要讨论下二叉树的遍历了。就是前，中，后序的非递归以及递归方法，还有深度优先（DFS),广度优先（BFS）;

关于递归方式的前中后序遍历很简单，因为对于每个节点来说，除了它本身的值，只有两个左右孩子，只要从根节点开始，递归它的左右子孩子，就能完整的遍历整个树。

而它前序，中序，后序，就是每次递归时，输出值语句位置不同而造成的。

将他的顺序打印出来，就可以得到这些遍历顺序的规律

先序：根左右

中序：左根右

后续：左右根

代码如下

//先序遍历递归
void xianxubianlidg(list_tree* root) {
    
    if (root == nullptr) return;
    
    std::cout<<root->val<<",";
    xianxubianlidg(root->left_ch);
    xianxubianlidg(root->right_ch);
}
//中序遍历递归
void zhongxubianlidg(list_tree* root)
{
    if (root == nullptr) return;

    zhongxubianlidg(root->left_ch);
    std::cout << root->val << ",";
    zhongxubianlidg(root->right_ch);
}
//后序遍历递归
void houxubianlidg(list_tree* root)
{
    if (root == nullptr) return;

    houxubianlidg(root->left_ch);
    houxubianlidg(root->right_ch);
    std::cout << root->val << ",";
}

为了深入理解这些遍历顺序，最好实现一下非递归遍历的方式

代码如下

//非递归先,中，后序遍历
void xianxu(list_tree* root)
{
    if (root==nullptr) return;

    std::stack<list_tree*> xx;
    list_tree* bl;
    bl = root;
    while (!xx.empty() || bl)
    {
        if (bl)
        {
            std::cout << bl->val<<",";
            xx.push(bl);
            bl = bl -> left_ch;
        }
        else
        {
            bl = xx.top();
            xx.pop();
            bl = bl->right_ch;
        }
    }


}
void zhongxu(list_tree* root)
{
    if (root==nullptr) return;

    list_tree* bl = root;
    std::stack<list_tree*> zx;
    while (!zx.empty() || bl)
    {
        if (bl) {
            zx.push(bl);
            bl = bl->left_ch;
        }
        else {
            bl = zx.top();
            std::cout << zx.top()->val<<",";
            bl = zx.top()->right_ch;
            zx.pop();
        }
    }
}
void houxu(list_tree* root)
{
    if (root == nullptr) return;

    std::stack<list_tree*> s1;
    std::stack<list_tree*> s2;
    s1.push(root);


    while (!s1.empty())
    {
        root = s1.top();
        s1.pop();
        s2.push(root);

        if (root->left_ch != nullptr)
        {
            s1.push(root->left_ch);
        }
        if (root->right_ch != nullptr)
        {
            s1.push(root->right_ch);
        }
    }
    while (!s2.empty())
    {
        std::cout << s2.top()->val << ",";
        s2.pop();
    }

咋一直是草稿，我是不是忘写点啥？？想起来再说！