c语言——二叉树

server/2024/9/25 22:59:07/

目录

目录

二叉树关键概念理解

一颗拥有1000个结点的树度为4，则它的最小深度是？

那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，

求二叉树大小

求叶子结点个数 

求深度

求第k层的结点个数

寻找值为k的结点

遍历打印

判断二叉树是否是完全二叉树

销毁

二叉树的构建 

 1.    求二叉树大小

 2.    求叶子结点个数 

3.求深度

需要注意的是：需要每次存储每次递归的大小， 优化时间

4.求第k层的结点个数

5.寻找值为k的结点

 需要注注意的是需要存储每次递归的ret，优化时间

6.层序遍历打印

前序： 根->左子树->右子树

中序： 左子树->根->右子树

后序： 左子树->右子树->根

层序 ：一层一层打印

7. 判断二叉树是否是完全二叉树

8.销毁

一颗拥有1000个结点的树度为4，则它的最小深度是？

那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，

求二叉树大小

求叶子结点个数 

求深度

求第k层的结点个数

寻找值为k的结点

遍历打印

判断二叉树是否是完全二叉树

销毁

二叉树的构建 

 1.    求二叉树大小

 2.    求叶子结点个数 

3.求深度

需要注意的是：需要每次存储每次递归的大小， 优化时间

4.求第k层的结点个数

5.寻找值为k的结点

 需要注注意的是需要存储每次递归的ret，优化时间

6.层序遍历打印

前序： 根->左子树->右子树

中序： 左子树->根->右子树

后序： 左子树->右子树->根

层序 ：一层一层打印

7. 判断二叉树是否是完全二叉树

8.销毁

二叉树关键概念理解

二叉树的概念在这里就不进行过多的赘述，那么主要说一下我认为重要的部分，

第一点就是二叉树里面部分概念的理解：

就比如说，你对于如何构建二叉树，掌握的十分深刻，但刷题的时候对于一些题目所给的概念不清楚，导致看不明白题目，这课不好，

二叉树的概念如下图所示,其实都很简单，主要是当给他的名字时，你明不明白。

还有对于满二叉树与完全二叉树 需要注意的就是完全二叉树，最后一层，从左到右时必须连续的。 

 经过看过这两张图后，再加上我们原本的二叉树基础，我们看几道题：

一颗拥有1000个结点的树度为4，则它的最小深度是？

 如果我们了解度的概念，那么就很好计算出答案。

那么思路：最小度数就是当每个结点都是满的情况下，那么就为最小深度，

设高度为h，那么每个结点都是满的情况下，通过数学计算得出，此时总共结点数：（4^h-1)/3,那么h=5时，最大结点数为341，h=6时，为1365，

那么最小深度就为6.

 2-3树是一种特殊的树，它满足两个条件：

(1) 每个内部结点有两个或三个子结点

(2) 所有的叶结点到根的距离相同

如果一颗2-3树有10个结点，那么它有( )个叶结点

对于本道题，经过分析，我们得知，第二层一定是只有两个结点,或三个结点，

当为三个结点时，只有这一种情况：

 当为二个结点时：

再最多的情况下也只可以放九个

所以就只有6个叶子结点。

那么对于二叉树，只掌握这些是远远不够的，我们还需要掌握几个最基本的经典问题，

  1. 求二叉树大小

  2. 求叶子结点个数 

  3. 求深度

  4. 求第k层的结点个数

  5. 寻找值为k的结点

  6. 遍历打印

  7. 判断二叉树是否是完全二叉树

  8. 销毁

二叉树的构建 

//二叉树
typedef int BTDataType;
typedef struct BTNode
{BTDataType val;struct BTNode* left;struct BTNode* right;
}BTNode;
BTNode* Creat_Node()
{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);Node1->left = Node2;Node1->right = Node4;Node2->left = Node3;Node4->left = Node5;Node4->right = Node6;//Node6->right = Node7;return Node1;
}BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");}node->val = x;node->left = NULL;node->right = NULL;return node;
}

 接下来依次介绍

 1.    求二叉树大小

代码实现：

int BT_Size(BTNode* root)
{if (root == NULL){return 0;}return BT_Size(root->left) + BT_Size(root->right) + 1;
}

或者： 

int BT_Size(BTNode* root)
{return root == NULL ? 0 : BT_Size(root->left) +BT_Size(root->right) + 1;
}

 2.    求叶子结点个数 

 叶子结点有一个特点，那么就是左节点与右节点全为空，只要抓住这一点特点，利于递归，还是很好实现的。

int BT_Leaf_Size(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BT_Leaf_Size(root->left) +BT_Leaf_Size(root->right);
}

3.求深度

求二叉树深度可以转化为求左子树的深度，与右子树的深度，然后比比谁的大，然后左子树深度求法又可以分为，求左子树的左子树与右子树的深度，以此类推。

需要注意的是：需要每次存储每次递归的大小， 优化时间

int BT_Depth_Size(BTNode* root)
{if (root == NULL){return 0;}int left_Depth_Size = BT_Depth_Size(root->left);int right_Depth_Size = BT_Depth_Size(root->right);return left_Depth_Size > right_Depth_Size ?BT_Depth_Size(root->left) + 1 : BT_Depth_Size(root->right) + 1;
}

4.求第k层的结点个数

 思路就是首先我们要先找到第k层所在位置，然后每找到一个就利用递归然会去1；

int BT_Size_Levre_k(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BT_Size_Levre_k(root -> left, k - 1) +BT_Size_Levre_k(root -> right, k - 1);
}

5.寻找值为k的结点

 需要注注意的是需要存储每次递归的ret，优化时间

