一、树 Tree 基础笔记
1. 前提条件

树是一种非线性数据结构。

线性结构是：数组、链表、栈、队列

它们基本是：一个接一个

树是：一对多的层次结构

例如：

        A
      / | \
     B  C  D
    / \
   E   F

2. 核心概念
结点 Node

树中的每一个元素都叫结点:A、B、C、D、E、F 都是结点

根结点 Root：最上面的结点。
A 是根结点

父结点 Parent
如果 A 下面连着 B，那么：
A 是 B 的父结点

子结点 Child
如果 A 下面连着 B，那么：
B 是 A 的子结点

兄弟结点 Sibling
有同一个父结点的结点叫兄弟。
B、C、D 是兄弟结点

叶子结点 Leaf
没有孩子的结点。
C、D、E、F 是叶子结点

结点的度
一个结点的孩子个数。

例如：A 有 3 个孩子

所以：A 的度 = 3

树的度:整棵树中，所有结点度的最大值。

例如：A 的度最大，是 3

所以：树的度 = 3

层次

一般教材常用：根结点是第 1 层

例如：

第1层：A
第2层：B C D
第3层：E F

高度 / 深度
常见记法：
树的高度 = 最大层数

例如上面的树高度是：3

3. 树的重要性质
性质 1：n 个结点的树有 n-1 条边

例如：

6 个结点

那么边数：5 条

因为除了根结点外，每个结点都有且只有一条边连向父结点。

性质 2：二叉树每个结点最多两个孩子

二叉树是树的一种特殊情况：每个结点最多有两个孩子

分别叫：

左孩子
右孩子

比如：

        A
       / \
      B   C
     / \
    D   E
4. 二叉树结构体模板
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

↓

Python

class TreeNode:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None

含义：

val：当前结点的值
left：左孩子
right：右孩子

5. 二叉树递归的基本模板
很多树题都是递归。

模板：

void dfs(struct TreeNode* root)
{
    if(root == NULL)
    {
        return;
    }

    // 处理当前结点,如果不是NULL就往左右各自遍历

    dfs(root->left);

    dfs(root->right);
}

核心：root == NULL 是递归边界

6. 树题最重要的思维

链表题经常是：
当前节点 + next

树题经常是：
当前节点 + 左子树 + 右子树

所以树的递归要这样想：

如果左子树能解决
如果右子树能解决
那当前结点怎么处理？

7. 易错点
易错点 1：树不是线性结构

链表只有一个 next。

树有：

left
right

甚至普通树有多个孩子。

易错点 2：递归边界一定要写
if(root == NULL)
{
    return;
}

否则访问：

root->left

会出错。

二、二叉查找树 BST 笔记
1. 前提条件

二叉查找树，英文Binary Search Tree

简称：BST

它首先是一棵二叉树。

然后额外满足：

左子树所有结点 < 根结点
右子树所有结点 > 根结点

这就是 BST 的核心性质；BST 的查找、插入、删除复杂度和树高有关，如果树比较平衡，一般能接近 O(log n)，如果退化成链表则可能到 O(n)。

2. 核心概念

例如：

        8
       / \
      4   10
     / \    \
    2   6    12

对于根结点 8：

左边：4、2、6 都小于 8
右边：10、12 都大于 8

对于结点 4：

左边 2 小于 4
右边 6 大于 4

每一个结点都满足这个规则。

3. BST 最重要性质

BST 的中序遍历结果是有序的。
上面这棵树中序遍历：

2 4 6 8 10 12

是升序。

这个性质非常重要。

以后判断一棵树是不是 BST，经常用中序遍历。

三、BST 查找

1. 查找思路
查找一个值 target。
从根结点开始：

如果 target == root->val
    找到

如果 target < root->val
    去左子树找

如果 target > root->val
    去右子树找

2. 查找例子
树：

        8
       / \
      4   10
     / \    \
    2   6    12

查找：6

过程：

6 < 8，去左边
6 > 4，去右边
6 == 6，找到

3. BST 查找 C 代码
递归版：

struct TreeNode* searchBST(struct TreeNode* root, int target)
{
    if(root == NULL)
    {
        return NULL;
    }

    if(root->val == target)
    {
        return root;
    }

    if(target < root->val)
    {
        return searchBST(root->left, target);
    }
    else
    {
        return searchBST(root->right, target);
    }
}

迭代版：

struct TreeNode* searchBST(struct TreeNode* root, int target)
{
    while(root != NULL)
    {
        if(root->val == target)
        {
            return root;
        }
        else if(target < root->val)
        {
            root = root->left;
        }
        else
        {
            root = root->right;
        }
    }

    return NULL;
}

四、BST 插入

1. 插入思路

插入一个值 x。

从根开始比较：

x < 当前结点，往左走
x > 当前结点，往右走

直到遇到空位置：NULL

就在这个位置创建新结点。

2. 插入例子

原树：

        8
       / \
      4   10
     / \
    2   6

插入：5

过程：

5 < 8，去左
5 > 4，去右
5 < 6，去左
6 的左边为空，插入 5

结果：

        8
       / \
      4   10
     / \
    2   6
       /
      5
3. 创建结点代码
#include <stdlib.h>

struct TreeNode* createNode(int x)
{
    struct TreeNode* node =
        malloc(sizeof(struct TreeNode));

    node->val = x;
    node->left = NULL;
    node->right = NULL;

    return node;
}
4. 插入 C 代码

递归版：

struct TreeNode* insertBST(struct TreeNode* root, int x)
{
    if(root == NULL)
    {
        return createNode(x);
    }

    if(x < root->val)
    {
        root->left = insertBST(root->left, x);
    }
    else if(x > root->val)
    {
        root->right = insertBST(root->right, x);
    }

    return root;
}

