数据结构第十讲：二叉树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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.相同的树

链接: OJ题链接

typedef struct TreeNode TreeNode;

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

    //最后要得到的是两棵树是否相同，就要看两棵树的左节点树和右节点树是否相同
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3.对称二叉树

链接: OJ题链接

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

typedef struct TreeNode TreeNode;

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //要检查两棵树是否对称，就要同时遍历两棵树的结点，还是要用到递归
    //递归结束条件
    //当两个结点全为空时，返回true
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //当两个结点不全为空
    //当两个结点中有一个为空时，说明两棵树不同
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //当两棵树的结点值不同时，返回false
    if(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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

4. 另一棵树的子树

链接: OJ题链接

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

typedef struct TreeNode TreeNode;

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //要检查两棵树是否相同，就要同时遍历两棵树的结点，还是要用到递归
    //递归结束条件
    //当两个结点全为空时，返回true
    if(p == NULL && q == NULL)
    {
        return true;
    }
    //当两个结点不全为空
    //当两个结点中有一个为空时，说明两棵树不同
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //当两棵树的结点值不同时，返回false
    if(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;
    }

    //对于返回值，只要左右树中有一棵树中存在目标子树，就需要返回true
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

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 199

2.在具有 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 / 2

3.⼀棵完全⼆叉树的结点数位为531个，那么这棵树的⾼度为（ ）
//完全二叉树，假设数的高度为h，那么结点数为2的h次方-1，2的10次方为1024
//2的9次方为512，512《531《1024，所以数的高度为10
A 11
B 10//√
C 8
D 12

4.⼀个具有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 HDEBFGCA

2.⼆叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK; 中序遍历：HFIEJKG.则⼆叉树根结点为（ ）
//先序遍历先访问的是根节点，所以直接选A
A E//√
B F
C G
D H

3.设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为____。
//后序遍历最后访问的是根节点，所以根节点为a，然后根据中序遍历画图即可
A adbce
B decab
C debac
D abcde//√

4.某⼆叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同⼀层从左到右）
的序列为（ ）
//仍然是自己依据性质画图
A FEDCBA//√
B CBAFED
C DEFCBA
D ABCDEF
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61