python数据结构：数组、链表、栈、队列、树_python队列和序列

1.数组

1.1 数组的数据结构

1.1.1 数组的定义

数组(array)表示的是可以在 给定的碎银位置访问或替代的项的一个序列。从表述上和列表有点像，实际上列表的底层数据结构就是数组。

这里讨论的数组，一般也适用于列表，但是数组要更直观。数组的特征和行为主要有：在给定的位置访问或替换数组的一项；查看数组的长度；获取字符串表示；不能添加删除某个位置的项；不能改变数组的大小。通常数组的长度在创建的时候就固定了。

Python中自带的Array模块包含了array类，但是它仅限于存储数字。本章我们自己定义一个新的Array类，遵从前面讲的限制，但是可以保存任何类型的项。这里我们使用python列表来保存项。我们定义的新类Array允许对其使用下标运算符[]、len函数、str函数和for循环，这些操作所需要的方法见下表，其中变量a表示一个Array对象。

当python遇到了表中左边的操作的时候，会自动调用右边对应的方法。

Array类的代码如下：

class Array:

    def __init__(self, capacity, fill_value=None):
        """capacity是数组的长度
        fillValue是初始化数组时每个位置的项的值"""
        self._items = list()
        for count in range(capacity):
            self._items.append(fill_value)

    def __len__(self):
        return len(self._items)

    def __str__(self):
        return str(self._items)

    def __iter__(self):
        # 使用iter函数返回一个迭代器
        return iter(self._items)

    def __getitem__(self, index):
        return self._items[index]

    def __setitem__(self, index, new_item):
        self._items[index] = new_item


if __name__ == "__main__":
    a = Array(5)
    print(len(a))
    print(a)
    for i in range(len(a)):
        a[i] = i + 1
    print(a[0])
    for item in a:
        print(item)
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

可以看到，数组是列表的一个非常受限制的版本。

1.1.2 随机访问和连续内存

数组的索引是随机的访问操作。在随机访问中，计算机通过执行一定数目的步骤，获取看第i项的位置。因此，不管数组有多大，它访问第1项所需的时间和第i项所需的时间是相同的。

这主要是由于计算机为数组分配了一段连续的内存单元。由于项的地址在编号上是连续的，数组的某一项地址可以通过数组的基本地址和项的便宜地址相加得出。这样数组的索引操作就只要以下两个步骤：

1. 获取数组内存块的基本地址
2. 给这个地址加上索引，返回最终的结果

1.1.3 静态内存和动态内存

在一些底层的语言中，数组是静态的数据结构，即数组的长度在编译时确定的，因为程序员需要用一个常量指定大小。但是一些需求中，数组的长度不能固定，可能会导致程序浪费了内存或者超出了数组长度。

项Java和C++这样的现在语言，允许创建动态数组，动态数组也是占据了连续的内存块并支持随机访问，但在运行时并不需要知道数组的长度。Python也是类似。

有一种方法可以在运行时根据应用程序的数据需求来调整数组的长度。一般有以下3种形式：

• 在程序开始的时候创建一个具有默认大小的数组。
• 在这个数组不能保存更多数据的时候，创建一个新的、更大的数组，并且从旧数组转移数据项。
• 当数组似乎存在浪费内存的时候（一些数据被删除了），以一种类似方式减小数组长度。

对于Python列表来说，这些都是自动进行的。

1.1.4 物理大小和逻辑大小

数组的物理大小是它的数组单元的总数，或者说是在创建数组的时候，用来指定其容量的数字。

数组的逻辑大小，是它当前已供应用程序使用的项的数目。

当数组总是满的时候，不用担心他俩的区别，但是这种情况很少。

通常，逻辑大小的物理大小会告诉我们数组状态的几件重要的事：

• 如果逻辑大小为0，数组为空，则说明该数组不包含数据项；
• 如果数组包含的数据项，数组最后一项的索引为逻辑大小减1；
• 如果逻辑大小等于物理大小，数组已经被数据填满。

1.2 数组的操作

下面将学习数组的一些操作：数组改变大小、插入删除一项。这些操作数组并没有提供，需要使用者自己编写。后面的示例，将有如下假设数据：

DEFAULT_CAPACITY = 5
logical_size = 0
a = Array(DEFAULT_CAPACITY)
1
2
3

表示，数组的初始大小为0，物理大小（容量）默认为5。

1.2.1 增加数组大小

当数组要插入新的项，并且物理大小等于逻辑大小，那么就该增加数组的大小了。调整大小的过程包含如下3个步骤：

