第5讲 二叉排序树、表达式树

1.二叉排序树 BST

中序遍历有序的二叉树 为 二叉排序树

AcWing 3786. 二叉排序树

2.平衡树——AVL

(1) 定义：满足如下条件的树：
a. 是二叉查找树
b. 每个节点的左子树和右子树的高度差最多为1
(2) 平衡因子：一个结点的左子树的高度减去右子树的高度，可取-1、0、1三种值
(3) 平衡操作

左旋 右旋 不改变中序遍历

中序遍历不变

image-20210727163412049

3.表达式树

考的少

image-20210727164520285

4.考题：2011-7、2012-4、2013-3(PDF中的分析有误，以上课讲解为准)、2013-6、2015-4、2018-6、2019-4、2019-6、2020-5、2017-41

2011-7

image-20210727164907499

A

判断中序遍历是否有序

image-20210727165303010

image-20210727165130394

2012-4

image-20210727165415989

B

image-20210727165720445

2013-3

image-20210727163607794

D 左旋 右旋 不改变中序遍历

image-20210727164002437

2013-6

image-20210727165759234

C

删除一个节点后又添加这个节点，树会不会不同

为叶节点： 相同

不为叶节点：

image-20210727170031782

2015-4

image-20210727170408836

D

AVL 树 中序遍历为降序

左子树一定大于此元素

最大元素一定无左子树

2018-6

image-20210727170610360

image-20210727170617758

C

2019-4

image-20210727170743812

A

image-20210727170958283

image-20210727171144035

2019-6

image-20210727164634164

A

表达式树的化简

image-20210727164716317

到

image-20210727164737507

2020-5

image-20210727171222387

2017-41

image-20210727171446721

AcWing 3765. 表达式树

C++： $O(n^2)$

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val；
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    
    string dfs(TreeNode* root){
        
        
        if(!root) return "" ;// 节点为空
        if(!root->left&&!root->right) return root->val;  // 叶节点 
        else {
            
            return "(" + dfs(root->left) + root->val + dfs(root->right) + ")";
            
        }
        
        
    }
    
    string expressionTree(TreeNode* root) {
        
        // 最外层不要括号
        
        return dfs(root->left ) + root->val + dfs(root->right);
        
    }
};

image-20210727172012391