【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;
}

运行结果:
在这里插入图片描述