---

5.二叉树算法题

5.1 单值二叉树

点击链接做题

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) {if(root == NULL){return true;}//root不为空，把root和root->left,root->right比较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);
}

---

5.2 相同的树

点击链接做题

1. 两棵树都为空树------相同的树

2. 其一为空树------不是相同的树

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//给了两个树的根节点//判断是否为空树if(p == NULL && q == NULL){return true;}//其一为空if(p == NULL || q == NULL){return false;}//说明都不为空if(p->val != q->val){return false;}//说明结构相同值相同return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

---

拓展学习

对称二叉树：

点击链接做题

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
typedef struct TreeNode TreeNode;bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//给了两个树的根节点//判断是否为空树if(p == NULL && q == NULL){return true;}//其一为空if(p == NULL || q == NULL){return false;}//说明都不为空if(p->val != q->val){return false;}//说明结构相同值相同return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
}bool isSymmetric(struct TreeNode* root) {return isSameTree(root->left,root->right);
}

---

5.3 另一棵树的子树

点击链接做题

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
typedef struct TreeNode TreeNode;bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//给了两个树的根节点//判断是否为空树if(p == NULL && q == NULL){return true;}//其一为空if(p == NULL || q == NULL){return false;}//说明都不为空if(p->val != q->val){return false;}//说明结构相同值相同return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}//判断subRoot是不是root的子树
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root == NULL){return false;}if(isSameTree(root,subRoot)){return true;}//判断root的左右子树是否和subRoot一样return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

---

5.4 二叉树遍历

前序遍历：

点击链接做题

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
typedef struct TreeNode TreeNode;// ⼆叉树结点个数
int BinaryTreeSize(TreeNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//表示是当前函数的子函数
void _preorderTraversal(TreeNode* root,int* arr,int* pi){if (root == NULL){return;}//根左右arr[(*pi)++] = root->val;_preorderTraversal(root->left,arr,pi);_preorderTraversal(root->right,arr,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {//int* returnSize是一个整型数组//1.先求出二叉树结点的个数*returnSize = BinaryTreeSize(root);//2.动态申请内容---arr的大小int* returnArr = (int*)malloc(sizeof(int)*(*returnSize));//开始前序遍历int i = 0;_preorderTraversal(root,returnArr,&i);return returnArr;
}

---

中序遍历：

点击链接做题

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct TreeNode TreeNode;// ⼆叉树结点个数
int BinaryTreeSize(TreeNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//表示是当前函数的子函数
void _preorderTraversal(TreeNode* root,int* arr,int* pi){if (root == NULL){return;}//左根右_preorderTraversal(root->left,arr,pi);arr[(*pi)++] = root->val;_preorderTraversal(root->right,arr,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {//int* returnSize是一个整型数组//1.先求出二叉树结点的个数*returnSize = BinaryTreeSize(root);//2.动态申请内容---arr的大小int* returnArr = (int*)malloc(sizeof(int)*(*returnSize));//开始中序遍历int i = 0;_preorderTraversal(root,returnArr,&i);return returnArr;
}

---

后序遍历：

点击链接做题

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
typedef struct TreeNode TreeNode;// ⼆叉树结点个数
int BinaryTreeSize(TreeNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//表示是当前函数的子函数
void _preorderTraversal(TreeNode* root,int* arr,int* pi){if (root == NULL){return;}//左右根_preorderTraversal(root->left,arr,pi);_preorderTraversal(root->right,arr,pi);arr[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {//int* returnSize是一个整型数组//1.先求出二叉树结点的个数*returnSize = BinaryTreeSize(root);//2.动态申请内容---arr的大小int* returnArr = (int*)malloc(sizeof(int)*(*returnSize));//开始后序遍历int i = 0;_preorderTraversal(root,returnArr,&i);return returnArr;
}

---

5.5 二叉树的构建及遍历

点击链接做题

代码：

#include <stdio.h>
typedef struct BinaryTreeNode {char data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;//创建节点
BTNode* buyNode(char x) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}//前序遍历
BTNode* creatrTree(char* arr, int* pi) {if (arr[*pi] == '#') {//如果取到的是空字符，那么就不要创建它的根节点(*pi)++;//继续往后走return NULL;}//先创建arr[*pi]这个根节点，然后后置++，这样就到了后面的结点BTNode* root = buyNode(arr[(*pi)++]);root->left = creatrTree(arr, pi);//把根节点的左孩子当作新的根节点root->right = creatrTree(arr, pi);return root;
}//中序遍历--左根右
void InOrder(BTNode* root) {if (root == NULL) {return;}InOrder(root->left);//左printf("%c ", root->data);//中InOrder(root->right);//右
}int main() {//读取用户输入的字符串保存在字符数组中char arr[100];scanf("%s",arr);//根据字符串（前序遍历）创建二叉树int i = 0;BTNode* root = creatrTree(arr, &i);//root指向二叉树的根节点//输出二叉树的中序遍历InOrder(root);return 0;
}

---

6.二叉树选择题

二叉树性质

1. 对任何一棵二叉树, 如果度为 0 其叶结点个数为n₀ , 度为 2 的分支结点个数为n₂ ,则有n₀=n₂+1

证明上述性质：

假设一个二叉树有 a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个二叉树的边数是2a+b

另一方面，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1

结合上面两个公式：

2a+b = a+b+c-1 ，即： a = c-1

根据二叉树的性质，完成以下选择题：（答案在后面）

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
   A 不存在这样的二叉树
   B 200
   C 198
   D 199

n₀=n₂+1

2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
   A n
   B n+1
   C n-1
   D n/2

n₀+n₁+n₂=2N：所有节点加起来2n

因为n₀=n₂+1，所以化简为下面的

2n₀+n₁-1=2N

完全二叉树中有1或0个，度为1的结点。

因为2N是偶数，2n₀是偶数，所以n₁-1也为偶数，所以n₁为奇数，n₁=1。

2n₀=2N，n₀为n个

3. 一棵完全二叉树的结点数位为531个，那么这棵树的高度为（ ）
   A 11
   B 10
   C 8
   D 12

2⁰+2¹+…+2⁸+20=531

4. 一个具有767个结点的完全二叉树，其叶子结点个数为（）
   A 383
   B 384
   C 385
   D 386

2n₀+n₁-1=767

因为767是奇数，2n₀是偶数，所以n₁=0，n₀=384

答案：

1.B

2.A

3.B

4.B

---

链式二叉树遍历选择题：（答案在后面）

1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
   A ABDHECFG
   B ABCDEFGH
   C HDBEAFCG
   D HDEBFGCA

2. 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
   A E
   B F
   C G
   D H

3. 设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为（）
   A adbce
   B decab
   C debac
   D abcde

4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为（）
   A FEDCBA
   B CBAFED
   C DEFCBA
   D ABCDEF

1.A

2.A

3.D

4.A