1. 创建一个新的数组；
2. 将数据从旧的数组复制到新的数组中；
3. 将旧的数组变量重新设置为新的数组对象。

下面是操作代码：

if logical_size == len(a):
  	temp = Array(len(a) + 1)  # 新数组，长度比原来大1
    for i in range(logical_size):   # 把原数组数据拷贝到新数组
      	tem[i] = a[i]
    a = temp  # 旧的数组变量重新设置为新的数组对象
1
2
3
4
5

注意，旧数组的内存留给了垃圾回收程序进行回收。

考虑下上述操作的性能：当调整数组大小的时候，复制操作的次数是线性的，也就是说，给一个数组添加n项的整体时间性能是 1+2+3 + ··· + n，也就是n(n+1)/2，即复杂度是O(n^2)。

如果每次增加数组的时候，把数组的大小加倍，可以改善上述的时间复杂度，如下所示：

tem = Array(len(a) * 2)
1

这样是牺牲了一部分内存才获得的。而且这一操作的空复杂度还是线性的，因为不管使用什么策略，都需要一个临时的数组。

1.2.2 减小数组大小

当数组的逻辑大小缩小的时候，就会有单元浪费。当要删除一项或未使用的单元达到或超过某一阈值，例如物理大小的四分之三时，就该减少数组的物理大小了。

如下示例，当数组的逻辑大小小于或等于物理大小的四分之一，并且物理大小至少是创建数组的默认容量的两倍的时候，就减少数组大小到原来的一半，只要改变后的物理大小不小于默认的容量。代码如下：

