😏专栏导读
👻作者简介：M malloc，致力于成为嵌入式大牛的男人
👻专栏简介：本文收录于 初阶数据结构，本专栏主要内容讲述了初阶的数据结构，如顺序表，链表，栈，队列等等，专为小白打造的文章专栏。
👻相关专栏推荐：LeetCode刷题集，C语言每日一题。
🤖文章导读
本篇文章我将详细的讲解关于树的知识点
🙀树的预备知识
前情介绍
对于大量的输入数据，链表的线性访问时间太慢，不宜使用。本片文章，我将讲述一种简单的数据结构，其大部分操作的时间复杂度为O(log n)。
树
树(tree)可以用几种方式定义。定义树的一种自然的方式是递归的方法。一棵树是一些节点的集合。这个集合可以是空集;若非空，则一棵树由称做根(root)的节点r以及0个或多个非空的(子)树 T1，T2，…，T 组成，这些子中每一的根都被来自根的一条有向的边(edge)所连接。
每一棵子树的根叫做根r的儿子(child)而r每一棵子的根的父亲(parent)。下图是显示用递归定义的典型的树。
从递归定义中我们发现，一棵树是 N 个节点和N - 1条边的集合，其中的一个节点叫做根。存在 N -1条边的结论是由下面的事实得出的，每条边都将某个节点连接到它的父亲，而除去根节点外每一个节点都有一个父亲,如下图所示。
根节点，父亲节点，叶子节点，兄弟节点的详解
在上图的树中，节点A是根结点，节点F有一个父亲A并且有儿子K、L、M。每一个节点可以有任意多个儿子，也可以没有儿子也就是0个，但是只能有一个父亲。没有儿子的节点成为叶子节点(leaf)；上图的叶子节点是B,C,H,I,P,Q,K,L,M和N。具有相同父亲的节点称为兄弟节点(sibing);因此K、L和M都是兄弟。
深度(depth)
首先，根的深度为0。在上图中E节点的深度为1，但是高为2，F的深度为1，高为1，该树的高为3，一个树的深度等于它的最深的树叶的深度；该深度总是等于这颗树的高。
🙀二叉树
二叉树(binary tree)是一棵树，其中每个节点都不能有多于两个的儿子。
二叉树的一个性质是平均二叉树的深度要比 N 小得多这个性质有时很重要。分析表明，这个平均深度为 O(/N).而对于特殊类型的二叉树，即二叉查找树(binary search tree)其深度的平均值是 O(log N)。不幸的是，正如下图中的例子所示，这个深度是可以大到 N -1的。
最坏情况的二叉树
😳树的代码实现及其各类讲解
🌲树的结构体初始化
树的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
二叉树，顾名思义就是一个左子树，一个右子树，所以在这里我们定义了一个结构体类型的左子树和右子树。那么是不是还要存放数据呢？对的没错！所以还需要一个数据域data
手动创建一个树和开辟新节点
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
在上述代码中运用到了malloc这个库函数。这是在堆上动态开辟一块区域，把我们想要存入的值再放进去。
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode * node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
BTNode* node7 = BuyNode(7);
BTNode* node8 = BuyNode(8);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
//node5->left = node7;
node2->right = node7;
node3->left = node8;
return node1;
}
上述是手动进行指向节点，就是我们要对应着一幅图进行画它的指向，比如，node1的左边指向node2，就说明node2在node1的左边，然后node1的右边存放着node4，就说明node4的父亲是node1，也就是node4在node1的右边，也就是下图所示
树的前序遍历
其实在树的前序遍历过程中其实就是递归的过程。有一个很好的口诀，就是中左右，意思就是先遍历根节点，然后在遍历左子树，再从左子树递归下去，右子树也是样的操作。
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return NULL;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
树的中序遍历
那么中序遍历呢？中序遍历的口诀是左中右，就是先遍历左子树，在遍历根节点，右子树。就是这样的一系列的操作就行啦
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return NULL;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
树的后序遍历
后序遍历的自然也是有口诀的啦！我们的口诀是左右中，此时我们的根节点是最后才遍历的不知道你们发现没有！文章来源：https://www.toymoban.com/news/detail-581365.html
void taorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return ;
}
taorder(root->left);
taorder(root->right);
printf("%d ", root->data);
}
总结
在本片文章中只是粗略的介绍了一下树的前中后序的遍历，其实代码的思路是很简单的就是几个递归的操作，大家多画画递归的展开图就能理解啦！那么这只是树的上篇。在树的下篇中，我将详细讲解怎么利用递归求出树的一系列操作等问题，我是爱你们的M malloc 我们下期再见！文章来源地址https://www.toymoban.com/news/detail-581365.html
到了这里，关于【数据结构之树】初阶数据结构之树的实现及其各种方式(上)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
