【数据结构】二叉树的定义及二叉树的遍历，肯定是最详细的（附有源码-可直接运行）
时间：2022-09-04 18:00:00
目录
一、树的概念和定义
1.树的定义
2.树的相关专业术语
3.树的表示
二,.二叉树的概念
1.定义二叉树
二、二叉树的性质
三，.储存二叉树
1..顺序存储
2.链式存储
四，二叉树的操作
1.定义链式二叉树
二、二叉树初始化
3.将结点添加到二叉树
4.获得二叉树的左右子树
五、二叉树的状态
6.搜索二叉树
7.清空二叉树
五、二叉树遍历
1.先序遍历
2.中序遍历
3.后序遍历
4.按层遍历
六、所有代码
一、树的概念
树：顾名思义，就像树一样有无限的分支，但这个方向是向下生长。
它和线性链表的区别在于:线性链表有:最多只有一个前驱和一个后继点，其为线性的。但是树则遵循：一个结点有一个前驱和多个后继。
1.树的定义
树：有n个结点的集合中有一个特殊的结点叫做根。根点下分布着一些不相交的集合，每个集合都是一棵树，这些子树被称为根点
感觉如何？ 很抽象？ 上图说话吧。
讲解3.1那么A就是根结点，如果连A都没有，那就是空集合(空树)，同时也没有结点，A也是传说中的树根root，补充相关根点：如果一棵树只有一个结点，没有前驱，那么这个结点就是根点。
2.树的相关专业术语
- 父节点，子节点，兄弟结点：A是第一代，为父节点，B C D 同时，他三个是兄弟，所以被称为兄弟结点.
- 结点的度：计算结点的子数，看他们有多少孩子，比如A有三个孩子，A的度是3，B C D则分别是 1 2 2；
- 树的度：例如，这棵树是整棵树中最大的度数 3
- 叶结点和分支结点：度为0 他没有后代，也叫终端结点或叶结点，这里有E J K L M N有孩子的叫分支结点或非终端结点。
- 结点的层数：计算从根结点开始(即A）然后往下数1 2 3 4
- 树的深度：树中结点的最大层数是深度，这是 4
- 森林:去掉树根A，B C D三棵树成了新根，多棵树是森林
3.树的表示
只需按括号中的括号表示即可。
二,.二叉树额概念
任何树都可以转化为相应的二叉树，so，二叉树很重要。
1.定义二叉树
二叉树：就是指一个树分成俩杈子，这就是二叉树。俩杈子左边叫左子树，右边叫右子树。
区别 ：树的分支没有限制(即度)，但二叉树最多是两棵，树的孩子多，没有名字，二叉树多做两个孩子，有左右之分。
一直两个孩子，永远不要偏叫:满二叉树，只有一个孩子会付出所有的爱：完全二叉树，但完全二叉树可以用满二叉树来表示。完全二叉树官方解释是:深度为k，有n个结点的二叉树，当每个结点与每个结点与深度为k的满二叉树从1号编号时~n当结点一一对应时，称为完全二叉树。特征：对于任何结点，如果右分支的子孙最大水平是l，要求左分支下子孙的最大比例为l或 l 1.否则，它不是完全的二叉树 。 例如，如果图a中的N点被删除，他就不满意了，总结:右分支可以，左分支不能动trong>
2.二叉树的性质
- 二叉树中，第 i 层最多是2i-1个结点。
- 深度为k的二叉树的结点 最少 k 个，最多 2k-1个结点
- 若一个二叉树，叶节点为 n0若度的为 2 的节点数为n2 那么则由 n0= n2+1(怎样解释呢，看那个满二叉树，也结点是8个，H~O，但是度为2的结点是A~G，所以差是1）
对于（5）解释：这里的除法是满足整数除法的 3 / 2 = 1
拿B举例，他的父结点是A也就是1 为 3/2=1，子为 D E，分别是4 5后边的同理
三，.二叉树的储存
1..顺序存储
解释：与线性表的顺序存储类似，二叉树也是将其存储到一个一维数组之中
定义如下
#define MAXSIZE 100 //最大结点数
typedef int DATA //元素类型
typedef DATA SeqBinTree[MAXSIZE];
SeqBinTree SBT; //定义保存二叉树组当你知道某一结点的位置时，你可以按照公式去推算他的父亲和左右的子结点的位置，
以E举例，现在结点是5，父结点就是（5 / 2）为 2 就是B，（前提存在）则其左子结点的话，就是5*2 = 10 计时J 右则为 5*2 +1 = 11 就是 K。
但是就这样储存就完了吗？
当然不是，若不是完全二叉树呢？中间有的没有子结点呢？或者子节点缺失呢？
不怕，按照完全二叉树来进行补齐，大不了算的是补的空，就是没有子结点呗
2.链式存储
声明：因为按照循序存储结构会浪费空间，在线性表也是同样的问题，那么多数用的都是链式存储结构
看到这想到了什么，链表，双向链表，其实就是多了一个指针域，这个也同样
二叉链式结构
typedef struct ChainTree
{
DATA data; //元素数据
struct ChainTree *left; //左子树结点指针
struct ChainTree *right;//右子树结点指针
} ChainTreeType;
ChainTreeType *root=NULL; //定义二叉树根结点指针最后一行的是根结点指针，若为空，则root为NULL。在具有n个结点的二叉树中，一共有2n个指针域，但是有n-1个指向孩子，n+1个指针域为空。（因为也结点是俩空指针，度为一的是一个空指针，所以2 * n0 + n1（空指针的总数量）因为遵循 n0 = n2 + 1，所以则总和一下 空指针 = n0 +（n2 + 1）+ n1 得到为 n + 1个空）上边的性质三（标红）
三叉链式结构
typedef struct ChainTree
{
DATA data; //元素数据
struct ChainTree *left; //左子树结点指针
struct ChainTree *right;//右子树结点指针
struct ChainTree *parent；//父结点指针
} ChainTreeType;
ChainTreeType *root=NULL; //定义二叉树根结点指针四，二叉树的操作
1.定义链式二叉树
#include
#include
#define QUEUE_MAXSIZE 50 //队列的大小
typedef char DATA; //类型
typedef struct ChainTree //二叉树结点类型
{
DATA data; //数据储存
struct ChainTree* left; //左
struct ChainTree* right;
}ChainBinTree; 2.初始化二叉树
：参数node为二叉树的指针，当其不为空，则作为根结点
ChainBinTree* BinTreeInit(ChainBinTree* node)
{
if (node != NULL) //节点不为空
return node;
else
return NULL;
}3.添加结点到二叉树
bt是父结点的指针，node是子结点，n则判断将node添加的左或右结点
int BinTreeAddNode(ChainBinTree* bt, ChainBinTree* node, int n)
{
if (bt == NULL)
{
printf("父节点不存在，请先设置父节点！\n");
return 0;
}
switch (n)
{
case 1: if (bt->left) {
printf("左子树结点不为空！\n");
return 0;
}else
bt->left = node;
break;
case 2: if (bt->right) {
printf("右子树结点不为空！\n");
return 0;
}else
bt->right = node;
break;
default:
printf("参数错误！\n");
return 0;
}
return 1;
}4.获取二叉树的左右子树
ChainBinTree* BinTreeLeft(ChainBinTree* bt) //返回左子结点
{
if (bt)
return bt->left;
else
return NULL;
}
ChainBinTree* BinTreeRight(ChainBinTree* bt)
{
if (bt)
return bt->right;
else
return NULL;
}
5.二叉树的状态
int BinTreeIsEmpty(ChainBinTree* bt) //检查是否为空
{
if (bt)
return 0;
else
return 1;
}
int BinTreeDepth(ChainBinTree* bt) //得到深度
{
int dep1, dep2;
if(bt==NULL)
return 0;
else
{
dep1 = BinTreeDepth(bt->left);
dep2 = BinTreeDepth(bt->right);
if (dep1 > dep2)
return dep1 + 1;
else
return dep2 + 1;
}
}
6.二叉树的查找
ChainBinTree* BinTreeFind(ChainBinTree* bt, DATA data)
{
ChainBinTree* p;
if(bt==NULL)
return NULL;
else
{
if (bt->data == data)
return bt;
else {
if (p = BinTreeFind(bt->left, data))
return p;
else if (p = BinTreeFind(bt->left, data))
return p;
else
return NULL;
}
}
}7.二叉树的清空
因为是malloc所申请的内存，因此要用free函数来释放所占内存。
void BinTreeClear(ChainBinTree* bt)
{
if (bt)
{
BinTreeClear(bt->left);
BinTreeClear(bt->right); //清空左右结点
free(bt); //释放当前结点
bt = NULL;
}
return;
}五，二叉树的遍历
1.先序遍历
则遵循以下的code原则
void BinTree_DLR(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
if (bt)
{
oper(bt);
BinTree_DLR(bt->left, oper);
BinTree_DLR(bt->right, oper);
}
return;
}2.中序遍历
void BinTree_LDR(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
if (bt) //树不为空
{
BinTree_LDR(bt->left, oper);//中序遍历
oper(bt);
BinTree_LDR(bt->right, oper);
}
return;
}
3.后序遍历
void BinTree_LRD(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
if (bt) //树不为空
{
BinTree_LDR(bt->left, oper);//中序遍历
BinTree_LDR(bt->right, oper);
oper(bt);
}
return;
}
4.按层遍历
void BinTree_level(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
ChainBinTree* p;
ChainBinTree* q[QUEUE_MAXSIZE];
int head = 0, tail = 0;
if (bt)
{
tail = (tail + 1) % QUEUE_MAXSIZE; //上一节的那一套
q[tail] = bt;
}
while (head != tail)
{
head = (head + 1) % QUEUE_MAXSIZE;
p = q[head];
oper(p);
if (p->left != NULL)
{
tail = (tail + 1) % QUEUE_MAXSIZE;
q[tail] = p->left;
}
if (p->right != NULL)
{
tail = (tail + 1) % QUEUE_MAXSIZE;
q[tail] = p->right;
}
}
return;
}
六,全部代码
BinTree函数部分
#include "Bintree.h"
void oper(ChainBinTree* p)
{
printf("%c ", p->data);
return;
}
ChainBinTree* BinTreeInit(ChainBinTree* node)
{
if (node != NULL) //节点不为空
return node;
else
return NULL;
}
int BinTreeAddNode(ChainBinTree* bt, ChainBinTree* node, int n)
{
if (bt == NULL)
{
printf("父节点不存在，请先设置父节点！\n");
return 0;
}
switch (n)
{
case 1: if (bt->left) {
printf("左子树结点不为空！\n");
return 0;
}else
bt->left = node;
break;
case 2: if (bt->right) {
printf("右子树结点不为空！\n");
return 0;
}else
bt->right = node;
break;
default:
printf("参数错误！\n");
return 0;
}
return 1;
}
ChainBinTree* BinTreeLeft(ChainBinTree* bt)
{
if (bt)
return bt->left;
else
return NULL;
}
ChainBinTree* BinTreeRight(ChainBinTree* bt)
{
if (bt)
return bt->right;
else
return NULL;
}
int BinTreeIsEmpty(ChainBinTree* bt)
{
if (bt)
return 0;
else
return 1;
}
int BinTreeDepth(ChainBinTree* bt)
{
int dep1, dep2;
if(bt==NULL)
return 0;
else
{
dep1 = BinTreeDepth(bt->left);
dep2 = BinTreeDepth(bt->right);
if (dep1 > dep2)
return dep1 + 1;
else
return dep2 + 1;
}
}
ChainBinTree* BinTreeFind(ChainBinTree* bt, DATA data)
{
ChainBinTree* p;
if(bt==NULL)
return NULL;
else
{
if (bt->data == data)
return bt;
else {
if (p = BinTreeFind(bt->left, data))
return p;
else if (p = BinTreeFind(bt->left, data))
return p;
else
return NULL;
}
}
}
void BinTreeClear(ChainBinTree* bt)
{
if (bt)
{
BinTreeClear(bt->left);
BinTreeClear(bt->right); //清空左右结点
free(bt); //释放当前结点
bt = NULL;
}
return;
}
void BinTree_DLR(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
if (bt)
{
oper(bt);
BinTree_DLR(bt->left, oper);
BinTree_DLR(bt->right, oper);
}
return;
}
void BinTree_LDR(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
if (bt) //树不为空
{
BinTree_LDR(bt->left, oper);//中序遍历
oper(bt);
BinTree_LDR(bt->right, oper);
}
return;
}
void BinTree_LRD(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
if (bt) //树不为空
{
BinTree_LDR(bt->left, oper);//中序遍历
BinTree_LDR(bt->right, oper);
oper(bt);
}
return;
}
void BinTree_level(ChainBinTree* bt, void(*poer)(ChainBinTree* p))
{
ChainBinTree* p;
ChainBinTree* q[QUEUE_MAXSIZE];
int head = 0, tail = 0;
if (bt)
{
tail = (tail + 1) % QUEUE_MAXSIZE; //上一节的那一套
q[tail] = bt;
}
while (head != tail)
{
head = (head + 1) % QUEUE_MAXSIZE;
p = q[head];
oper(p);
if (p->left != NULL)
{
tail = (tail + 1) % QUEUE_MAXSIZE;
q[tail] = p->left;
}
if (p->right != NULL)
{
tail = (tail + 1) % QUEUE_MAXSIZE;
q[tail] = p->right;
}
}
return;
}
BinTree.h
#include
#include
#define QUEUE_MAXSIZE 50
typedef char DATA;
typedef struct ChainTree
{
DATA data;
struct ChainTree* left;
struct ChainTree* right;
}ChainBinTree;
void oper(ChainBinTree* p);
ChainBinTree* BinTreeInit(ChainBinTree* node); //初始化
int BinTreeAddNode(ChainBinTree* bt, ChainBinTree* node, int n); //添加到二叉树
ChainBinTree* BinTreeLeft(ChainBinTree* bt); //返回左子节点
ChainBinTree* BinTreeRight(ChainBinTree* bt); //返回左子节点
int BinTreeIsEmpty(ChainBinTree* bt); //检验是否为空
int BinTreeDepth(ChainBinTree* bt); //求深度
ChainBinTree* BinTreeFind(ChainBinTree* bt, DATA data);
void BinTreeClear(ChainBinTree* bt);
//void BinTree_DLR(BinTree);
void BinTree_DLR(ChainBinTree* bt, void(*poer)(ChainBinTree* p));
void BinTree_LDR(ChainBinTree* bt, void(*poer)(ChainBinTree* p));
void BinTree_LRD(ChainBinTree* bt, void(*poer)(ChainBinTree* p));
void BinTree_level(ChainBinTree* bt, void(*poer)(ChainBinTree* p));
BinTree.c（main函数部分）
#include
#include "Bintree.h"
ChainBinTree* InitRoot()
{
ChainBinTree* node;
if (node = (ChainBinTree*)malloc(sizeof(ChainBinTree)))
{
printf("\n输入根节点数据：");
scanf("%s", &node->data);
node->left = NULL;
node->right = NULL;
return node;
}
return NULL;
}
void AddNode(ChainBinTree* bt)
{
ChainBinTree* node, * parent;
DATA data;
char select;
if (node = (ChainBinTree*)malloc(sizeof(ChainBinTree)))
{
printf("\n输入二叉树的结点数据：");
fflush(stdin);
scanf("%s", &node->data);
node->left = NULL;
node->right = NULL;
printf("输入父结点数据：");
fflush(stdin);
scanf("%s", &data);
parent = BinTreeFind(bt, data);
if (!parent)
{
printf("未找到父结点！\n");
free(node);
return;
}
printf("1.添加到左子树\n 2.添加到右子树\n");
do {
select = getchar();
select -= '0';
if (select == '1' || select == '2')
BinTreeAddNode(parent, node, select);
} while (select != 1 && select != 2);
}
return;
}
int main()
{
ChainBinTree* root = NULL;
char select;
void (*oper1)(ChainTree*); //指向集体的指针
oper1 = &oper; //指向具体的操作函数
do {
printf("\n1.设置二叉树根元素 2.添加二叉树结点\n");
printf("3.先序遍历 4.中序遍历\n");
printf("5.后序遍历 6.按层遍历\n");
printf("7.二叉树的深度 0.退出\n");
select = getchar();
switch (select) {
case '1': root = InitRoot(); break;
case '2':AddNode(root); break;
case '3':
printf("\n先遍历的结果：");
BinTree_DLR(root,oper1);
printf("\n");
break;
case '4':
printf("\n中序遍历的结果：");
BinTree_LDR(root, oper1);
printf("\n");
break;
case '5':
printf("\n中序遍历的结果：");
BinTree_LRD(root, oper1);
printf("\n");
break;
case '6':
printf("\n中序遍历的结果：");
BinTree_level(root, oper1);
printf("\n");
break;
case '7': printf("\n二叉树的深度为：%d\n", BinTreeDepth(root)); break;
case '0': break;
}
} while (select != '0');
BinTreeClear(root);
root = NULL;
getchar();
return 0;
}
运行
那个做着做着太累喽，后边就在凑合了，下次要注意我的篇幅和详细和略过的点，我会注意的，我能力有限，只能写道这个部分，谢谢阅读。
