树 Tree

基本概念

image.png

“树” 这种数据结构很像我们现实生活中的“树”，这里面每个元素我们叫做“节点”；用来连接相邻节点之间的关系，我们叫做“父子关系”。

在下图中，

  • A 节点就是 B 节点的 父节点
  • B 节点是 A 节点的 子节点
  • B、C、D 节点的父节点是同一个节点，所以它们之间互称为 兄弟节点
  • 没有父节点的节点叫 根节点 ，图中的节点 E
  • 没有子节点的节点叫做 叶子节点 或者 叶节点 ，如图中的 G、H、I、J、K、L

image.png

高度（Height）、深度（Depth）、层（Level）

  • 节点高度 = 节点到叶子节点的最长路径（边数）
  • 节点深度 = 根节点到这个节点所经历的的边的个数
  • 节点层数 = 节点的深度 + 1
  • 数的高度 = 根节点的高度

image.png

树.png

  • 根节点 Root
    • 左子树
    • 右子树

二叉树 Binary Tree

二叉树.png

  • 儿子结点只有两个（左儿子 和 右耳子）

图 Graph

图.png

  • 图和树最关键的区别：就是看子结点有没有环

  • 简化理解

    • 链表（Linked List）是特殊化的树（Tree）
    • 树（Tree）是特殊化的图（Graph）

树结点的定义：示例代码

  • Python

    1. class TreeNode:
    2.   def __init__(self, val):
    3.       self.val = val
    4.       self.left, self.right = None, None

  • Java

    public class TreeNode() {
  public int val;
  public TreeNode,left,right;
  public TreeNode(int val) {
      this.val = val;
      this.left = null;
      this.right = null;
  }
}

  • C++

    struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x): val(x), left(NULL), right(NULL){}
}

二叉树遍历 Pre-order / In-order / Post-order

  1. 前序（Pre-order）：根 - 左 - 右
  2. 中序（In-order）：左 - 根 - 右
  3. 后序（Post-order）：左 - 右 - 根

  • 遍历的示例代码 ```python

    前序

    def preorder(self, root):

    if root:

      self.traverse_path.append(root.val)
  self.preorder(root.left)
  self.preorder(root.right)

中序

def inorder(self, root):

if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)

后序

def postorder(self, root):

if root:
    self.postorder(root.left)
    self.postorder(root.right)
    self.traverse_path.append(root.val)

```

二叉搜索树 Binary Search Tree

二叉搜索树.png

  • 普通的树要想查找，必须遍历，时间复杂度就是 O(n)
  • 二叉搜索树，也称二叉查找树、二叉排序树、有序二叉树（Ordered Binary Tree）、排序二叉树（Sorted Binary Tree），是一颗空树或具有下列性质的二叉树：
    • 左子树上所有节点的值均小于它的根节点的值
    • 右子树上所有节点的值均大于它的根节点的值
    • 以此类推：左右子树也分别为二叉搜索树（重复性！！！）

中序遍历：升序排列

二叉搜索树的最大的特点是：支持动态数据集合的快速插入、删除、查找操作。

二叉搜索树常见操作

  1. 查询 O(logn)
  2. 插入新结点（创建）O(logn)
  3. 删除

Demo: https://visualgo.net/zh/bst

实战题目