数据结构第十讲：二叉树OJ题

1.单值二叉树

链接: OJ题链接

typedef struct TreeNode TreeNode;bool isUnivalTree(struct TreeNode* root) {//这一题要对二叉树结点进行逐一遍历，这里要用到递归//递归结束条件：if(root == NULL){return true;}if(root->left && root->left->val != root->val){return false;}if(root->right && root->right->val != root->val){return false;}//我们想要的是每个结点都具有相同的值，所以就需要左树和右树上结点的数据都相同return isUnivalTree(root->left) && isUnivalTree(root->right);
}

2.相同的树

链接: OJ题链接

typedef struct TreeNode TreeNode;bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//要检查两棵树是否相同，就要同时遍历两棵树的结点，还是要用到递归//递归结束条件//当两个结点全为空时，返回trueif(p == NULL && q == NULL){return true;}//当两个结点不全为空//当两个结点中有一个为空时，说明两棵树不同if(p == NULL || q == NULL){return false;}//当两棵树的结点值不同时，返回falseif(p->val != q->val){return false;}//最后要得到的是两棵树是否相同，就要看两棵树的左节点树和右节点树是否相同return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

3.对称二叉树

链接: OJ题链接

这一题和上一题差不多，属于上一题的拓展，需要注意的是，这一题要求的是是否对称，而上一题要求的是是否相同，对称要求一棵树的左结点和另一棵树的右节点相同，就这一点与上一题不同

typedef struct TreeNode TreeNode;bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//要检查两棵树是否对称，就要同时遍历两棵树的结点，还是要用到递归//递归结束条件//当两个结点全为空时，返回trueif(p == NULL && q == NULL){return true;}//当两个结点不全为空//当两个结点中有一个为空时，说明两棵树不同if(p == NULL || q == NULL){return false;}//当两棵树的结点值不同时，返回falseif(p->val != q->val){return false;}//此时要求的是是否对称，所以递归对比的是左结点和右结点return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}bool isSymmetric(struct TreeNode* root) {if(root == NULL){return true;}//这里只需要检查二叉树根结点的左节点树和右节点树是否对称即可//与上一题不同的是，这里要求检查是否对称，不是相同，所以函数的内部实现要特别注意：return isSameTree(root->left, root->right);
}

4. 另一棵树的子树

链接: OJ题链接

这一题仍然需要利用相同的树那一题的方法，不同的是，对于这一题的返回值，return的应该是左树中存在目标子树或右树中存在目标子树，只要一颗树中存在目标子树，就返回true

typedef struct TreeNode TreeNode;bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//要检查两棵树是否相同，就要同时遍历两棵树的结点，还是要用到递归//递归结束条件//当两个结点全为空时，返回trueif(p == NULL && q == NULL){return true;}//当两个结点不全为空//当两个结点中有一个为空时，说明两棵树不同if(p == NULL || q == NULL){return false;}//当两棵树的结点值不同时，返回falseif(p->val != q->val){return false;}//最后要得到的是两棵树是否相同，就要看两棵树的左节点树和右节点树是否相同return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){//递归结束条件：if(root == NULL){return false;}if(isSameTree(root, subRoot)){return true;}//对于返回值，只要左右树中有一棵树中存在目标子树，就需要返回truereturn isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

5.二叉树的前序遍历

链接: OJ题链接

这一题与之前所写的前序遍历不同，之前所写的前序遍历都是将数直接打印出来，而这里的前序遍历要求将遍历的数依次存储在数组中，而且，题目还有一个提示：
也就是说，函数返回的是一个数组，数组是由动态内存开辟的空间

typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root)
{//递归结束条件if(root == NULL){return 0;}//需要返回的是根节点的数目+左节点树的结点树+右结点树的结点数return 1 + TreeSize(root->left) + TreeSize(root->right);
}void TreePreOrder(TreeNode* root, int* arr, int* i)
{if(root == NULL){return;}arr[(*i)++] = root->val;TreePreOrder(root->left, arr, i);TreePreOrder(root->right, arr, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {//1.首先，我们要确定需要开辟空间的大小，然后开辟空间//注意，这里要用*returnSize表示结点个数，从函数声明中可以分析得出*returnSize = TreeSize(root);int* arr = (int*)malloc((*returnSize)*sizeof(int));//2.其次就是递归遍历二叉树的结点，然后将结点的值存储在数组中int i = 0;TreePreOrder(root, arr, &i);return arr;
}

后续还要实现二叉树的中序遍历和二叉树的后续遍历，思路和这一个是一样的，自行实现即可

6.二叉树的中序遍历

链接: OJ题链接

typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root)
{if(root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);
}void TreeInOrder(TreeNode* root, int* arr, int* i)
{if(root == NULL){return;}TreeInOrder(root->left, arr, i);arr[(*i)++] = root->val;TreeInOrder(root->right, arr, i);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {//1.先求出需要开辟空间的大小*returnSize = TreeSize(root);//2.开辟空间int* arr = (int*)malloc((*returnSize) * sizeof(int));//3.将数据通过中序遍历进行存储int i = 0;TreeInOrder(root, arr, &i);return arr;
}

7.二叉树的后序遍历

链接: OJ题链接

typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root)
{if(root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);
}void TreeInOrder(TreeNode* root, int* arr, int* i)
{if(root == NULL){return;}TreeInOrder(root->left, arr, i);TreeInOrder(root->right, arr, i);arr[(*i)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {//1.先求出需要开辟空间的大小*returnSize = TreeSize(root);//2.开辟空间int* arr = (int*)malloc((*returnSize) * sizeof(int));//3.将数据通过后序遍历进行存储int i = 0;TreeInOrder(root, arr, &i);return arr;
}

8.二叉树的构建及其遍历

链接: OJ题链接

与力扣的题目不同，这道题出自于牛客网，所给出的不仅仅是一个片段，是一段程序的接口，而是自己手动实现全部的代码：

这道题中，数组插入二叉树的结构应该为：

下面的CreatTree方法应该好好记着：

//二叉树结点结构体
typedef struct TreeNode
{char val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;TreeNode* CreatTreeNode(char x)
{TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));newnode->val = x;newnode->left = newnode->right = NULL;return newnode;
}
//--------------------------------------------------------------------------------
TreeNode* CreatTree(char* arr, int* i)
{//对于树的创建是一个新的方法，要好好记着//此方法仍需要使用到递归//递归结束条件:当arr中的数据为#时，代表遇到的是NULL，此时需要返回NULL被存储if(arr[(*i)] == '#'){(*i)++;return NULL;}//当不为空时，开辟空间即可TreeNode* root = CreatTreeNode(arr[(*i)++]);root->left = CreatTree(arr, i);root->right = CreatTree(arr, i);//我们需要返回的是头结点return root;
}
//--------------------------------------------------------------------------------
void TreeInOrder(TreeNode* root)
{if(root == NULL){return;}TreeInOrder(root->left);printf("%c ", root->val);TreeInOrder(root->right);
}int main() {//1.创建一个数组，使用数组接收传入的字符串char arr[100];//题目要求长度不超过100，所以这里可以直接写scanf("%s", arr);//2.其次就是使用结构体来接受这些数据//将数组中的数据挨个放到二叉树中int i = 0;TreeNode* root = CreatTree(arr, &i);//3.树创建完成之后，就是简单的中序遍历TreeInOrder(root);return 0;
}

9.二叉树选择题

9.1二叉树性质1

对于任意一颗二叉树，如果度为0的结点的个数为n0，度为2的结点的个数为n2，则有：n0 = n2+1

证明上述性质：

9.2二叉树性质2

对于一棵二叉树，假设它：
前序排列：EFHIGJK
中序排列：HFIEJKG
后序排列：HIFJKGE
前序排列首先访问的是根节点，后序排列最后访问的是根节点，中序访问中间访问的是根节点，可以根据根节点的位置推出左子树和右子树

9.3二叉树性质三

对于完全二叉树来说，它拥有的度为1的结点只能有0/1个：
当完全二叉树有2n个结点时，度为1的结点有1个
当完全二叉树有2n+1个结点时，度为1的结点有0个

9.4选择题

//二叉树基本性质选择题
1. 某⼆叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该⼆叉树中的叶⼦结点数为（ ）
//不是完全二叉树，399个结点，度为2的结点数为199，所以叶子结点个数 = 度为2的结点个数+1 = 200
A 不存在这样的⼆叉树
B 200//√
C 198
D 1992.在具有 2n 个结点的完全⼆叉树中，叶⼦结点个数为（ ）
//完全二叉树，2n个结点，度为1的结点个数为1，假设度为2的结点个数为x
//则叶子结点个数为x+1，那么2*x+1+1 = 2n，求得x = n-1，那么叶子结点个数为n-1+1 = n
A n//√
B n + 1
C n - 1
D n / 23.⼀棵完全⼆叉树的结点数位为531个，那么这棵树的⾼度为（ ）
//完全二叉树，假设数的高度为h，那么结点数为2的h次方-1，2的10次方为1024
//2的9次方为512，512《531《1024，所以数的高度为10
A 11
B 10//√
C 8
D 124.⼀个具有767个结点的完全⼆叉树，其叶⼦结点个数为（）
//完全二叉树，767个结点，偶数，度为1的结点数为1，设叶子结点数为x
//那么度为2的结点数为x-1，则有2x-1 = 767，所以x = 384
A 383
B 384//√
C 385
D 386//链式二叉树遍历选择题
1.某完全⼆叉树按层次输出（同⼀层从左到右）的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为（ ）
//这一题很简单，自己画图写出前序遍历即可
A ABDHECFG//√
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA2.⼆叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK; 中序遍历：HFIEJKG.则⼆叉树根结点为（ ）
//先序遍历先访问的是根节点，所以直接选A
A E//√
B F
C G
D H3.设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为____。
//后序遍历最后访问的是根节点，所以根节点为a，然后根据中序遍历画图即可
A adbce
B decab
C debac
D abcde//√4.某⼆叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同⼀层从左到右）
的序列为（ ）
//仍然是自己依据性质画图
A FEDCBA//√
B CBAFED
C DEFCBA
D ABCDEF