强烈推荐，超详细实现二叉树的建立（附实现源码）
目录
1.如何创建一棵二叉树1.二叉树的存储结构定义2.实现二叉树结点的新建、查找、修改3.实现二叉树结点的插入4.二叉树创建过程
2.二叉树的遍历1.先序遍历2.中序遍历3.后序遍历4.层序遍历
3.源码实现
1.如何创建一棵二叉树
创建一棵二叉树需要什么 其实答案很简单，无非就是从根节点开始，逐步实现子节点的创建，从而实现树的整体框架 由于树是一种特殊的线性表，所以对于生成后的树，我们应该可以对它进行查找，修改，插入等功能 最后，我们将进行对树的遍历，这里将讨论常用的先序，中序，后序以及层序等四种遍历方式
关于二叉查找树结点的删除，可以查看后续文章 强烈推荐！超详细实现二叉查找树结点的删除（附实现源码）
1.二叉树的存储结构定义
一般来说，二叉树使用链表来定义，不同的是，由于二叉树每个结点都存在两条出边，因此指针域变为两个，分别指向左子树和右子树的跟结点地址，因此又把这种链表叫做二叉链表
struct node
{
int data; //数据域
node * lchild; //指向左子树根节点的指针
node * rchild; //指向右子树根节点的指针
};
2.实现二叉树结点的新建、查找、修改
如果需要新建结点（例如往二叉树里面插入结点时，可使用下面的函数（返回类型是一个指向node的指针）
node* newNode(int v) {
node*Node = new node; //申请一个node类型变量的地址空间
Node->data = v; //结点权值为v
Node->lchild = Node->rchild = NULL; //初始状态下无左右孩子
return Node; //返回新节点的地址
}
查找操作是指在给定的数据域内，在二叉树里面找到所有数据域（对多个结点实行操作）为给定数据域的结点，并且对查找到的结点修改为给定的数据域
void search(node*root,int x, int newdata){
if (root == NULL) return; //考虑为空节点的可能性
if (root->data == x) {
root->data = newdata; //找到数据域为x的结点，把它修改为newdata
}
search(root->lchild, x, newdata);//往左子树搜索
search(root->rchild, x, newdata);//往右子树搜索
}
3.实现二叉树结点的插入
关于二叉树结点的插入，由于在没有给出插入条件的问题中，很难给出插入的具体方法。因此这里以在一棵二叉搜索树中插入为例。插入过程的核心思想，是按照给定的插入条件（例中为二叉查找树）找到树里面的边界（死胡同），此处就是查找失败的地方，也是结点需要插入的地方
void insert(node*& root, int x) { //注意 传入的是结点指针的引用
if (root == NULL) { //空树，即查找失败，插入结点（递归边界）
root = newNode(x);
return;
}
if (root->data > x) { //往左子树搜索
insert(root->lchild, x);
}
else insert(root->rchild, x); //往右子树搜索
}
在上述代码中，一个关键的点就是根节点指针root使用了引用&，这样在函数中可以直接修改原变量。这么做的原因是，在insert函数中新建了一个新结点，并且把新节点的地址赋给了当层的root。如果不采用引用，root = new node 这个语句对root 的修改就无法作用到原变量，也就无法将节点加到二叉树上面。那为什么前面的search 函数不需要加引用呢？因为search 函数修改的是指针root指向的内容，而不是root本身，对结点指向的内容的修改是不需要加引用的
4.二叉树创建过程
二叉树的创建，其实就是二叉树结点的插入过程，比较常用的写法是把需要插入的数据域存储在数组中，并且最终返回插入结点后树的根结点
node*create(int data[], int n) {
node* root = NULL; //新建空根结点
for (int i = 0; i < n; i++) {
insert(root, data[i]); //将data[0]到data[n-1]插入二叉树
}
return root; //返回根节点
}
2.二叉树的遍历
在下文提到的四种遍历方式中，像先、中、后三种遍历方式，都是基于深度优先搜索（DFS)，而层序遍历则是基于广度搜索（BFS）由于树本质上是一种递归结构，因此可以抽象的把树看成root， 左子树 ，右子树 三部分，且对左右子树也进行同样的划分前三种遍历中无论哪一种，都是先开始左子树的遍历，再到右子树。所谓先、中、后则是代表根节点在访问过程中的位置
1.先序遍历
由定义知，先序遍历的遍历顺序是根节点->左子树->右子树，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界
所以核心问题是处理好 递归式与递归边界
实现效果图如下： 代码实现如下：
void preorder(node* root) { //先序遍历
if (root == NULL) return; //到达空树，即递归边界
cout << root->data << endl;; //访问根节点数据域
preorder(root->lchild); //访问左子树
preorder(root->rchild); //访问右子树
}
2.中序遍历
中序遍历也是一样的思想，中序遍历的遍历顺序是左子树->根节点->右子树，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界实现效果图如下： 代码实现如下：
void inorder(node* root) { //中序遍历
if (root == NULL) return; //到达空树，即递归边界
inorder(root->lchild); //访问左子树
cout << root->data << endl;; //访问根节点数据域
inorder(root->rchild); //访问右子树
}
3.后序遍历
后序遍历同上，中序遍历的遍历顺序是左子树->右子树->根节点，由上文提到的抽象思想，对于每个结点都采用相同的遍历思路，直到到达递归边界实现效果图如下： 代码实现如下：
void postorder(node* root) { //后序遍历
if (root == NULL) return; //到达空树，即递归边界
preorder(root->lchild); //访问左子树
preorder(root->rchild); //访问右子树
cout << root->data << endl;; //访问根节点数据域
}
4.层序遍历
层序遍历是按照层次顺序从根节点向下逐层进行遍历，且对同一层的结点由左往右进行遍历，由于存在回溯问题，因此需要用到队列这种数据结构
具体实现思路如下
①将根节点root 加入队列q②取出队首结点，访问它③若该结点有左孩子，则将左孩子入队④该结点有有孩子，则将右孩子入队重复进行步骤②，直到队列为空 实现效果图如下：
实现代码如下：
void LayerOrder(node* root) { //层序遍历
queue
q.push(root); //将根节点入队
while (!q.empty()) //退出条件为队列为空
{
node* now = q.front(); //取出队首元素
cout << now->data << endl;
q.pop(); //弹出队首元素
if (now->lchild != NULL) q.push(now->lchild);//左子树非空则压入队列
if (now->rchild != NULL) q.push(now->rchild);//右子树非空则压入队列
}
}
3.源码实现
#include
#include
using namespace std;
struct node
{
int data;
node * lchild;
node * rchild;
};
node* newNode(int v) {
node*Node = new node; //申请一个node类型变量的地址空间
Node->data = v; //结点权值为v
Node->lchild = Node->rchild = NULL; //初始状态下无左右孩子
return Node; //返回新节点的地址
}
void search(node*root,int x, int newdata){
if (root == NULL) return; //考虑为空节点的可能性
if (root->data == x) {
root->data = newdata; //找到数据域为x的结点，把它修改为newdata
}
search(root->lchild, x, newdata);//往左子树搜索
search(root->rchild, x, newdata);//往右子树搜索
}
void insert(node*& root, int x) {
if (root == NULL) { //空树，即查找失败，插入结点（递归边界）
root = newNode(x);
return;
}
if (root->data > x) { //往左子树搜索
insert(root->lchild, x);
}
else insert(root->rchild, x); //往右子树搜索
}
node*create(int data[], int n) {
node* root = NULL; //新建空根结点
for (int i = 0; i < n; i++) {
insert(root, data[i]); //将data[0]到data[n-1]插入二叉树
}
return root; //返回根节点
}
void preorder(node*root) { //先序遍历
if (root == NULL) return; //到达空树，即递归边界
cout << root->data << endl;; //访问根节点数据域
preorder(root->lchild); //访问左子树
preorder(root->rchild); //访问右子树
}
void inorder(node*root) { //中序遍历
if (root == NULL) return; //到达空树，即递归边界
inorder(root->lchild); //访问左子树
cout << root->data << endl;; //访问根节点数据域
inorder(root->rchild); //访问右子树
}
void postorder(node* root) { //后序遍历
if (root == NULL) return; //到达空树，即递归边界
preorder(root->lchild); //访问左子树
preorder(root->rchild); //访问右子树
cout << root->data << endl;; //访问根节点数据域
}
void LayerOrder(node* root) { //层序遍历
queue
q.push(root); //将根节点入队
while (!q.empty()) //退出条件为队列为空
{
node* now = q.front(); //取出队首元素
cout << now->data << endl;
q.pop(); //弹出队首元素
if (now->lchild != NULL) q.push(now->lchild);//左子树非空则压入队列
if (now->rchild != NULL) q.push(now->rchild);//右子树非空则压入队列
}
}
int main() {
int n = 10;
int nums[10] = { 5,3,8,2,4,1,6,7,9,0 };
node* root = create(nums, 10);
//search(root, 7, 11); //查找替换
preorder(root);//前序遍历
//inorder(root); //中序遍历
//postorder(root); //后序遍历
//LayerOrder(root); //层序遍历
system("pause");
return 0;
}