什么是树

  • 树(Tree)是一种非线性结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。树是递归结构,在树的定义中又用到了树的概念。

什么是二叉树

  • 二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或者“右子树”。二叉树的分支具有左右次序,不能随意颠倒。二叉树可以为空。

完全二叉树

  • 若设二叉树的深度为ℎ,除第ℎ层外,其它各层(1~ℎ−1)的结点数都达到最大个数,第ℎ层所有的结点都连续集中在最左边,这就是完全二叉树

什么是二叉搜索树

  • 左子树的值都比根节点小,右子树的值都比根节点大。

树的定义(Python)

1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.value = x
self.left = None
self.right = None

树的遍历

深度优先,通常有前序(pre-order),中序(in-order),后序(post-order)3种遍历方法,每一种又分递归和迭代两种实现

  • 3种遍历经过的路径都是一样的,而且每个节点都会被访问3次,当我们在第一次访问该节点就打印出来的话,那么这就是前序;当我们第二次访问该节点才打印出来的话,那么这就是中序;当我们第三次访问该节点才打印出来的话,那么这就是后序。
  • 伪代码,递归实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # pseudocode,递归
    ## 前序
    func preorder(root):
    if not root: return
    **print(root.val)**
    preorder(root.left)
    preorder(root.right)


    ## 中序, 对于二叉搜索树,中序后的是一个排序数组
    func inorder(root):
    if not root: return
    inorder(root.left)
    **print(root.val)**
    inorder(root.right)

    ## 后序
    func postorder(root):
    if not root: return
    postorder(root.left)
    postorder(root.right)
    **print(root.val)**
  • Python 实现
    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
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    ## 前序遍历
    ### 1. 递归实现
    class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    ans = []
    if not root: return ans
    self.preTraversal(root, ans)
    return ans

    def preTraversal(self, t, ans):
    ans.append(t.val)
    if t.left:
    self.preTraversal(t.left, ans)
    if t.right:
    self.preTraversal(t.right, ans)

    ### 2. 迭代实现,栈
    class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
    ans = []
    stack = []
    if not root:
    return ans
    p = root
    while(p or len(stack)):
    if p:
    ans.append(p.val)
    stack.append(p)
    p = p.left
    else:
    p = stack[-1]
    stack.pop(-1)
    p = p.right
    return ans

    ## ---------------split line-------------------

    ## 中序序遍历
    ### 1. 递归实现
    class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
    ans = []
    if not root: return ans
    self.inTraversal(root, ans)
    return ans

    def inTraversal(self, t, ans):
    ans.append(t.val)
    if t.left:
    self.inTraversal(t.left, ans)
    if t.right:
    self.inTraversal(t.right, ans)

    ### 2. 迭代实现
    class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
    ans = []
    stack = []
    if not root:
    return ans
    p = root
    while(p or len(stack)):
    if p:
    stack.append(p)
    p = p.left
    else:
    p = stack[-1]
    ans.append(p.val)
    stack.pop(-1)
    p = p.right
    return ans

    ## ---------------split line-------------------

    ## 后序序遍历
    ### 1. 递归实现
    class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    ans = []
    if not root: return ans
    self.postTraversal(root, ans)
    return ans

    def postTraversal(self, t, ans):
    ans.append(t.val)
    if t.left:
    self.postTraversal(t.left, ans)
    if t.right:
    self.postTraversal(t.right, ans)

    ### 2. 迭代实现,因为前序是root->left->right, 而后序是left->right->root,刚好反过来
    class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    ans = []
    stack = []
    if not root:
    return ans
    p = root
    while(p or len(stack)):
    if p:
    ans.append(p.val)
    stack.append(p)
    p = p.right
    else:
    p = stack[-1]
    stack.pop(-1)
    p = p.left
    return [val for val in reversed(ans)]

    广度优先

  • 层次遍历(level-order)
  • 利用队列(queue)来实现
      1. 根节点先入队列
      1. 迭代当前队列上的所有元素
      1. 若该元素所指节点的左右孩子节点非空,则将其左右孩子的指针入队列,把当前元素出队列,并保存其数值到结果数组中。
      1. 循环重复2-4,直到队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
queue = [root]
res = []
if not root:
return []
while queue:
templist = []
templen = len(queue)
for i in range(templen):
temp = queue.pop(0)
templist.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
res.append(templist)
return res

链表(Linked list),树(Tree),图(Graph)的关系

  • 链表是特殊的是特殊的

reference-参考