if logical_size <= len(a) // 4 and len(a) >= DEFAULT_CAPACITY * 2:
  	temp = Array(len(a) // 2)
    for in range(logical_size):
      	temp[i] = a[i]
    a = temp
1
2
3
4
5

1.2.3 插入一项

向数组插入一项和替换一项是不一样的。替换的时候，给的索引位置已经存在一项，并且对该位置进行一次赋值就够了，而且，数组的逻辑大小并不会改变。

插入的情况下，需要做以下4件事：

1. 在尝试第一次插入或增加数组的物理大小之前，要先检查可用的空间；
2. 从数组的逻辑末尾开始，直到目标索引位置，每一项都向后移动一个单元。这个过程会在目标索引位置为新的项腾出一个空位置；
3. 将新的项赋值给目标索引位置；
4. 将逻辑大小加1.

代码如下：

# 把目标索引的项向后移动，注意是从开始往前遍历
for i in range(logical_size, target_index, -1):
  	a[i] = a[i - 1]
    
# 将新的项赋值给目标索引位置
a[target_index] = new_item
# 逻辑大小加1
logical_size += 1
1
2
3
4
5
6
7
8

1.2.4 删除一项

删除一项是插入一项的反过程，步骤如下：

1. 从目标索引开始（不包含目标索引），到数组的逻辑末尾，每一项都向前移动一位；
2. 逻辑大小减1
3. 检查浪费空间，如果有必要，将物理数组大小减1。

# 把目标索引的项向前移动，注意是从前往后遍历
for i in range(target_index, logical_size-1):
  	a[i] = a[i + 1]
    
# 逻辑大小减1
logical_size -= 1
1
2
3
4
5
6

同样的，移动一项的时间复杂度平均是线性的，删除操作的时间复杂度也是线性的。

1.2.5 复杂度权衡

数组结构表明了运行时间性能和内存性能之间的一个权衡。下表记录了每次数组操作的时间复杂度：

其实数组提供了对已经存在项的快速访问，并且提供了在逻辑末尾快速插入和删除。在任意位置插入和删除可能会慢上一个量级。

调整大小所需的时间是线性阶的，但是将大小加大倍能够一定时间减少时间。

1.3 二维数组

前面说的都是一维数组，即只是一个简单的序列。那二维数组就是类似一个表格，像一个网格。一般我们说二维数组有几行几列。

要访问网格的的一个项，我们需要定位到第几行第几列，所以会使用两个下标来定位一个项。

下面自定义一个二维数组，名称为Grid，代码如下：

class Grid:
    
    def __init__(self, rows, columns, fill_value=None):
        self._data = Array(rows)
        for row in range(rows):
            self._data[row] = Array(columns, fill_value)
            
    def get_height(self):
        """返回行数"""
        return len(self._data)
    
    def get_width(self):
        """返回列数"""
        return len(self._data[0])
    
    def __getitem__(self, index):
        return self._data[index]
    
    def __str__(self):
        res = ""
        for row in range(self.get_height()):
            for col in range(self.get_width()):
                res += str(self._data[row, col])
            res += "\n"
        return res
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

2.链表

参考：https://blog.csdn.net/m0_70964767/article/details/126184640

2.1 链表分类

一般链表值讲单链表和双链表。

单链表和上链表的结构如下图：

链表的基本单位是节点（Node），节点主要由数据项和链接两部分组成，数据项代表本节点的数据，链接代表下个（或上个）节点的位置链接。可以看到链表就像一列火车一样，而每个节点就相当于每个车厢一样被连接起来。

在单链表中，通过一个外部的头链接（head）来访问第1个项。然后通过第1项产生的、串联起来的、单个链条（上图中的箭头表示），来访问其他后面的项。在单链表中，很容易获取某个项的后继项，但不是很容易获取前驱项。

在双链表中，包含了两个方向的链接，因此很容易获取某个项的后继项和前驱项。双链表还有一个外部链接是尾链接（tail），它允许直接访问双链表的最后一项。

无论单链表还是双链表，最后一项都没有只想下一项的链接，如上图中斜杠画出的，这种叫做空链接（empty link）。双链表的第一项是没有指向前驱项的链接的。

链表相对于数组，插入和删除有很大不同：

• 一旦找到一个插入点或删除点，可以直接插入删除，不需要再内存中移动数据项。
• 每一次插入和删除的过程中，链表结构会调整大小，并不需要额外的内存代价，也不需要复制数据项。

2.2 链表特点

数组的项是必须存储在连续的内存中，也就是数组中项的逻辑顺序时和内存中的物理单元序列紧密耦合。

链表则不同，链表的特点是非连续性内存。只要计算机遵照链表结构中一个给定项的地址和位置的链接，就能够在内存中找到它的单元在何处。

上面我们知道，链表由数据项和链接组成，那么在python中，就可以使用对象引用建立节点和链表结构。在pyhton中，任何变量都可以引用任何内容，包括None值，它意味着一个空链接。由此，python可以通过两个字段的对象来表示一个节点：数据项的一个引用和另一个节点的一个引用。python为每一个新的节点对象提供了动态分配的非连续内存，并且当对象不再被应用程序引用的时候，会自动垃圾回收。

2.3 单链表

2.3.1 结构

前面说过链表的结构特点，由一个数据项和下一个节点的引用组成，单链表节点的代码如下：

class Node:
    
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
1
2
3
4
5

如果定义一个单链表类，则初始化方法init需要传入一个Node对象，并且把其设置为头节点，代码如下：

class SingleLinkedList:

    def __int__(self, node=None):
        if node is None:
            self._head = node
        else:
            self._head = Node(node)
1
2
3
4
5
6
7

2.3.2 常用方法

上述方法都是链表常用的方法，下面一一实现。

1.is_empty()

判断链表是否为空，返回True或False。因为单链表是单项从头一次向后的，所有如果链表的头是None就是空，代码如下：

def is_empty(self):
    return self._head is None
1
2

2.travel()

遍历整个链表，需要从头节点开始，依次寻找下个节点，直到没有下个节点（即当前节点的链接为空链接）为止，则遍历完成，代码如下：

def travel(self):
  	probe = self._head
  	while probe:
    		print(probe.data)
    		probe = probe.next
1
2
3
4
5

整个遍历过程在时间上是线性的，并且不需要额外的内存。

3.length()

计算链表的长度，链表计算长度比较麻烦，因为得从头开始遍历，一个个数，代码如下：

def length(self):
    count = 0
    probe = self._head
    while probe:
        count += 1
        probe = probe.next
        return count
1
2
3
4
5
6
7

4.search(item)

查找结点是否存在。遍历链表，比较节点数据与查找数据是否相同。代码如下：

def search(self, item):
    probe = self._head
    while probe:
        if probe.data == item:
          return True
        probe = probe.next
    return False
1
2
3
4
5
6
7

5.add(item)

在链表头部添加一项。如果原链表头部不是None，需要把新添加的这一项设为头部，并把原来头部节点设为新头部的下个节点。代码如下：

def add(self, item):
  	self._head = Node(item, self._head)
1
2

6.append(item)

链表尾部添加元素。如果head为None，将新的节点设为头节点即可；如果head不为None，则需要从头搜索到最后一个节点，并将其next指针指向新的节点。

def append(self, item):
    new_node = Node(item)
    if self._head is None:
      	self._head = new_node
    else:
        # 遍历到最后
        probe = self._head
        while probe:
            probe = probe.next
            probe.next = new_node
1
2
3
4
5
6
7
8
9
10

7.insert(pos,item)

在指定位置添加元素。有两种情况，如果指定位置的节点为空或next指针为None，则意味着插入位置大于等于链表最后一个节点了，因此，把新的项放在链表的末尾；如果指定位置的节点不为空且next指针不为None，则意味着插入位置小于链表最后一个节点位置，因此，把新的项放在指定位置，且新的项的next指针是原位置的项，前一项的next指针是新的项。

代码如下：

def insert(self, index, item):
    if self._head is None or index <= 0:
      self._head = Node(item, self._head)
    else:
        # 遍历到指定位置
        probe = self._head
        while probe.next and index > 1:
            probe = probe.next
            index -= 1
            probe.next = Node(item, probe.next)
1
2
3
4
5
6
7
8
9
10

8.remove(item)

删除指定节点。

def remove(self, item):
    probe = self._head
    if self._head is None:
      	return
    while probe:
        if probe.next.data == item:
            probe.next = probe.next.next
            probe = probe.next
1
2
3
4
5
6
7
8

全部代码如下：

class Node:

    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class SingleLinkedList:

    def __int__(self, node=None):
        if node is None:
            self._head = node
        else:
            self._head = Node(node)

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

    def travel(self):
        probe = self._head
        while probe:
            print(probe.data)
            probe = probe.next

    def length(self):
        count = 0
        probe = self._head
        while probe:
            count += 1
            probe = probe.next
        return count

    def search(self, item):
        probe = self._head
        while probe:
            if probe.data == item:
                return True
            probe = probe.next
        return False

    def add(self, item):
        self._head = Node(item, self._head)

    def append(self, item):
        new_node = Node(item)
        if self._head is None:
            self._head = new_node
        else:
            # 遍历到最后
            probe = self._head
            while probe:
                probe = probe.next
            probe.next = new_node

    def insert(self, index, item):
        if self._head is None or index <= 0:
            self._head = Node(item, self._head)
        else:
            # 遍历到指定位置
            probe = self._head
            while probe.next and index > 1:
                probe = probe.next
                index -= 1
            probe.next = Node(item, probe.next)

    def remove(self, item):
        probe = self._head
        if self._head is None:
            return
        while probe:
            if probe.next.data == item:
                probe.next = probe.next.next
            probe = probe.next
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

2.4 双链表

双链表比单链表更加灵活，可以从给定节点移动到前一个节点，可以直接移动到最后一个节点。

双链表的节点除了有指向下一个节点的链接next，还有指向前一个节点的链接previous。

双链表的节点及结构如下，我们继承原来单节点的Node：

class TwoManyNode(Node):
    def __init__(self, data, previous=None, next=None):
        super().__init__(data, next)
        self.previous = previous


class DoubleLinkedList:
    def __init__(self, node=None):
        if node is None:
            self._head = TwoManyNode(node)
        else:
            self._head = node
1
2
3
4
5
6
7
8
9
10
11
12

3.栈

3.1 概览

栈是一种线性集合，就像餐厅的盘子，先放的被压在下面，后放的在上面，在取出使用时，也是从顶部开始取，这种类似的结构和行为。栈的访问被限制在顶部，只能从顶部依次访问，遵循后进先出（last-in first-out，LIFO）的协议。

从栈放入项和从栈删除项分别叫做压入（push）和弹出（pop）。下图是栈的压入和弹出操作对栈的影响，栈顶的项用阴影表示：

3.2 栈方法

除了push和pop之外栈接口还提供了一个名为peek的操作，用来查看栈顶部的元素。另外，和其他集合一样，栈类型也有clear、is_empty、len、str、in和+操作，还有一个迭代器。其常见方法如下：

注意pop和peek有个重要的先验条件。

3.3 栈实现

栈并不是python内建的数据类型，有时候可以使用列表类模拟栈，但是列表可以在任意位置插入删除替换元素，并不安全。接下来基于数组来实现一个栈，数组使用我们前面讲过的数组Array类。初始化时，和数组一样，有逻辑大小和物理大小，使用DEFAULT_CAPACITY来初始化默认数组的大小，使用self._size来表示逻辑大小。在压入和弹出多次后，需要时，我们也需要根据策略来调整数组的大小，这里不再演示，可参考数组。

代码如下：

from struct1_Array import Array


class ArrayStack:
    """基于数组实现的栈"""
    # 栈的默认大小
    DEFAULT_CAPACITY = 10

    def __init__(self, source_collection=None):
        # 初始化数组
        self._items = Array(ArrayStack.DEFAULT_CAPACITY)
        # 栈的实际项目数量
        self._size = 0
        
    def __len__(self):
        return self._size
    
    def __iter__(self):
        cursor = 0
        while cursor < len(self):
            yield self._items[cursor]
            cursor += 1
            
    def peek(self):
        return self._items[len(self) - 1]
    
    def clear(self):
        self._size = 0
        self._items = Array(ArrayStack.DEFAULT_CAPACITY)
        
    def push(self, item):
        # 如果有需要可以像数组一样改变大小
        self._items[len(self)] = item
        self._size += 1
        
    def pop(self):
        item = self._items[len(self) - 1]
        # 如果有需要可以像数组一样改变大小
        self._size -= 1
        return item
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

4.队列

4.1 概述

和栈一样，队列也是线性的集合。

与栈不同，队列的特点是只能队尾插入，从队头删除。队列支持先进先出（first-in first-out，FIFO）的协议。有点像我们排队买票，先排队的先买票出列。

队列又两个基本操作，add在队尾添加一项，pop从队头删除一项。下图是一个队列再生命周期的各个阶段的样子。

一开始队列是空的了然后添加一个a元素；接下来有添加了b、c、d三个元素，然后弹出一项，依次类推。

有个和队列相关的集合叫优先队列，前面说的队列中，要弹出的项总是等待时间最长的项。优先队列是把优先级考虑进来：优先级高的先被弹出，相同优先级的，等待时间长的先弹出。

队列在计算机中的应用非常广泛，很多都涉及调度和对共享资源的访问，如：

• CPU访问：进程排队等候访问一个共享的CPU资源；
• 磁盘访问：进程排队等候访问共享的辅助存储设备；
• 打印机访问：打印任务排队等候访问共享的激光打印机。

进程调度可涉及简单队列和优先队列。例如，和那些需要大量计算的进程相比，请求键盘输入和屏幕输出的进程通常会给予较高的优先级。

4.2 队列方法

队列常见的方法如下表：

注意pop和peek有个重要的先验条件。

4.3 队列实现

python标准库提供Queue模块来使用队列。

如果自己实现，简单的可以使用python列表模拟队列。列表哪一端是队头，哪一端是队尾，都无关紧要。最简单的是使用列表的append把元素加到队列的队尾，使用pop(0)方法从列表前面删除项并返回。但是这样的话其他的列表操作也可以操作队列。

本节队列的结构可以使用数组或链表来实现。由于链表的行为更能较好的贴合队列行为，下面使用一个单链表实现一个队列。

队列初始化会维护三个变量，front表示队头，即链表的头部节点；rear表示队尾，即链表的尾部节点，主要是由于单链表访问尾部需要从头遍历，所以自己维护方便操作；size表示对列的大小。

由于其他方法与集合都是类似，下面只写队列的add和pop方法，看看如何操作队列。代码如下：

class Node:

    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LinkedQueue:
    """基于单链表实现的队列"""

    def __init__(self, front=None, rear=None):
        # 队头：即链表的第一个节点
        self._front = front
        # 队尾：即列表的尾部节点
        self._rear = rear
        # 栈的实际项目数量
        self._size = 0

    def is_empty(self):
        return self._size < 1

    def add(self, item):
        """队尾添加
        先根据item创建一个新的节点
        如果是空队列，直接把新的节点设为链表的头
        如果不是，则把最后一个节点的next指针设置为新节点，并把新节点设为队尾"""
        new_node = Node(item, None)
        if self.is_empty():
            self._front = new_node
        else:
            self._rear.next = new_node
        self._rear = new_node
        self._size += 1

    def pop(self):
        """队头删除一项并返回"""
        # 获取现在队头的元素
        old_item = self._front.data
        # 把第二项设为队头
        self._front = self._front.next
        # 如果队头是None，说明原来就一项，则把队尾也设为None
        if self._front is None:
            self._rear = None
        self._size -= 1
        return old_item
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

5.树

5.1 概览

前面学的线性结构中，所有项都有一个不同的前驱，除了最后一项都有一个后继。在树中，前驱和后继被父节点和子节点代替。树的结构就如其名字，像树一样，有节点和分支，树主要有两个特征：

• 每个项都有多个子节点；
• 除了叫做根的特殊项，所有其他项都只有一个父节点。

树的结构如下图：

树结构在计算机也有很多用途，比如文件系统有根目录、子目录，文件的目录结构可以使用树结构。

树结构常见的术语：

1.节点

树种存储的项

2.根

树中最顶端的节点，只有它没有父节点，如上图的H节点。

3.子节点

一个节点紧挨着的下面的节点，如上图B是H的子节点。一个节点可以有多个自己点，并且子节点被视为按照从左到右的顺序排列。最左边的节点称为第一个子节点，最右边的节点称为最后一个子节点。

4.父节点

一个节点紧挨着的上面的节点，如上图H是B的父节点。一个节点只能有一个父节点。

5.兄弟节点

拥有共同的父节点的子节点。如上图的B和F互为兄弟节点。

6.叶子节点

没有子节点的节点

7.内部节点

至少有一个子节点的节点

8.边/分支/连接

将一个父节点连接到其子节点的线

9.后代

一个节点的子节点，以及子节点的子节点，一直到叶子节点

10.祖先

一个节点的父节点，以及父节点的父节点，一直到根节点

11.路径

连接一个节点与其一个后代节点的边的序列

12.路径长度

路径中边的数目

13.深度或层级

一个节点的深度或层级等于将其连接到根节点的路径的长度。因此根节点的深度或层级是0，根节点的子节点的层级为1，依次类推。

14.高度

树中最长的路径的长度，或者说树中的叶子节点的最大层级树数。一个空的数，高度是-1。

15.子树

将一个节点和其所有的子节点考虑在内，所形成的一个树。

5.2 二叉树

5.2.1 什么是二叉树

二叉树与普通的树不同，在二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树中，只有一个子节点的时候，它要么是左子节点，要么是右子节点。如下图两个二叉树，是不同的二叉树，但是当做普通树的时候他俩没有区别。

5.2.2 二叉树的分类

树可以有各种形状和大小，一些树是分叉的，一些是茂密的。根据二叉树的高度和它所包含的节点数目之间的关系，可以对二叉树进行分类。

（1）满二叉树

所谓的满二叉树就是每一层级都包含了完整的节点内容，也就是说，所有的内部节点都有两个子节点，且所有的子节点都在最低的一层。如下图：

满二叉树的高度H和节点数目N是有一定关系，给定高度，节点数目的值如下

​ N = 1 + 2 + 4 + … + 2H

即N = 2的H+1次方 - 1。

给定N个几点的满二叉树，其深度是：

​ H = log2(N + 1) - 1

即H等于log以2为底的N + 1，减-1。

（2）完全二叉树

一颗二叉树的深度为H，除了第H层外，其他各层的节点都有两个子节点，且第H层的所有节点都集中在最左边。

满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。

（3）二叉搜索树

每个节点具有大小。可以为空树，如若不为空，则若它的左子树不空，则左子树上的所有结点的值均小于根节点的值；若它的右子树不空，则右子树上的所有结点的值均大于根节点的值，左右子树分别为二叉排序树。

有可能二叉搜索树已经退化为链表，搜索一个元素的时间复杂度从O(lgn)退化为O(n)出现这种情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树。

（4）平衡二叉树

它是一个空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。

这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

5.3 二叉树遍历

5.3.1 前序遍历

前序遍历是先访问树的根节点，然后以类似的方式分别遍历左子树和右子树。如下图所示

节点访问顺序是：H B A C F J E

5.3.2 中序遍历

中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。这个算法尽量地移动到树的最左边，然后才开始访问节点。访问的顺序如下图：

5.3.3 后序遍历

后续遍历算法会先遍历左子树，然后是右子树，最后访问根节点。顺序如下图

5.3.4 层序遍历

层序遍历是首先从0层级开始，在每一层按照从左到右顺序访问节点。访问顺序如下图：

5.4 树实现

以链表实现为例，实现二叉树。

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
 
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
 
    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t
 
    def getRightChild(self):
        return self.rightChild
 
    def getLeftChild(self):
        return self.leftChild
 
    def setRootVal(self,obj):
        self.key = obj
 
    def getRootVal(self):
        return self.key
 
 
if __name__ == '__main__':
    r = BinaryTree('a')
    r.insertLeft('b')
    r.insertRight('c')
    r.getRightChild().setRootVal('hello')
    r.getLeftChild().insertRight('d')
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