说明：如果题目不允许重复值，x == root->val 时不插入。

五、BST 删除

删除是 BST 最容易混的地方。

删除一个结点分三种情况。

情况 1：删除叶子结点

例如删除 2：

        8
       / \
      4   10
     / \
    2   6

2 没有孩子。

直接删。

结果：

        8
       / \
      4   10
       \
        6
情况 2：删除只有一个孩子的结点

例如：

        8
       / \
      4   10
             \
             12

删除 10。

10 只有右孩子 12。

让 12 顶上来：

        8
       / \
      4   12
情况 3：删除有两个孩子的结点

例如删除 8：

        8
       / \
      4   10
     / \    \
    2   6    12

8 有左孩子和右孩子。

不能直接删。

常用做法：找右子树最小值

右子树：

10
  \
  12

最小值是：

10

用 10 替换 8。

然后再去右子树删除原来的 10。

结果：

        10
       /  \
      4    12
     / \
    2   6

删除 C 代码
struct TreeNode* findMin(struct TreeNode* root)
{
    while(root->left != NULL)
    {
        root = root->left;
    }

    return root;
}

struct TreeNode* deleteBST(struct TreeNode* root, int x)
{
    if(root == NULL)
    {
        return NULL;
    }

    if(x < root->val)
    {
        root->left = deleteBST(root->left, x);
    }
    else if(x > root->val)
    {
        root->right = deleteBST(root->right, x);
    }
    else
    {
        if(root->left == NULL && root->right == NULL)
        {
            free(root);
            return NULL;
        }
        else if(root->left == NULL)
        {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        else if(root->right == NULL)
        {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        else
        {
            struct TreeNode* successor = findMin(root->right);
            root->val = successor->val;
            root->right = deleteBST(root->right, successor->val);
        }
    }

    return root;
}

六、BST 易错点
1. BST 不是普通二叉树
普通二叉树没有大小关系。

BST 必须满足：
左小右大

2. 中序遍历是升序
这是 BST 最重要性质。
BST 中序遍历 = 升序序列

3. 查找不是全树遍历
BST 查找不用左右都搜。
只需要根据大小走一边：

小了走左
大了走右

4. 删除两个孩子的结点最麻烦
常用替代结点：
右子树最小值

或者：
左子树最大值

二选一即可。

5. BST 可能退化成链表

如果插入顺序是：

1 2 3 4 5

BST 会变成：

1
 \
  2
   \
    3
     \
      4
       \
        5

查找就退化成：

O(n)

这也是为什么后面要学 AVL 树。

BST 笔记总结
二叉查找树 BST

定义：

左子树所有结点 < 根结点
右子树所有结点 > 根结点

--------------------------------

重要性质：中序遍历结果是升序

--------------------------------

查找：

target < root->val
    去左子树

target > root->val
    去右子树

target == root->val
    找到

--------------------------------

插入：按查找路径往下走

遇到 NULL 就插入新结点

--------------------------------

删除：

1. 叶子结点
   直接删除

2. 只有一个孩子
   孩子顶上来

3. 有两个孩子
   用右子树最小值
   或左子树最大值替换

--------------------------------

复杂度：和树高有关

平衡时接近 O(log n)

退化成链表时 O(n)

--------------------------------

为什么需要 AVL：

普通 BST 插入顺序不好时，
可能退化成链表。

然后稍微复习一下py的代码
一、普通二叉树
节点定义

Python：
//使用类之后魔术封装给左右都是None，设立节点
class TreeNode:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None

对应 C：

struct TreeNode{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

手动建树

例如：

        1
       / \
      2   3
     / \
    4   5

Python：

root = TreeNode(1)

root.left = TreeNode(2)
root.right = TreeNode(3)

root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

画出来：

   root
    ↓
    1
   / \
  2   3
 / \
4   5

二、遍历
前序遍历
根左右

def preorder(root):

    if root is None:
        return

    print(root.val)

    preorder(root.left)

    preorder(root.right)

中序遍历
左根右

def inorder(root):

    if root is None:
        return

    inorder(root.left)

    print(root.val)

    inorder(root.right)

后序遍历
左右根

def postorder(root):

    if root is None:
        return

    postorder(root.left)

    postorder(root.right)

    print(root.val)

树递归就一个模板：

if root is None:
    return

左子树

右子树

只是：print放哪里不同。

三、BST（二叉查找树）

先定义节点：

class TreeNode:

    def __init__(self,val):

        self.val = val
        self.left = None
        self.right = None
查找

例如找：6

树：

        8
       / \
      4   10
     / \
    2   6

代码：

def search(root,target):

    if root is None:
        return None

    if root.val == target:
        return root

    if target < root.val:
        return search(root.left,target)

    return search(root.right,target)

思想和 C 一模一样：

比当前小去左边

比当前大去右边


插入：5

代码：

def insert(root,x):

    if root is None:
        return TreeNode(x)

    if x < root.val:
        root.left = insert(root.left,x)

    elif x > root.val:
        root.right = insert(root.right,x)

    return root

执行：

root = insert(root,5)

结果：

        8
       / \
      4   10
     / \
    2   6
       /
      5

四、封装成 BST 类

面向对象写法。

class BST:

    def __init__(self):
        self.root = None

插入：

class BST:

    def __init__(self):
        self.root = None

    def _insert(self,node,x):

        if node is None:
            return TreeNode(x)

        if x < node.val:
            node.left = self._insert(node.left,x)

        elif x > node.val:
            node.right = self._insert(node.right,x)

        return node

    def insert(self,x):
        self.root = self._insert(self.root,x)

使用：

tree = BST()

tree.insert(8)
tree.insert(4)
tree.insert(10)
tree.insert(2)
tree.insert(6)

最后：

        8
       / \
      4   10
     / \
    2   6