遍历二叉树
跟数组不同，树是一种非线性的数据结构，是由n（n >=0）个节点组成的有限集合。如果n==0，树为空树。如果n>0，树有一个特定的节点，叫做根节点（root）。
对于树这种数据结构，使用最频繁的是二叉树。每个节点最多只有2个子节点的树，叫做二叉树。二叉树中，每个节点的子节点作为根的两个子树，一般叫做节点的左子树和右子树。
我们可以为树的节点定义一种结构体类型，而且为了方便以后在不同的文件中使用，还可以自定义一个头文件tree_node.h，将结构体TreeNode的定义放在里面：
#pragma once
#include<string>
using namespace std;
struct TreeNode
{
string name;
TreeNode* left;
TreeNode* right;
};
在别的文件中，如果想要使用TreeNode这个结构体，我们只要引入就可以：
#include "TreeNode.h"
对于树的遍历，主要有这样三种方式：
l 先序遍历：先访问根节点，再访问左子树，最后访问右子树；
l 中序遍历：先访问左子树，再访问根节点，最后访问右子树；
l 后序遍历：先访问左子树，再访问右子树，最后访问根节点。
这种遍历方式就隐含了“递归”的思路：左右子树本身又是一棵树，同样需要按照对应的规则来遍历。
我们可以先单独创建一个文件print_tree.cpp，实现二叉树的遍历方法：
#include<iostream>
#include "tree_node.h"
// 先序遍历打印二叉树
void printTreePreOrder(TreeNode* root)
{
// 基准情况，如果是空树，直接返回
if (root == nullptr) return;
//cout << (*root).name << "\t";
cout << root->name << "\t";
// 递归打印左右子树
printTreePreOrder(root->left);
printTreePreOrder(root->right);
}
// 中序遍历打印二叉树
void printTreeInOrder(TreeNode* root)
{
// 基准情况，如果是空树，直接返回
if (root == nullptr) return;
printTreeInOrder(root->left);
cout << root->name << "\t";
printTreeInOrder(root->right);
}
// 后序遍历打印二叉树
void printTreePostOrder(TreeNode* root)
{
// 基准情况，如果是空树，直接返回
if (root == nullptr) return;
printTreePostOrder(root->left);
printTreePostOrder(root->right);
cout << root->name << "\t";
}
然后将这些函数的声明也放到头文件tree_node.h中：
void printTreePreOrder(TreeNode* root);
void printTreeInOrder(TreeNode* root);
void printTreePostOrder(TreeNode* root);
接下来就可以在代码中实现具体的功能了：
#include<iostream>
#include "tree_node.h"
int main()
{
// 定义一棵二叉树
TreeNode nodeG = {"G", nullptr, nullptr};
TreeNode nodeF = { "F", nullptr, nullptr };
TreeNode nodeE = { "E", &nodeG, nullptr };
TreeNode nodeD = { "D", nullptr, nullptr };
TreeNode nodeC = { "C", nullptr, &nodeF};
TreeNode nodeB = { "B", &nodeD, &nodeE };
TreeNode nodeA = { "A", &nodeB, &nodeC };
TreeNode* tree = &nodeA;
printTreePreOrder(tree);
cout << endl << endl;
printTreeInOrder(tree);
cout << endl << endl;
printTreePostOrder(tree);
cin.get();
}
标签：遍历,TreeNode,中序,nullptr,二叉树,root,节点 From： https://www.cnblogs.com/huangzuhong/p/17702301.html