数据结构与算法：二叉树
目录树的概念
二叉树
二叉树性质
二叉树的遍历
前序遍历
中序遍历
后序遍历
层序遍历
二叉树节点个数
二叉树叶子节点个数
二叉树高度
二叉树第k层节点个数
二叉树查找值为x的节点
判定二叉树是否是完全二叉树
二叉树销毁
树的概念
树型结构是一类紧张的非线性数据结构。此中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树，也就是说它常是根朝上，而叶朝下的。
树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机范畴中也得到广泛应用，如在操作系统中,可用树来表示文件系统的结构。又如在数据库系统中，树形结构也是信息的紧张组织形式之一 。
树在不同范畴也有不同的定义。
1、在数学中，树是一种无向图，此中不存在环路（即无回路），且任意两个结点之间有且仅有一条简单路径相连 。这种定义主要用于图论和离散数学中，用于研究树的性质和特征。
2、在操作系统中，树是一种用于表示文件系统的结构，此中根目录位于树的顶部，子目录和文件位于根目录下 。这种定义主要用于操作系统计划和文件管理。
3、在数据库中，树是一种用于表示层次关系的数据结构，树结构常用于实现数据库的索引、表示层次数据关系（如组织结构、分类目录）以及优化查询操作。这种定义主要用于数据库计划和数据管理，以进步数据检索服从和结构化数据的存储。
根本术语：
[*]1.结点：包含一个数据元素及若干指向其子树的分支；
[*]2.结点的度：一个结点拥有的子树的数目；
[*]3.叶子或终端结点：度为0的结点；
[*]4.非终端结点或分支结点：度不为0的结点；
[*]5.树的度：树内各结点的度的最大值；
[*]6.孩子结点或子结点：结点的子树的根称为该结点的孩子结点或子结点；
[*]7.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的双亲结点或父结点；
[*]8.兄弟结点：同一个双亲的孩子之间互称兄弟；
[*]9.祖先结点：从根到该结点所经分支上的全部结点；
[*]10.子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；
[*]11.结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 L 层．则其子树的根就在第 L + 1层；
[*]12.堂兄弟结点：其双亲在同一层的结点互为堂兄弟；
[*]13.树的深度或高度：树中结点的最大层次；
[*]14.森林：由m（m > 0）棵互不相交的树的聚集称为森林;
[*]15.有序树和无序树：树中结点的各子树从左到右是有序次的，不能互换，称该树为有序树，否则称为无序树；
[*]16.路径和路径长度：路径是由树中的两个结点之间的结点序列构成的。而路径长度是路径上所经过的边的个数
二叉树
https://i-blog.csdnimg.cn/direct/9cdc9964f3ab4910af2f702244cfd6a5.png
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点举行相应的操作，并且每个结点只操作一次。访问结点所做的操作依靠于详细的应用问题。 遍历是二叉树上最紧张的运算之一，也是二叉树上举行其它运算的基础。
二叉树性质
1.若规定根节点的层数为1，则一棵非空二叉树上的第 i 层最多有https://latex.csdn.net/eq?2%5E%7B%28i-1%29%7D个节点
2.若规定根节点的层数为1，则深度为 h 的二叉树的最大节点数是https://latex.csdn.net/eq?2%5E%7Bh%7D-1
3.对任何一棵二叉树，如果度为0其叶节点个数为https://latex.csdn.net/eq?n_%7B0%7D，度为2的分支结点个数为https://latex.csdn.net/eq?n_%7B2%7D,则有https://latex.csdn.net/eq?n_%7B0%7D%20%3D%20n_%7B2%7D%20+%201
4.若规定根节点的层数为1，具有 n 个节点的满二叉树的深度，https://latex.csdn.net/eq?h%20%3D%20%5Clog_%7B2%7D%28N+1%29
5.对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组序次对以是结点从0开始编号，则对于序号为 i 的结点有：
[*]若 i > 0, i 位置结点的双亲序号：(i - 1) / 2; i = 0, i 为根节点编号，无双亲结点。
[*]若 2i+ 1 < n ，左孩子序号 2i+ 1， 2i+ 1 >= n 则为左孩子
[*]若 2i+ 2 < n，右孩子序号：2i+ 2，2i+ 1 >= n 则无右孩子
二叉树的遍历
https://i-blog.csdnimg.cn/direct/1e00088d623c4daaa3e08bb22b0c75f0.png
前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
//前序
void Preorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
Preorder(root->left);
Preorder(root->right);
} 中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
//中序
void Inorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
} https://i-blog.csdnimg.cn/direct/187e304f89554bda9523365f99f68a8b.png
后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
//后序
void Posorder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
Posorder(root->left);
Posorder(root->right);
printf("%d ", root->data);
}
层序遍历
层序遍历（也称为广度优先遍历）是二叉树遍历的一种方法，其根本思想是从根节点开始，按照从上到下、从左到右的序次访问二叉树的每一层节点。
层序遍历通常使用队列来实现：
[*]将根节点放入队列中。
[*]当队列不为空时，循环执行以下操作：
[*]从队列中弹出一个节点，访问该节点。
[*]如果该节点有左子节点，将左子节点加入队列。
[*]如果该节点有右子节点，将右子节点加入队列。
[*]继承执行步调2，直到队列为空。
void TreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//上一层带下一层
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
QueueDestory(&q);
}
二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
static int size = 0;
if (root == NULL)
return 0;
else
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}不能如许写，如许写每次调用这个函数都会累加
https://i-blog.csdnimg.cn/direct/2199e07327b748458722544296f83b53.png
可以如许写
int size = 0;
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}但是每次调用这个函数的时候，都要重置一下size。
最好的方法 分治递归
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 :
BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) +
BinaryTreeLeafSize(root->right);
} 什么是叶子结点呢？通常来讲在一棵树里面，如果一个结点没有左子树和右子树，那么它就是叶子。左子树和右子树为空，那么叶子结点个数加1，返回给上一层。
二叉树高度
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeHeight(root->left) > BinaryTreeHeight(root->right) ?
BinaryTreeHeight(root->left) + 1 : BinaryTreeHeight(root->right) + 1;
} 上面这种方法存在服从问题，原因是递归返回后函数栈帧会销毁，没有记录，
int BinaryTreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int left = BinaryTreeHeight(root->left);
int right = BinaryTreeHeight(root->right);
return left > right ? left + 1 : right + 1;
}
//int BinaryTreeHeight(BTNode* root)
//{
// if (root == NULL)
// return 0;
// return fmax(BinaryTreeHeight(root->left), BinaryTreeHeight(root->right)) + 1;
//}
二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) +
BinaryTreeLevelKSize(root->right, k - 1);
} https://i-blog.csdnimg.cn/direct/17d6c973334e4ca99f8c07a45d5706d8.png
求第k层结点个数，需要转化成当前问题和子问题。比如说，求第3层结点的个数，那么对这棵树的第一层来说，从它开始，求它向下的3层。然后k减1。对于第二层来说，求从它开始向下的第2层，k减1。对于第三层来说，就是求从它开始向下的第1层，为第1层时，返回1给上一层。
二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
} 如果走到叶子节点的下一个，即root为空，就返回空。如果在左子树找到了，那么在右子树就没必要找了，就直接返回这个节点。但是一定要记录这个节点，因为递归返回会销毁函数栈帧，你不返回给上层这个找到的节点的记录，上层不知道你找到没有，就以为没有找到。继承返回给它的上层。 如果左子树没有找到，右子树也没有找到，就返回空。
https://i-blog.csdnimg.cn/direct/5c057f35e3494941b56dc9de2a3267c1.png
判定二叉树是否是完全二叉树
需要用到层序遍历
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇到第一个空，就可以开始判断，如果队列中还有非空，那就不是完全二叉树
if (front == NULL)
break;// 跳出循环，不再进行层序遍历
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
//开始判断队列中已有的数据
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//遇到非空,不是完全二叉树
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
} 首先定义一个队列，初始化队列，如果树不为空，那么让树的根结点入队列。通过一个while循环，可以把二叉树的全部节点全部遍历一遍，让它的节点入队列和出队列。这个while循环竣事后吗，二叉树中的全部结点全部过了一遍，就算有 没有入队列的结点，也没有关系，因为这时只需要判定现在的队列中，是否还存在数据，如果存在，则说明不是完全二叉树，返回false。反之，说明为完全二叉树，返回true。这一层判定通过一个while循环完成。
二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
return;
BinaryTreeDestory((*root)->left);
BinaryTreeDestory((*root)->right);
free(*root);
} 二叉树的销毁可以看成一个后序遍历，先左子树销毁，然后右子树销毁，最后根节点销毁。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]