【数据结构】二叉树的定义及二叉树的遍历，肯定是最详细的（附有源码-可直接运行）
最新推荐文章于 2023-07-11 11:14:49 发布
i-阿松！
最新推荐文章于 2023-07-11 11:14:49 发布
阅读量1.1k
收藏
7
点赞数
3
最新推荐文章于 2023-07-11 11:14:49 发布
阅读量1.1k
收藏
7
点赞数
3
目录
1.树的定义
2.树的相关专业术语
3.树的表示
二,.二叉树的概念
1.二叉树的定义
2.二叉树的性质
三，.二叉树的储存
1..顺序存储
2.链式存储
四，二叉树的操作
1.定义链式二叉树
2.初始化二叉树
3.添加结点到二叉树
4.获取二叉树的左右子树
5.二叉树的状态
6.二叉树的查找
7.二叉树的清空
五，二叉树的遍历
1.先序遍历
2.中序遍历
3.后序遍历
4.按层遍历
六,全部代码
一,树的概念
树：顾名思意，就是像树一样有无限的分支，但是这个的方向是向下长得。
它和线性链表的区别是：线性链表中具有：一个结点最多只有一个前驱和一个后继结点，其为线性的。但是树则遵循：一个结点有一个前驱和多个后继。
1.树的定义
树：具有n个结点的集合，集合中有一个称为根的特殊结点，在根结点下的分布着一些互不相交的集合，每个集合又是一个树，这些数称之为根结点的子树
感觉怎么样？ 很抽象？ 咱们上图说话。
讲解3.1那么A就是根结点，如果连A也没有那么就是一个空集合（空树）也同时没有结点，同时A也是传说中的树根root，有关根结点在补充一点是：若在一棵树中，仅有一个结点，没有前驱，那么这个结点就是根结点。
2.树的相关专业术语
- 父节点，子节点，兄弟结点：A是第一代，为父节点，B C D 为A的子节点，同时他仨还是兄弟，因此称之为兄弟结点.
- 结点的度：就是计算结点的子数，看他们有几个孩子，比如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点去掉，他就不满足了，总结：右分支可以少，左分支不可动
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 <stdio.h>
#include <stdlib.h>
#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 <stdio.h>
#include <stdlib.h>
#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 <stdio.h>
#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;
}
运行
那个做着做着太累喽，后边就在凑合了，下次要注意我的篇幅和详细和略过的点，我会注意的，我能力有限，只能写道这个部分，谢谢阅读。
950
暂无认证
到【灌水乐园】发言
i-阿松！: 哈哈哈，谢谢
白话机器学习: 文章写得专业、深入、详细，收藏啦
i-阿松！: 这个文章是展示了部分的页面展示，【微信小程序制作-背单词的小程序制作 - CSDN App】http://t.csdnimg.cn/WPvrB
i-阿松！: 我已经将这个项目开源了，这个里边有演示视频的链接【微信小程序-词汇大师项目分享 - CSDN App】http://t.csdnimg.cn/ZQS6l
2202_75352922: 好好好好哈哈哈