二叉树和二叉搜索树

Posted on |

二叉树和树

二叉树：概念和性质

定义

二叉树是结点的有穷集合。这个集合或者是空集，或者其中有一个成为根节点的特殊结点，其余结点分属两棵不相交的二叉树，这两棵二叉树分别是原二叉树（或者说是原二叉树的根结点）的左子树和右子树。

  • 二叉树是一种递归结构，是最简单的树形结构，是复杂结构

基本概念

  • 分类：空树、单点树、其他
  • 结点：父结点、子结点、兄弟结点、叶结点
  • 关系：父子关系、祖先关系、子孙关系
  • 度数：一个结点的子结点个数称为该节点的度数，二叉树中叶结点的度数为0，分结点的度数可以是1或2
  • 路径：从一个祖先结点到其任何子孙结点都存在一系列的边，称为一条路径，路径中边的条数称为该路径的长度。每个结点到其自身的路径长度为0
  • 层次结构：根结点的层次为0，对于k层结点，其子结点是k+1层的元素。从根结点到树中任一结点的路径长度就是该结点所在的层数，称为该结点的层数
  • 高度：一棵二叉树的高度就是树中结点的最大层数（最长路径的长度）。只有根结点的树高度是0

二叉树的性质

  • 在非空二叉树第i层至多有$2^i$个结点$(i>=0)$
  • 高度为h的二叉树至多有$2^{h+1}-1$个结点$(h>=0)$
  • 任何非空二叉树T，如果其叶结点的个数为$n_0$，度数为2的结点的个数为$n_2$，那么$n_0=n_2+1$

满二叉树和扩充二叉树

满二叉树
  • 定义：如果二叉树中所有分支结点的度数都是2，则称为满二叉树
  • 性质：满二叉树的叶结点比分支结点多一个
扩充二叉树
  • 定义：对于二叉树T，加入足够多的新叶结点，使T的原有结点都变成度数为2的分支结点，得到二叉树称为T的扩充二叉树。其新增的结点称为外部结点，原树T的结点称为其内部结点。空树的扩充二叉树为空树
  • 性质：是满二叉树，扩充二叉树的外部结点的个数比内部结点个数多1

完全二叉树

  • 定义：对于一棵高度为h的二叉树，如果第0-h-1层的结点都满（就是说$0<=i<=h-1$，第i层有$2^i$个结点）。如果下一层的结点不满，则左右结点在最左边连续排列，空位都在右边。这种二叉树称为完全二叉树。
  • 性质
    • n个结点的完全二叉树高度$h=\lfloor \log_2n \rfloor$，即不大于$\lfloor \log_2n \rfloor$的自最大整数。设完全二叉树有n个结点，高度是h。由于T在n个结点的二叉树里面最低，所以$2^{h}-1<n \leq 2^{h+1}-1$，即$2^h \leq n<2^{h+1}-1$，取对数得$h \leq \log_2n<h+1$
    • 包含n个结点的完全二叉树的结点按层次并按从左到右的顺序从0开始编号，对于任一结点i（$0 \leq i \leq n-1$）有：
      • 序号为0的是根结点
      • 对于i>0，其父结点的编号是$(i-1)/2$
      • 对于$ 2i+1<n$，其左孩子结点序号为$2i+1$，否则没有左孩子结点
      • 对于$2i+2<n$，其右孩子结点序号为$2i+2<n$，否则没有右孩子结点

遍历二叉树

分类

深度优先遍历：先序遍历、中序遍历、后序遍历
宽度优先遍历

  • 如果知道了一棵二叉树的中序序列，又知道另种遍历序列（先序或者后序序列），就可以唯一的确定这个二叉树

二叉树的list实现

二叉树的类实现

二叉树结点类

递归定义的二叉树操作具有统一的模式：

  1. 描述对空树的处理，应该直接给出结果
  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
