目录
- 1 基础说明
- 2 基本思路-二叉树的创建和插入
- 2.1 节点存储结构的建立
- 2.2 二叉树创建函数的设计
- 2.3 二叉树插入函数的设计
- 2.4 简单的进行二叉树的检测看看插入的对不对：
- 2.5 整体代码：
- 3 二叉树的遍历
- 3.1 中序遍历
- 3.2 程序代码：
- 3.3 程序结果：
- 4 二叉树的查找
- 4.1 改进中序递归查找
- 4.2 程序结果
- 5 二叉树节点中序增加
主要是进行代码的书写，原理部分不过多介绍，原理部分应该是优先掌握的，不会原理写代码
事倍功半，知道了原理再去理解程序事半功倍
1 基础说明
在进行二叉树的建立、查找和修改时，要具备一些基本的知识。
- 首先对于结构体要熟悉，知道结构体的定义和使用，以及结构体常用的别名的使用
- 其次就是对malloc函数比较熟悉，能熟练的使用malloc进行动态数组的建立
- 然后就是最重要的就是对链表要很熟悉，至少单链表要能进行建立和查找，删除
- 然后就是要对二叉树要熟悉，如果二叉树是什么都不知道，怎么进行建立?，要知道其原理，其次要知道二叉树的遍历的三种方式，一般就是有先序、中序、后序，这些遍历的原理至少要掌握
- 最后就是二叉树的建立要用到一个比较重要的知识点就是递归，其中插入节点要用到
地址的递归回溯过程，其他的就跟单链表建立差不多的；
2 基本思路-二叉树的创建和插入
2.1 节点存储结构的建立
有了上面的基础后,其实内心对于二叉树的建立应该有了一个大致的轮廓，不至于一窍不通，肯定要进行数据的输入，那么就要创建一个能存储数据的结构体：如下
// 创建树的节点结构体
typedef struct tree
{
int data;
struct tree *Lchildren;
struct tree *Rchildren;
/* data */
} BinTree;
2.2 二叉树创建函数的设计
有了能存储的结构体，那么下一步就是要创建二叉树，可以分为两个大步骤，第一个就是二叉树的建立，第二个就是进行而叉树的建立；
第一步进行二叉树的创建函数的设计：这里，先不管插入函数，就先认为已经把插入的功能实现了，进行创建一个二叉树要有一个根节点，这里选用手动进行数据的输入，还要定义一个key，因此每次输入一个数据就要用malloc动态的申请一个节点，（由于这个节点是由malloc函数申请的，数据是放在了堆上，因此这个函数调用完毕，数据也不会清空），并对这个节点进行初始化，然后进行插入，最后执行完这个函数只需要把根节点给返回就行，因此创建函数可以定义为指针函数；
BinTree *CreatNode()
{
int key;
BinTree *NewNode;
BinTree *root = NULL; // 二叉树的根节点，会作为地址返回给主函数
// 二叉树的根节点，必须设置为空，不然第一次进行插入时，无法正确的插入
while (1)
{
scanf("%d", &key);
if (key != -1) // 如果key为-1就停止
{
NewNode = (BinTree *)malloc(sizeof(BinTree));
NewNode->data = key;
NewNode->Lchildren = NULL;
NewNode->Rchildren = NULL;
root = InsertTree(root, NewNode); // 调用插入函数
}
else
{
break;
}
}
return root;
}
2.3 二叉树插入函数的设计
可以简单考虑一下，对于插入函数要有根节点和新节点的地址，这样方便进行插入，而且每次插入完毕可以把根节点地址给返回回来，这里假设中序插入，思考一下树的定义，以及如何能在我插入完新节点后，地址能一层一层的返回，也就是地址回溯，这样我就递归的寻找到顶点，到顶点后，再依次进行地址回溯，这样就能完成新节点的插入，而对于是中序插入，还是先序插入，完全取决于你写的顺序；插入函数如下：
// 插入函数，递归调用，root是根地址，但是随着递归的调用
// 地址在进行回溯
BinTree *InsertTree(BinTree *root, BinTree *newnode)
{
if (root == NULL) // 递归的终止条件，终止后把新节点的地址传给上一层，
// 上一层继续执行下面的函数（条件都不满足实际上就是直接跳到了return）
// ，并把地址传给上上一层，以此类推进行地址的回溯
{
root = newnode;
}
else
{
if (root->data > newnode->data)
{
root->Lchildren = InsertTree(root->Lchildren, newnode);
// 这一点比较难以理解
// 要理解回溯的思想
}
if (root->data < newnode->data)
{
root->Rchildren = InsertTree(root->Rchildren, newnode);
}
}
return root;
}
2.4 简单的进行二叉树的检测看看插入的对不对：
例如插入 7 4 5；如下图：
int main()
{
BinTree *root;
root = CreatNode();
return 0;
}
输入和打印结果：
2.5 整体代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 创建树的节点结构体
typedef struct tree
{
int data;
struct tree *Lchildren;
struct tree *Rchildren;
/* data */
} BinTree;
// 插入函数，按照中序插入
BinTree *InsertTree(BinTree *root, BinTree *newnode);
// 二叉树的创建函数
BinTree *CreatNode();
BinTree *CreatNode()
{
int key;
BinTree *NewNode;
BinTree *root = NULL; // 二叉树的根节点，会作为地址返回给主函数
// 二叉树的根节点，必须设置为空，不然第一次进行插入时，无法正确的插入
while (1)
{
scanf("%d", &key);
if (key != -1) // 如果key为-1就停止
{
NewNode = (BinTree *)malloc(sizeof(BinTree));
NewNode->data = key;
NewNode->Lchildren = NULL;
NewNode->Rchildren = NULL;
root = InsertTree(root, NewNode); // 调用插入函数
}
else
{
break;
}
}
return root;
}
// 插入函数，递归调用，root是根地址，但是随着递归的调用
// 地址在进行回溯
BinTree *InsertTree(BinTree *root, BinTree *newnode)
{
if (root == NULL) // 递归的终止条件，终止后把新节点的地址传给上一层，
// 上一层继续执行下面的函数（条件都不满足实际上就是直接跳到了return）
// 并把地址传给上上一层，以此类推进行地址的回溯
{
root = newnode;
}
else
{
if (root->data > newnode->data)
{
root->Lchildren = InsertTree(root->Lchildren, newnode);
// 这一点比较难以理解
// 要理解递归的思想
}
if (root->data < newnode->data)
{
root->Rchildren = InsertTree(root->Rchildren, newnode);
}
}
return root;// 要理解回溯的思想
}
int main()
{
BinTree *root;
root = CreatNode();
printf("%d,%d,%d", root->data, (root->Lchildren)->data, ((root->Lchildren)->Rchildren)->data);
return 0;
}
3 二叉树的遍历
3.1 中序遍历
继续对上述的代码进行补充，即进行中序遍历输出：中序这里采用递归的方法，其实对于先序和中序，后序都可以采用递归的方法，同时也可以采用堆栈的的方法进行遍历，但是这里就先利用递归的方法进行编写：递归中难以理解就是函数的运行过程，具体理解可以参考下图，其中紫色的箭头就是其程序的运行过程： 尤其注意的是到顶点后不会立刻返回上一个节点，而是会进行两次判断后再次进入上一个顶点：
3.2 程序代码：
// 中序递归遍历，可以这个比较难以理解
void InOrder(BinTree *root)
{
if (root == NULL)
{
return;
}
InOrder(root->Lchildren);
printf("%d,", root->data);
InOrder(root->Rchildren);
}
int main()
{
BinTree *root, *find;
int key;
root = CreatNode();
printf("%d,%d,%d", root->data, (root->Lchildren)->data, ((root->Lchildren)->Rchildren)->data);
InOrder(root);//中序遍历
return 0;
}
3.3 程序结果：
4 二叉树的查找
上面已经得到二叉树的中序遍历，那么接下来就是对元素进行查找，其中查找可以把中序的函数修改一下，让其每次与目标值的比较，如果掌握了前面的内容，那么查找函数就是比较好写的：
4.1 改进中序递归查找
由中序遍历改进而来，其他保持不变
// 改进 中序递归查找
BinTree *InOrderSerach(BinTree *root, int val)
{
if (root == NULL)
{
return NULL;
}
BinTree *Find = InOrderSerach(root->Lchildren, val);
if (Find != NULL)
{
return Find; // 如果找了值就一直递归返回，直到返回原函数，后面递归就不执行了
}
if (root->data == val)
{
return root;
}
Find = InOrderSerach(root->Rchildren, val);
return Find; // 这个不能删除，作为最后，同时返回右子树为空的情况函数的返回值
}
int main()
{
BinTree *root, *find;
int key;
root = CreatNode();
InOrder(root);
printf("\n");
while (1)
{
if (key != -1)//key==-1结束
{
scanf("%d", &key);
find = InOrderSerach(root, key);
printf("\nYES:%d\n", find->data);
}
else
{
break;
}
}
return 0;
}
4.2 程序结果
5 二叉树节点中序增加
到目前为止，我们从一个结构体起步，进行了了二叉树的建立，中序遍历，中序递归查找，那么接下来就是增删的内容了，上面的内容可以保持不变；简单想一下，对于二叉树的增加，首先就是要用到插入函数，其次就是左右子树的指针指向要改变一下，弄完后要一直递归返回就行了，剩下的不用管了；
所以主线就是，先找到插入的位置，然后改变指针指向，最后一直return返回就行了；剩下待补充…
