二叉树的创建和遍历，递归和非递归实现

类别: 默认类别

本文介绍了二叉树的最大权重之和

本文最初由当地帅哥金田大神创作. 版权所有. 欢迎转载. 但是请保留此版权信息，感谢您的合作. 如有任何疑问，请通过微信与我联系: jintianiloveu

如果以递归方式遍历二叉树递归创建二叉树，则非常简单，只需选择一个即可在前顺序和后顺序中遍历. 让我们创建一个二叉树并查看:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
struct BiTreeNode {
    int data;
    BiTreeNode *left_child;
    BiTreeNode *right_child;
};
void create_tree(BiTreeNode* &tree) {
    int data;
    cin >> data;
    if (data != '\n') {
        if (data == -1) {
            tree = nullptr;
        } else {
            tree = new BiTreeNode;
            tree->data = data;
            create_tree(tree->left_child);
            create_tree(tree->right_child);
        }
    }
}

例如，我们有这样的二叉树:

      2
    /   \
  3      4
  /
5

这么简单的二叉树递归创建二叉树，一次输入:

2 3 5 -1 -1 -1 4 -1 -1

请注意，首先输入所有左边的子树，然后输入右边的子树，并且没有左右子级用-1表示. 这时树就建好了. 然后我们遍历序列:

void pre_order_traverse(BiTreeNode* &tree) {
    // 先序遍历
    if (tree) {
        cout << tree->data << " ";
        pre_order_traverse(tree->left_child);
        pre_order_traverse(tree->right_child);
    }
}

结果是:

2 3 5 4

它没有错，按顺序遍历:

void in_order_traverse(BiTreeNode* &tree) {
    // 中序遍历
    if (tree) {
        in_order_traverse(tree->left_child);
        cout << tree->data << " ";
        in_order_traverse(tree->right_child);
    }
}

结果是:

5 3 2 4

最重要的是，我们如何实现二叉树的非递归遍历？

void pre_order_traverse_no_recurse(BiTreeNode* &tree) {
    // 非递归先序遍历二叉树
    stack<BiTreeNode*> s;
    BiTreeNode *p = tree;
    // 当栈非空或者p指针非空时调用循环
    while (p != nullptr || !s.empty()) {
        while ( p != nullptr) {
            cout << p->data << " ";
            s.push(p);
            p = p->left_child;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            p = p->right_child;
        }
    }
}

非递归的遍历遍历，非常容易理解: 首先，我们必须沿着左子树从根节点遍历. 此时，p遍历每个遍历，这对于在遍历左侧子树之后的遍历非常方便. 换句话说，它分为两个阶段. 第一级穿过左侧. 这是预遍历的基本原理. 它首先跟随节点，然后跟随左子树. 最后，如果堆栈不为空，则将先前的节点逐个从堆栈中删除. 取出顶部，然后取一个，然后扔一个，得到右边的节点，右边的节点也将执行左边的子树操作，最后完成非递归遍历.

非递归遍历的中间顺序遍历实现也类似:

void in_order_traverse_no_recurse(BiTreeNode* &tree) {
    stack<BiTreeNode*> s;
    BiTreeNode *p = tree;
    while (p != nullptr || !s.empty()) {
        while ( p != nullptr) {
            s.push(p);
            p = p->left_child;
        }
        if (!s.empty()) {
            p = s.top();
            cout << p->data << " ";
            s.pop();
            p = p->right_child;
        }
    }
}

好的，可怕的二叉树遍历算法到此结束. 实际上，很多时候您并不真正希望编写完全正确的二叉树或遍历操作. 至少您必须学习这个想法，最重要的是如何使用堆栈来模拟递归.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-221864-1.html