"""二叉树的链接表示"""
class BinTNode:
    def __init__(self,data,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right

"""统计树中结点个数"""
def count_BinTNodes(t):
    if t is None:
        return 0
    else:
        return 1+count_BinTNodes(t.left)+count_BinTNodes(t.right)

"""统计二叉树中所有数值之和"""
def sum_BinTNodes(t):
    if t is None:
        return 0
    else:
        return t.data+sum_BinTNodes(t.left)+sum_BinTNodes(t.right)

if __name__ == '__main__':
    t = BinTNode(1, BinTNode(2, BinTNode(3), BinTNode(4)), BinTNode(5))
    print('Count the nodes in the binary tree:\t',count_BinTNodes(t))
    print('Get the sum of the nodes in the binary tree:\t',sum_BinTNodes(t))
    # Count the nodes in the binary tree:	 5
    # Get the sum of the nodes in the binary tree:	 15

二叉树遍历

深度优先遍历
非递归先序遍历

在先序遍历中，访问的顺序依次为$根->左子树->右子树$。本方法先访问根结点，采用栈保存遇到的当前结点并暂不访问，并沿着树的左分支下。

循环中需要维持一种不变关系：假设变量t一直取值为当前待遍历子树的根，栈中保存当前遇到但尚未遍历的右子树。即循环条件是当前树非空（这棵树需要遍历）或者栈非空（还存在尚未遍历的部分）。

  • 由于先序遍历，先访问当前结点数据，当前结点的右分支入栈，下一步应该沿着树的左分支下行
  • 遇到空树时回溯，从弹出栈顶元素(最近的一个右子树),像二叉树一样遍历该右子树

每遇到空树,意味着完成遍历一棵子树：

  • 如果是一颗左子树，说明已遍历完该左子树，下一步应该访问与其对应的右子树（即栈顶元素）
  • 如果是一颗右子树，说明已遍历完以它为右子树的更大子树，下一步应该处理更上一层的子树的右子树（即栈顶元素）
非递归中序遍历

在中序遍历中，访问的顺序依次为$左子树->根->右子树$.本方法沿着树的左分支下行，并采用栈保存遇到的当前结点并暂不访问.

循环中维持一种不变关系：假设变量t一直取值为当前待遍历子树的根，暂不访问该根节点，并入栈存储。即循环条件是当前树非空（这棵树需要遍历）或者栈非空（还存在尚未遍历的部分）。
循环体中，应先沿着左子树下行，一路上当前结点入栈，这用到一个循环。内部循环至空树时回溯，从弹出栈顶元素（左子树为空，则弹出的是左子树的根；右子树为空，则弹出的是右子树的根的父结点），访问当前结点，下一步遍历当前节点的右子树。

每次遇到空树，意味着完成遍历一个子树。

  • 如果是一颗左子树，说明已遍历完该左子树，下一步应该访问以它为左子树的根结点（栈顶元素）。
  • 如果是一颗右子树，说明已遍历完以它为右子树的更大子树，下一步应该处理更上一层的子树（即右子树的根的父结点，栈顶元素）
非递归后序遍历

变量t的值是当前结点（可能为空）。在遍历循环中维持一种不变关系：

  • 栈中结点序列的左边是二叉树已遍历的部分，右边是未遍历部分
  • 如果t不为空，则其父结点是栈顶结点
  • 如果t为空时，栈顶就是应该访问的结点
    根据被访问结点是其父结点的左子节点或右子节点，决定下一步：如果是左子结点就转到右子结点；如果是右子结点，就应该处理根节点并强行退栈。
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
"""二叉树的链接表示"""
class BinTNode:
    def __init__(self,data,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right

"""递归遍历"""
def preorder(t,proc):
    if t is None:
        return
    assert(isinstance(t,BinTNode))
    proc(t.data)
    preorder(t.left,proc)
    preorder(t.right,proc)

def inorder(t,proc):
    if t is None:
        return
    assert(isinstance(t,BinTNode))
    inorder(t.left,proc)
    proc(t.data)
    inorder(t.right,proc)

def postorder(t,proc):
    if t is None:
        return
    assert(isinstance(t,BinTNode))
    postorder(t.left,proc)
    postorder(t.right,proc)
    proc(t.data)

"""非递归遍历"""
def preorder_nonrec(t,proc):
    stack=[]
    while t or stack:
        while t:
            proc(t.data)
            stack.append(t.right)
            t=t.left
        t=stack.pop()


def inorder_nonrec(t,proc):
    stack=[]
    while t or stack:
        while t:
            stack.append(t)
            t=t.left
        t=stack.pop()
        proc(t.data)
        t=t.right

def postorder_nonrec(t,proc):
    stack=[]
    while t or stack:
        while t:
            stack.append(t)
            t=t.left if t.left else t.right

        t=stack.pop()
        proc(t.data)

        if stack and stack[-1].left==t:
            t=stack[-1].right
        else:
            t=None

"""非递归遍历2"""

def preorderTraversal(self, root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    result=[]
    if not root:
        return result

    stack=[root]
    while stack:
        node=stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

def postorder_nonrec_2(t):
    stack=[t]
    ans=[]
    while stack:
        t=stack.pop()
        if t is None:
            continue
        ans.append(t.data)

        if t.left:
            stack.append(t.left)
        if t.right:
            stack.append(t.right)
    print(' '.join([str(x) for x in ans[::-1]]))

if __name__ == '__main__':
    t = BinTNode(1, BinTNode(2, BinTNode(3), BinTNode(4)), BinTNode(5))

    print('Recursive preorder:\t')
    preorder(t,lambda x:print(x,end=' '))
    print('\nNone-recursive preorder:\t')
    preorder_nonrec(t,lambda x:print(x,end=' '))
    print('\nNone-recursive preorder 2:\t')
    preorder_nonrec_2(t,lambda x:print(x,end=' '))
    print()

    print('\nRecursive inorder:\t')
    inorder(t,lambda x:print(x,end=' '))
    print('\nNone-recursive inorder:\t')
    inorder_nonrec(t,lambda x:print(x,end=' '))
    print()

    print('\nRecursive postorder:\t')
    postorder(t,lambda x:print(x,end=' '))
    print('\nNone-recursive postorder:\t')
    postorder_nonrec(t,lambda x:print(x,end=' '))
    print('\nNone-recursive postorder 2:\t')
    postorder_nonrec_2(t)

宽度优先遍历

要实现宽度优先遍历，需要用到一个队列。

处理一个结点时，函数先将其左右结点顺序加入到队列中。这样实现的就是对每层结点从左到右的遍历。下面的写法可能会把一些空树也加入队列中，浪费存储空间。可以考虑在操作前检查子结点的存在情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""宽度优先遍历"""
from collections import deque
def levelorder(t,proc):
    queue=deque([t])
    while queue:
        t=queue.popleft()
        if t is None:
            continue
        if t.left:
            queue.append(t.left)
        if t.right:
            queue.append(t.right)
        proc(t.data)
if __name__ == '__main__':
    t = BinTNode(1, BinTNode(2, BinTNode(3), BinTNode(4)), BinTNode(5))

    print('LevelOrder:\t')
    levelorder(t,lambda x:print(x,end=' '))

二叉树类

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
class BinTree:
    def __init__(self):
        self._root=None

    def is_empty(self):
        return self._root is None

    def set_root(self,rootnode):
        self._root=rootnode

    def set_left(self,leftchild):
        self._root.left=leftchild

    def set_right(self,rightchild):
        self._root.right=rightchild

    def root(self):
        return self._root

    def leftchild(self):
        return self._root.left

    def rightchild(self):
        return self._root.right

    def preorder_elements(self):
        t=self._root
        stack=[]
        while t or stack:
            while t:
                stack.append(t.right)
                yield t.data
                t=t.left
            t=stack.pop()

哈夫曼树

树和树林

二叉搜索树(BST)

二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储：设x是二叉搜索树的一个结点。如果y是x左子树的一个结点，那么$y.key \leq x.key$。如果y是x右子树的一个结点，那么$y.key \geq x.key$

查询二叉搜索树

查找

对于到的每个结点x，比较关键字k与x.key。如果两个关键字相等，查找就停止。如果k<x.key，查找在x的左子树继续，否则在x的右子树继续。

后继和前驱

给定一颗二叉搜索树中的一个结点，有时候需要中序遍历的次序查找它的后继。如果所有的关键字都互不相同，则一个结点x的后继是大于x.key的最小关键字的结点。

  • 如果x的右子树非空，那么x的后继恰是x右子树中的最左结点
  • 如果x的右子树为空，并有一个前驱y，那么y是x的最底层祖先，y的左孩子也是x的一个祖先。为了找到y，只需要简单的从x开始沿树而上直到遇到这样一个结点：这个结点是它的双亲的左孩子。

一棵高度为h的二叉搜索树，tree_successor的运行时间是$O(h)$，因为该规程或遵循最简单路径沿树而上或者遵循最简单的路径沿树而下。

在一棵高度为h的二叉搜索树上，动态集合上的操作查询、最小值、最大值、后继、前驱可以在O(h)时间内完成

插入与删除

插入

初始化遍历指针y为None，将其作为x的双亲，方便在x为None时，找到z属于的双亲
见代码

删除

  • 结点z没有左孩子：用其右孩子替换z，右孩子可以是None（等同于没有孩子结点）
  • 结点z没有右孩子：用其左孩子替换z，左孩子可以是None（等同于没有孩子结点）
  • 结点z有两个孩子结点：找z的后继结点y
    • 如果y是z的右孩子且y没有左孩子：用y替换z，使z的左孩子称为y的左孩子，使z的左孩子的双亲成为y
    • 如果y位于z的右子树但并不是z的右孩子：先用y的右孩子替换y，再用y替换z（置y为z的右孩子的双亲，置y为z的双亲的孩子，置y为z的左孩子的双亲）

在一棵高度为h的二叉搜索树上，动态集合上的操作插入与删除可以在O(h)时间内完成

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
"""二叉搜索树：查询、最大关键字元素与最小关键字元素、后继与前驱、插入与删除"""

class Node:
    def __init__(self,key,left=None,right=None,p=None):
        self.key=key
        self.left=left
        self.right=right
        self.p=p

class BinarySearchTree:
    def __init__(self,root):
        self.root=root

    def inorder_tree_walk(self,x):
        if x is not None:
            self.inorder_tree_walk(x.left)
            print(x.key,end=' ')
            self.inorder_tree_walk(x.right)

    def tree_search(self,x,k):
        if x is None or k==x.key:
            return x
        if k<x.key:
            return self.tree_search(x.left,k)
        else:
            return self.tree_search(x.right,k)

    def iter_tree_search(self,x,k):
        while x and k!=x.key:
            if k<x.key:
                x=x.left
            else:
                x=x.right
        return x

    def tree_minimum(self,x):
        while x.left:
            x=x.left
        print('Minimum is:\t',str(x.key))
        return x

    def tree_maximum(self,x):
        while x.right:
            x=x.right
        print('Maximum is:\t',str(x.key))
        return x

    def tree_successor(self,x):
        if x.right:
            return tree_minimum(x.right)
        y=x.p
        if y and x==y.right:
            print("Climbing tree to check " + str(y.key))
            x=y
            y=y.p
        print("successor of x (" + str(x.key) + ") is " + str(y.key))
        return y

    """插入"""
    def tree_insert(self,z):
        y=None
        x=self.root
        while x:                # 从树根开始，指针x记录一条简单的下降路径，直到x为None
            y=x                 # 保持便利指针y始终作为x的双亲
            if z.key<x.key:
                x=x.left
            else:
                x=x.right
        z.p=y                   # x为None所占据的位置就是输入项z要放置的位置，遍历指针y的作用是：找到位置None时需要知道他的双亲
        if y is None:
            self.root=z
        elif z.key<y.key:
            y.left=z
        else:
            y.right=z

    """替换子树，并使其称为原子树双亲的孩子"""
    def transplant(self,u,v):
        if u.p is None:
            self.root=v
        elif u==u.p.left:
            u.p.left=v
        else:
            u.p.right=v
        if v:
            v.p=u.p

    """删除"""
    def tree_delete(self,z):
        if z.left is None:                  # z没有左孩子
            self.transplant(z,z.right)
        elif z.right is None:               # z有一个左孩子，但没有右孩子
            self.transplant(z,z.left)
        else:                               # z有两个孩子结点，需要考虑y是否是z的右孩子
            y=self.tree_minimum(z.right)    # y是z的后继（在z的右子树中）
            if y.p !=z:                     # y不是z的右孩子，用y的右孩子替换y并成为y的双亲的一个孩子
                self.transplant(y,y.right)  # 然后将z的右孩子转换为y的右孩子
                y.right=z.right
                y.right.p=y
            self.transplant(z,y)            # y是z的右孩子，用y替换z，并成为z的双亲的一个孩子，用z的左孩子替换为y的左孩子
            y.left=z.left
            y.left.p=y

if __name__=='__main__':
    root=Node(15,None,None,None)
    T=[6,18,3,7,17,20,2,4,13,9]
    t=BinarySearchTree(root)

    print('Insert the node to the tree:\t',T)
    for i in T:
    	r=Node(i,None,None,None)
    	t.tree_insert(r)
    print('In order walk the tree:',end='\t')
    t.inorder_tree_walk(t.root)
    print()

    print('Delete the node:',end='\t')
    t.tree_delete(t.tree_search(t.root,7))
    t.inorder_tree_walk(t.root)

    # Insert the node to the tree:	 [6, 18, 3, 7, 17, 20, 2, 4, 13, 9]
    # In Order Walk the tree:	2 3 4 6 7 9 13 15 17 18 20
    # Delete the node:	2 3 4 6 9 13 15 17 18 20