BTNode* BTFind_Data_k(BTNode* root, int k)
{if (root == NULL){return NULL;}if (root->val == k){return root;}BTNode* ret1 = BTFind_Data_k(root->left, k);if (ret1){return ret1;}BTNode* ret2 = BTFind_Data_k(root->right, k);if (ret2){return ret2;}return NULL;
}

6.层序遍历打印

前序： 根->左子树->右子树

void Prev_Order(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->val);Prev_Order(root->left);Prev_Order(root->right);
}

中序： 左子树->根->右子树

void In_Order(BTNode* root)
{if (root == NULL){return;}In_Order(root->left);printf("%d ", root->val);Prev_Order(root->right);
}

后序： 左子树->右子树->根

void Post_Order(BTNode* root)
{if (root == NULL){return;}In_Order(root->left);Prev_Order(root->right);printf("%d ", root->val);
}

层序 ：一层一层打印

层序打印需要运用到栈，这里不提供栈的实现了，只提供实现层序打印的代码

void Lever_Order(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->val);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");
}

7. 判断二叉树是否是完全二叉树

 检查是否为完全二叉树，也是利用栈的知识来实现，因为在层序遍历的时候，是出完一层的时候也会在进完下一层，并且顺序是完全按照一层一层从左到右

所以实现思路就为，先找到第一个为空的结点，然后查看他后面的结点是不是为空，如果为空，那么就为完全二叉树，反之不是。

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 != NULL){return false;}if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}return true;
}

8.销毁

void BinaryTreeDestory(BTNode* root)//后序顺序释放
{if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}

还有一些结论：

1：二叉树第i层上的结点数目最多为2i-1(i>=1)

2：深度为k的二叉树至多有2^(k) - 1个结点（k>=1）,叶子节点为 2^(k - 1) 

3：包含n个结点的二叉树的高度至少为( log2(n) )+1

4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

5：leftchild=parent*2+1;   rightchild=parent*2+2;

6:  parent=(child-1)/2;

7: 令度为0，的结点个数为N0,度为2的个数为N2

那么N0=N2+1；


http://www.ppmy.cn/server/24885.html

相关文章

python生成随机验证码图片+噪声

python生成随机验证码图片+噪声

参数：图片宽高、验证码个数，文字大小 def check_code(width90, height30, length4, font_size26):code []from PIL import Image, ImageDrawimg Image.new(modeRGB, size(width, height), color(255, 255, 255))draw ImageDraw.Draw(img, modeRGB)def…
阅读更多...
C++信息学奥赛 数据结构认识

C++信息学奥赛 数据结构认识

数据结构 1.1数据结构分类 1.2基本数据类型 1.3数字编码 1.4字符编码 1.1数据结构分类 数据结构如同一副稳固而多样的框架。为数据的有序组织提供了蓝图，算法得以在此基础上生动起来。 常用的数据结构包括哪些 ， ， &…
阅读更多...
Unity 数字字符串逗号千分位

Unity 数字字符串逗号千分位

使用InputField时处理输入的数字型字符串千分位自动添加逗号，且自动保留两位有效数字 输入：123 输出：123.00 输入：12345 输出：12,345.00 代码非常简单 using UnityEngine; using TMPro;public class …
阅读更多...
【MyBatis】进阶使用 (动态SQL)

【MyBatis】进阶使用 (动态SQL)

动态SQL \<if>\<trim>\<where>\<set>\<foreach>\<include> 在填写表单时&#xff0c;有些数据是非必填字段&#xff08;例如性别&#xff0c;年龄等字段&#xff09;&#xff0c;那就需要在接收到参数时判断&#xff0c;根据参数具体的情况…
阅读更多...
Docker--compose概述与部署

Docker--compose概述与部署

目录 一、概述 1. Compose简介 1.1 docker compose常用命令 1.2 Compose配置常用字段 2. YAML简介 2.1 YAML支持的数据结构 2.2 YML文件编写注意事项 2.3 Docker Compose文件结构 3. Docker-Compose安装 ​编辑 4.docker Compose撰写nginx 镜像 1. 准备环境 ​编辑…
阅读更多...
HaLo-NeRF：利用视觉和语言模型对场景的精准定位和细粒度语义理解

HaLo-NeRF：利用视觉和语言模型对场景的精准定位和细粒度语义理解

包含大量摄影师拍摄的照片的互联网图像集有望实现对大型旅游地标的数字探索。然而&#xff0c;先前的工作主要集中在几何重建和可视化上&#xff0c;忽略了语言在为导航和细粒度理解提供语义界面方面的关键作用。 项目&#xff1a;HaLo-NeRF: Learning Geometry-Guided Semant…
阅读更多...
MongoDB聚合运算符：$size

MongoDB聚合运算符：$size

MongoDB聚合运算符&#xff1a;$size 文章目录 MongoDB聚合运算符&#xff1a;$size语法使用举例 $size聚合运算符返回数组中元素的数量。 语法 { $size: <expression> }<expression>为可解析为数组的表达式。 使用 $size 的参数必须解析为数组。如果 $size 的参…
阅读更多...
vue2 点击预览本地 word excle pdf 文件

vue2 点击预览本地 word excle pdf 文件

安装 考虑到三个包加一起的话会比较大&#xff0c;所以拆成了三个包&#xff0c;需要哪个自行安装即可。 //docx文档预览组件 npm install vue-office/docx//excel文档预览组件 npm install vue-office/excel//pdf文档预览组件 npm install vue-office/pdf npm i --save vue…
阅读更多...
最新文章

Copyright @ 2022~2023