树和二叉查找树BST和遍历

一、树 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