【C++二叉树创建和遍历】

学习内容：

分别用递归和非递归实现二叉树的先序，中序，后序遍历。 以及层序遍历。
二叉树的创建
先序：头左右
中序：左头右
后序：左右头
层序：按层遍历

要点：

递归方式遍历时，先序是第一次进入函数就打印，先打印的是头结点然后再打印左节点和右节点。中序是第一次回到函数时打印，此时左节点已经打印，当前打印的是头结点，之后再打印右节点。后序是第二次回到函数时打印，此时左右节点都已打印，当前打印的是头结点。
层序遍历用队列实现，先将头结点压入队列，然后出队时打印，先压左再压右。

                   1
                /      \
              2         3
            /   \      /
           4     5    6

此树的递归序为：1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，3，1
先序：1，2，4，5，3，6
中序：4，2，5，1，6，3
后序：4，5，2，6，3，1
层序：1，2，3，4，5，6

代码：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

struct Node
{
    int value;
    Node *left;
    Node *right;
    Node() : value(0), left(nullptr), right(nullptr) {}
    Node(int x) : value(x), left(nullptr), right(nullptr) {}
    Node(int x, Node *left, Node *right) : value(x), left(left), right(right) {}
};

/*
                    1
                 /      \
               2         3
             /   \      /
            4     5    6
*/
void creatBitree(Node *&node) //传入指针的引用(根节点)
{
    int in;
    cout << "int put: ";
    cin >> in; // 1  2  4 -1 -1  5 -1 -1  3  6 -1 -1 -1
    if (in == -1)
    {
        node = nullptr;
    }
    else
    {
        node = new Node(in);
        creatBitree(node->left);
        creatBitree(node->right);
    }
}

//递归遍历方式

void pre_order_recur(Node *head) //先序遍历
{
    if (head == nullptr)
    {
        return;
    }
    cout << head->value << " ";
    pre_order_recur(head->left);
    pre_order_recur(head->right);
}

void in_order_recur(Node *head) //中序遍历
{
    if (head == nullptr)
    {
        return;
    }
    in_order_recur(head->left);
    //运行到此处左节点已经打印了
    cout << head->value << " ";
    in_order_recur(head->right);
}

void post_order_recur(Node *head) //后序遍历
{
    if (head == nullptr)
    {
        return;
    }
    post_order_recur(head->left);
    post_order_recur(head->right);
    cout << head->value << " ";
}

//非递归方式
//弹栈顶，打印，先压右再压左
void pre_order_recur_stack(Node *head) //先序遍历
{
    if (head == nullptr)
    {
        return;
    }
    stack<Node *> stk;
    stk.push(head);
    while (!stk.empty())
    {
        head = stk.top();
        cout << head->value << " ";
        stk.pop();
        if (head->right)
        {
            stk.push(head->right);
        }
        if (head->left)
        {
            stk.push(head->left);
        }
    }
}

//把所有左边界压入栈中，直到左边界为空，弹出节点并打印，压入当前节点的右节点，然后再压左边界重复操作
void in_order_recur_stack(Node *head) //中序遍历
{
    if (head == nullptr)
    {
        return;
    }
    stack<Node *> stk;
    while (!stk.empty() || head)
    {
        if (head)
        {
            stk.push(head);
            head = head->left;
        }
        else
        {
            head = stk.top();
            stk.pop();
            cout << head->value << " ";
            head = head->right;
        }
    }
}

//双栈实现后序遍历
//栈1弹栈顶，压入栈2，栈1先压左再压右，栈2依次弹出
void post_order_recur_stack(Node *head) //后序遍历
{
    if (head == nullptr)
    {
        return;
    }
    stack<Node *> stk1;
    stk1.push(head);
    stack<Node *> stk2;
    while (!stk1.empty())
    {
        head = stk1.top();
        stk1.pop();
        stk2.push(head);
        if (head->left)
        {
            stk1.push(head->left);
        }
        if (head->right)
        {
            stk1.push(head->right);
        }
    }
    while (!stk2.empty())
    {
        head = stk2.top();
        stk2.pop();
        cout << head->value << " ";
    }
}

//层序遍历（宽度优先遍历） Tips：先序遍历是深度优先遍历

void wide_order(Node *head)
{
    if (!head)
    {
        return;
    }
    queue<Node *> que;
    que.push(head);
    while (!que.empty())
    {
        head = que.front();
        que.pop();
        cout << head->value << " ";
        if (head->left)
        {
            que.push(head->left);
        }
        if (head->right)
        {
            que.push(head->right);
        }
    }
}

int main()
{

    Node *root;
    creatBitree(root);

    //递归法
    cout << "递归法：" << endl
         << "先序遍历：";
    pre_order_recur(root);
    cout << endl
         << "中序遍历：";
    in_order_recur(root);
    cout << endl
         << "后序遍历：";
    post_order_recur(root);

    //栈法
    cout << endl
         << "栈法:" << endl
         << "先序遍历：";
    pre_order_recur_stack(root);
    cout << endl
         << "中序遍历：";
    in_order_recur_stack(root);
    cout << endl
         << "后序遍历：";
    post_order_recur_stack(root);

    //层序遍历
    cout << endl
         << endl
         << "层序遍历：";
    wide_order(root);
    return 0;
}

---

结果：

应用：

折纸问题：一张纸条，从下往上折对折N次，从上往下依次打印折痕内凹和外凸的顺序。

#include <iostream>
using namespace std;

//每次折纸，上一次的折痕上方会出现凹，下方出现凸。为满二叉树形式，折痕从上往下的顺序为二叉树中序遍历顺序。
void zhezhi(int N, bool isleft)
{
    if (N == 0)
    {
        return;
    }
    zhezhi(N - 1, true); //进左树，标记为true
    cout << (isleft ? "凹" : "凸") << "  ";
    zhezhi(N - 1, false); //进右树，标记为false
}

int main()
{
    int N = 3; //对折次数
    cout << "对折次数为 " << N << " 时,折痕为: " << endl;
    bool isleft = true; //是否为左子树，是为 true 否为 false
    zhezhi(N, isleft);
    return 0;
}

运行结果：