【数据结构】二叉树（下）
二叉树的链式结构链式二叉树的增删查改是没有意义的，建立在二叉树底子上的搜刮二叉树才具备增删查改的意义。但是链式二叉树是底子，就像修房子得先打地基一样。
二叉树的遍历
首先确定一个概念，二叉树分为空树和非空树，只要黑白空树就有根节点、根节点的左子树和根节点的右子树。二叉树的定义是递归式的。
二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操纵，并且每个节点只操纵依次。访问节点所做的操纵依赖于具体的应用问题，遍历是二叉树上最重要的运算之一，也是二叉树上进行别的运算的底子。
二叉树一共有四种遍历方式，前序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历）和层序遍历。
前序遍历（先根遍历）
访问根节点的操纵发生在遍历其左右子树之前。在遍历时，会不断向下遍历知道碰到空树才制止。
https://i-blog.csdnimg.cn/blog_migrate/05c0c6b0902c258e80c2ae25f1bd569c.png
void PrevOrder(BTNode* root)
{
if (NULL == root)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->深蓝色->粉色->金色->紫色->青色。
https://i-blog.csdnimg.cn/blog_migrate/5dfe973c3711b16c06138522df05358f.png
中序遍历（中根遍历）
访问根节点的操纵放生在遍历其左右子树之间。
https://i-blog.csdnimg.cn/blog_migrate/8cdc7aeca8c4b82aec8cf10e0d8049ca.png
void InOrder(BTNode* root)
{
if (NULL == root)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。
https://i-blog.csdnimg.cn/blog_migrate/5dd42836e95c0d4aa3a6f8d1cbb9c9a7.png
后序遍历（后根遍历）
访问根节点的操纵发生在遍历其左右子树之后。
https://i-blog.csdnimg.cn/blog_migrate/e2af209f28ae5f60adf583549763887c.png
void PostOrder(BTNode* root)
{
if (NULL == root)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。
https://i-blog.csdnimg.cn/blog_migrate/5dd44a729a2b6bea3adde6bc013e1a92.png
层序遍历
从第一层开始，每层从左到右，一层一层的走。四种遍历中，只有层序遍历黑白递归的，它采用的是队列来实现的。
https://i-blog.csdnimg.cn/blog_migrate/92b10c7915c2df161c9f13352a95961a.png
void LevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
// 先将根节点存入队列
if (root)
QueuePush(&q, root);
// 判空，如果为空就不执行以下语句
while (!QueueEmpty(&q))
{
// 获取队头，打印之后，移出队列
BTNode* front = QueueFront(&q);
printf("%d ", front->data);
QueuePop(&q);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
QueueDestroy(&q);
}
https://i-blog.csdnimg.cn/blog_migrate/2829234bf5e7ee85058b0ae572248131.png
二叉树的构建
二叉树的构建根据三种递归的遍历方式进行构建，可以进行前序、中序、后序构建，我这里利用的是前序构建。
BTNode* CreatBinaryTree(BTDataType* a, int* pi)
{
if (-1 == a[*pi])
{
(*pi)++;
return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
if (NULL == root)
{
perror("malloc fail");
exit(-1);
}
root->data = a[(*pi)++];
root->left = CreatBinaryTree(a, pi);
root->right = CreatBinaryTree(a, pi);
return root;
}
二叉树的节点数
int TreeSize(BTNode* root)
{
if (NULL == root)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色，末了返回的值是6。
https://i-blog.csdnimg.cn/blog_migrate/d73346b0fa894e0b83b1bd1b9c77ddfe.png
二叉树的叶子数
int TreeLeafSize(BTNode* root)
{
if (NULL == root)
{
return 0;
}
if (NULL == root->left && NULL == root->right)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为3。
https://i-blog.csdnimg.cn/blog_migrate/541d7e080ded7df159dff5d7f63fe513.png
二叉树的高度
int TreeHeight(BTNode* root)
{
if (NULL == root)
{
return 0;
}
int left = TreeHeight(root->left);
int right = TreeHeight(root->right);
return(left > right ? left : right) + 1;
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为3。
https://i-blog.csdnimg.cn/blog_migrate/737b5cae36641cb00f68297c1f3e096f.png
二叉树K层节点数
int TreeKLevelSize(BTNode* root, int k)
{
if (NULL == root)
{
return 0;
}
if (1 == k)
{
return 1;
}
return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为3。
https://i-blog.csdnimg.cn/blog_migrate/945571e8ed73d4500eca3e5009b25678.png
查找值为X的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (NULL == root)
return NULL;
if (x == root->data)
return root;
BTNode* ret1 = TreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = TreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为数字5节点的地点。
https://i-blog.csdnimg.cn/blog_migrate/b94223b682801ed2ce6365111ccb6d51.png
判定二叉树是否为完全二叉树
bool TreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
// 若队列为空，则不执行
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
// 判断front是否为空，为空则跳出循环
if (!front)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
// 若队列为空，则不执行
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
二叉树的烧毁
// 二叉树销毁
void TreeDestory(BTNode* root)
{
if (NULL == root)
{
return;
}
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]