玩转二叉树c语言,C语言中二叉树
文章目录前言1。部分选择题1.1 1.2 1.3由已知遍历序列画出原树的结构1.4单边树1.5 2。OJ题刷起来！KY11二叉树遍历100棵相同的树101对称二叉树572另一棵树的子树226翻转二叉树结论前言上一篇博客我带你体验了链式二叉树的操作。现在我们来看看二叉树的相关题目，一起巩固知识点！
点击我来回顾上一篇博客的内容！入口
1.部分选择题1.1设一棵二叉树有3个叶节点，8个度为1的节点，那么二叉树的节点总数是()。
A.11
B12
C.13
草14
设Ni代表节点数I，则节点总数N=N0 N1N2。
节点数与节点边数的关系：有N个节点的树有N-1条边。
与边缘度的关系：N-1=N1 2 * N2
因此：N0 N1 N2-1=N1 2 * N2
因此，得到：N0=N2 1
回到原问题，可以得到N0=3，N1=8，N2=2。
所以答案是3 8 2=13。
1.2具有n个元素的完全二叉树的深度是()
答案：logN 1是一棵高度为h的完全二叉树，节点数为：2 (h-1)-1 n=2 h-1。
即log(n 1)=h log(n 1) 1
这里需要注意的是n附近区间的开合。
一棵完全二叉树的最小节点数是2 (h-1)-11，所以它是n 2^(h-1)-1.
1.3从已知的遍历序列画出原树的结构。已知二叉树的中遍历序列为JGDHKBAELIMCF，后遍历序列为JGKHDBLMIEFCA，其前遍历序列为()
A.ABDGHJKCEFILM
B.ABDGJHKCEILMF
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF，我开始的问题是错的，因为我把它当成了完全二叉树，但是题目没有说是完全二叉树。
主旨：根节点可以从后续遍历中确定为A，A的左右子树可以通过中序遍历确定。然后从后续遍历继续确定A的左右子树的根节点，依次向下判断。
于是我画了一个分析图，如下？
给定二叉树的前序遍历序列为ABDEC，中间遍历序列为BDEAC，二叉树()
A.这是一棵完整的二叉树
B.是完全二叉树，不是完全二叉树
C.不是完整的二叉树
d是一棵在所有节点都没有右子树的二叉树。这个问题的思路和上一个是一样的。
已知二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，所以其后序遍历序列为()
A.4 2 5 7 6 9 1
B.4 2 7 5 6 9 1
C.4 7 6 1 2 9 5
D.4 7 2 9 5 6 1这个问题还是和上面两个问题一样！
1.4单边树非空二叉树的第一个遍历序列正好与第二个遍历序列相反，那么二叉树必须满足()
A.所有节点都没有左子节点。
B.所有节点都没有正确的子节点。
C.只有一个叶节点
D.最多只有一个节点。如果前序遍历和后序遍历的顺序正好相反，说明是单边树，比如下面这种由前序和后序序列组成的树结构：
1345(垂直)
54321
对于单侧树，只有一个叶节点。
1.520.如果二叉树的前序遍历结果是ABCD，则有()种不同的二叉树满足条件。
A.13
B.14
C.15
草16
首先，这个二叉树的高度必须在3到4层楼之间：
三层：
A(B(C，D)，())，A(()，B(C，D))，A(B(C，())，D)，A(B(()，C)，D)，
A(B，C(D，()))，A(B，C(()，D))
四层：
如果是四级树，那就是单面树。每个级别只有一个节点。除了根节点，其他节点都有两种选择，是在上层节点的左侧还是右侧，所以有八种222。
总共有14种。
2.刷一下2。OJ提问！KY11二叉树遍历
牛网的KY11二叉树遍历？入口
这个问题需要我们用一阶遍历操作从数组中读取一棵树，构造树的基本结构，然后用中阶遍历打印出树。
我们之前学过前序遍历的操作，这里只需要改变前序遍历中的printf操作来构建新的树。
因为涉及到对Tao I的多次调用，函数中的I需要获取地址。要保证我调用多次会同步构建树的节点，赋值后要递归构建左右子树。最后，节点的地址标题中的#为空，可以直接返回# includesdio.h。
#包含stdlib.h
#包含stdbool.h
typedef char BTDataType
typedef struct BTreeNode
{
BTDataType数据；
struct BTreeNode * left
struct BTreeNode * right
} BTNode
//二叉树中的顺序遍历
void BTreeInOrder(BTNode* root)
{
if (root==NULL){
返回；
}
BTreeInOrder(根左)；
printf(%c ，root-data)；
BTreeInOrder(根右)；
}
BTNode* CreatTree(char *arr，int*i)
{
if (arr[*i]==#){
(* I)；
返回NULL
}
Bt node * new node=(Bt node *)malloc(sizeof(Bt node))；
new node-data=arr[(* I)]；//我必须得到地址。
newnode- left=CreatTree(arr，I)；//递归构建左侧子树
newnode- right=CreatTree(arr，I)；//递归构建右边的子树
返回newnode
}
int main()
{
char arr[100]；
scanf(%s ，arr)；
int I=0；
BTNode* root=CreatTree(arr，I)；
BTreeInOrder(根)；
返回0；
}100棵一样的树
Leetcode: 100。同一棵树
题目很简单。给定两棵树的根节点，要求我们判断这两棵树是否相同。
如果两棵树都是空的，那么树是一样的；如果其中一个是空的，另一个不是空的，树就不一样了；如果两者都不为空，但节点值不同，则树不同；然后递归判断左子树和右子树，将它们的结果相加，其中一个为假，返回假布尔Issame树(structtree * p，structtree * q) {
If(p==NULL q==NULL)//比较两个节点是否都为空，以及两个节点都为空还是为真
返回true
If(p==NULLq==NULL)//如果一个为空，另一个不为空，则为false。
返回false
如果(p- val！=q- val)//不为空，判断val的值是否相等。
返回false
//递归确定左子树和右子树是否相等。
返回isSameTree(p- left，q- left)
isSameTree(p-右，q-右)；
}
学完这个问题，下面的一些问题其实只要改一下它的代码就可以用了？
什么？你不相信我？然后看下面这个问题！
101对称二叉树
Leetcode: 101。对称二叉树
题目很简单。判断是不是两边对称的树。
这和判断树相等有什么区别？只需要改变左右子树的判断就可以了吧？
直接调用上一题的代码！注意最后返回值是P的左边，Q的右边进行判断。
bool _ isSameTree(struct TreeNode * p，struct TreeNode* q){
If(p==NULL q==NULL)//比较两个节点是否都为空，以及两个节点都为空还是为真
返回true
If(p==NULLq==NULL)//如果一个为空，另一个不为空，则为false。
返回false
如果(p- val！=q- val)//不为空，判断val的值是否相等。
返回false
//递归判断左子树和右子树是否对称相等。
return _isSameTree(p- left，q- right)
_isSameTree(p-右，q-左)；
}
bool is symmetric(struct TreeNode * root){
return _isSameTree(根左，根右)；
}
哈哈，是不是很棒？别急，还有别的话题可以懒！
52另一棵树的子树
Leetcode: 572。另一棵树的子树
在这个问题中，我们要判断一棵树是否是另一棵树的子树，类似于判断一个字符串是否是另一个字符串的子串。
其实只需要递归判断每个节点的左右子树是否和subRoot一样！
bool _ isSameTree(struct TreeNode * p，struct TreeNode* q){
If(p==NULL q==NULL)//比较两个节点是否都为空，以及两个节点都为空还是为真
返回true
If(p==NULLq==NULL)//如果一个为空，另一个不为空，则为false。
返回false
如果(p- val！=q- val)//不为空，判断val的值是否相等。
返回false
//递归确定左子树和右子树是否相等。
return _isSameTree(p- left，q- left)
_isSameTree(p-右，q-右)；
}
bool issub tree(struct TreeNode * root，struct TreeNode* subRoot){
//if(root==NULL subRoot==NULL)
//返回true
//if(root！=NULL子根==NULL)
//返回true
//让isSametree函数比较两者
if(root==NULL)
返回false
if(_isSameTree(root，subRoot))
返回true
//只要左右有一个返回true，就是子树。
返回问题树(左根，子根)
isSubtree(root- right，subRoot)；
}
你感觉好吗？再来一次！
26翻转二叉树
Leetcode: 226。翻转二叉树
这个问题的思路是这样的！
如果是空树，不需要翻转。如果不是空的，就交换节点的左右子树(交换后不用担心找不到子树)。不需要单独制作空的子树，根节点为空时可以一起交换。快速返回snaps，代码写好了！
void _ invert tree(struct TreeNode * root)
{
If(root==NULL)//设置退出条件，如果根节点为空则返回。
返回；
//让另外两个值接收原来的左右节点
struct TreeNode * left=root-left；
struct TreeNode * right=root-right；
//更改左右节点
根-右=左；
根-左=右；
//递归子树
_invertTree(根-左)；
_invertTree(根-右)；
}
结构树节点*反转树(结构树节点*根){
If(root==NULL)//确定空树
返回NULL
_invertTree(根)；
返回根目录；
}
这个结论到此结束。如果对所涉及的话题一无所知，可以在评论区提出来！
如果你知道，OJ可以偷懒，呵呵呵.
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。