基础知识点

• 数据结构的概念
• 栈
• 队列
• 链表

数据结构

数据结构( data structure )是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重地依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。

栈允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。

复杂度分析

栈属于常见的一种线性结构，对于进栈和退栈而言，时间复杂度都为 O(1)

栈的实现

1. 创建一个 Stack 的类

对栈进行初始化参数设计

具体实现代码如下：

class Stack(object):
    def __init__(self, limit=10):
        self.stack = [] #存放元素
        self.limit = limit #栈容量极限

2. push 进栈

压入 push ：将新元素放在栈顶

当新元素入栈时，栈顶上移，新元素放在栈顶。

具体实现代码如下:

def push(self, data):
    if len(self.stack) >= self.limit: #判断栈是否溢出
        print('StackOverflowError')
            pass
    self.stack.append(data)

3. pop 退栈

弹出 pop ：从栈顶移出一个数据

• 栈顶元素拷贝出来
• 栈顶下移
• 拷贝出来的栈顶作为函数返回值

具体实现代码如下:

def pop(self):
    if self.stack:
        return self.stack.pop()
    else:
        raise IndexError('pop from an empty stack') #空栈不能被弹出

4. 添加其他函数

peek : 查看堆栈的最上面的元素

is_empty : 判断栈是否为空

size : 返回栈的大小

具体实现代码如下：

def peek(self):
    if self.stack:
         return self.stack[-1]
def is_empty(self):
    return not bool(self.stack)
def size(self):
    return len(self.stack)

完整代码如下：

class Stack(object):
    def __init__(self, limit=10):
        self.stack = [] #存放元素
        self.limit = limit #栈容量极限
    def push(self, data): #判断栈是否溢出
        if len(self.stack) >= self.limit:
            print('StackOverflowError')
            pass
        self.stack.append(data)
    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError('pop from an empty stack') #空栈不能被弹出
    def peek(self): #查看堆栈的最上面的元素
        if self.stack:
            return self.stack[-1]
    def is_empty(self): #判断栈是否为空
        return not bool(self.stack)
    def size(self): #返回栈的大小
        return len(self.stack)

示例

检查括号是否完全匹配

在这个实验中，我们要求使用一个堆栈检查括号字符串是否平衡

在/home/shiyanlou/下新建一个文件balanced_parentheses.py。根据栈的结构特点，结合 stack 代码，完成以下功能的实现。

有效括号字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

举例：

((())): True

((()): False

(())): False

目标：

1. 使用一个堆栈作为数据结构
2. 来检查括号字符串是否完全匹配

答案：

class Stack(object):
    def __init__(self, limit=10):
        self.stack = [] #存放元素
        self.limit = limit #栈容量极限
    def push(self, data): #判断栈是否溢出
        if len(self.stack) >= self.limit:
            print('StackOverflowError')
            pass
        self.stack.append(data)
    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError('pop from an empty stack') #空栈不能被弹出
    def peek(self): #查看堆栈的最上面的元素
        if self.stack:
            return self.stack[-1]
    def is_empty(self): #判断栈是否为空
        return not bool(self.stack)
    def size(self): #返回栈的大小
        return len(self.stack)

def balanced_parentheses(parentheses):
    stack = Stack(len(parentheses))
    for parenthesis in parentheses:
        if parenthesis == '(':
            stack.push(parenthesis)
        elif parenthesis == ')':
            if stack.is_empty():
                return False
            stack.pop()
    return stack.is_empty()

if __name__ == '__main__':
    examples = ['((()))', '((())', '(()))']
    print('Balanced parentheses demonstration:\n')
    for example in examples:
        print(example + ': ' + str(balanced_parentheses(example)))

链表

链表(linked_list)是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

链表通过将链点 i 与其邻居链点 i+1 通过指针相关联，从索引 0 到索引 N-1 对链点进行排序。

链表分为单链表和双链表两种。

单链表

1. 创建 Node 类

创建一个 Node 的类，作为基础数据结构：链点，并初始化对应的内参。

具体实现代码如下：

class Node:
    def __init__(self, data):
        self.data = data #表示对应的元素值
        self.next = None #表示下一个链接的链点

2. 创建 Linked_List 类

创建一个 Linked_List 的类，并初始化对应的内参。

具体实现代码如下：

class Linked_List:
    def __init__(self):
        self.head = None #表示链表的头部元素
    def initlist(self,data_list):    #链表初始化函数
        self.head=Node(data_list[0])   #创建头结点
        temp=self.head
        for i in data_list[1:]: #逐个为 data 内的数据创建结点, 建立链表
            node=Node(i)
            temp.next=node
            temp=temp.next

3. 添加 is_empty 函数

添加一个 is_empty 的函数，功能是判断链表是否为空

具体实现代码如下：

def is_empty(self):
        return self.Head is None #判断链表是否为空

4. 添加 insert 函数

insert(item) 往链表中任意位置添加一个 item 元素

流程如下：

1. Vertex vtx = new Vertex(v) 初始化一个新的点
2. tail.next = vtx 队列尾部的后继是这个新的点
3. tail = vtx 然后让队列尾部指针指向这个新的点

具体实现代码如下：

def insert(self,key,value): #链表插入数据函数
        if key<0 or key>self.get_length()-1:
            print("insert error")
        temp=self.head
        i=0
        while i<=key: #遍历找到索引值为 key 的结点后, 在其后面插入结点
            pre=temp
            temp=temp.next
            i=i+1
        node=Node(value)
        pre.next=node
        node.next=temp

5. 添加 remove 函数

remove() 从链表中任意位置删除一个元素

流程如下：

1. 先判断队列是否为空，为空即退出 dequeue 操作，不为空即继续后续操作
2. temp = head 设置一个 temp 指针，使它的指针指向队列头部
3. head = head.next 队列头部指针，使之指向队列头部的后继(即队列头部元素出队)
4. delete temp 删除 temp 指针

具体实现代码如下：

def remove(self,key):  #链表删除数据函数
        if key<0 or key>self.get_length()-1:
            print("insert error")
        i=0
        temp=self.head
        while temp !=None:  #遍历找到索引值为 key 的结点
            pre=temp
            temp=temp.next
            i=i+1
            if i==key:
                pre.next=temp.next
                temp=None
                return True
        pre.next=None

6. 添加其他函数

get_length:获取链表的长度

print_list:遍历链表，并将元素依次打印出来

reverse:将链表反转

具体实现代码如下：

 def get_length(self):  #获取链表的长度
        temp=self.head #临时变量指向队列头部
        length=0 #计算链表的长度变量
        while temp!=None:
            length=length+1
            temp=temp.next
        return length #返回链表的长度
    def print_list(self):   #遍历链表，并将元素依次打印出来
        print("linked_list:")
        temp = self.head #临时变量指向队列头部
        while temp is not None:
            print(temp.data)
            temp = temp.next
    def reverse(self): #将链表反转
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

复杂度分析

链表属于常见的一种线性结构，对于插入和移除而言，时间复杂度都为 O(1)

但是对于搜索操作而言，不管从链表的头部还是尾部，都需要遍历 O(n)，所以最好复杂度为 O(1)，最坏的情况就是从头部遍历到尾部才搜索出对应的元素，所以最坏复杂度为 O(n)，平均复杂度为 O(n)。

归纳如下：

• 最好复杂度为 O(1)
• 最坏复杂度为 O(n)
• 平均复杂度为 O(n)

双链表

双向链表（Double_linked_list）也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

class Node(object):
    # 双向链表节点
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None
class DLinkList(object):
    # 双向链表
    def __init__(self):
        self._head = None
    def is_empty(self):
        # 判断链表是否为空
        return self._head == None
    def get_length(self):
        # 返回链表的长度
        cur = self._head
        count = 0
        while cur != None:
            count=count+1
            cur = cur.next
        return count
    def travel(self):
        # 遍历链表
        cur = self._head
        while cur != None:
            print(cur.item)
            cur = cur.next
        print("")
    def add(self, item):
        # 头部插入元素
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 将node的next指向_head的头节点
            node.next = self._head
            # 将_head的头节点的prev指向node
            self._head.prev = node
            # 将_head 指向node
            self._head = node
    def append(self, item):
        # 尾部插入元素
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 移动到链表尾部
            cur = self._head
            while cur.next != None:
                cur = cur.next
            # 将尾节点cur的next指向node
            cur.next = node
            # 将node的prev指向cur
            node.prev = cur
    def search(self, item):
        # 查找元素是否存在
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False
    def insert(self, pos, item):
        # 在指定位置添加节点
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向cur的下一个节点
            node.next = cur.next
            # 将cur的下一个节点的prev指向node
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node
    def remove(self, item):
        # 删除元素
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                # 如果首节点的元素即是要删除的元素
                if cur.next == None:
                    # 如果链表只有这一个节点
                    self._head = None
                else:
                    # 将第二个节点的prev设置为None
                    cur.next.prev = None
                    # 将_head指向第二个节点
                    self._head = cur.next
                return
            while cur != None:
                if cur.item == item:
                    # 将cur的前一个节点的next指向cur的后一个节点
                    cur.prev.next = cur.next
                    # 将cur的后一个节点的prev指向cur的前一个节点
                    cur.next.prev = cur.prev
                    break
                cur = cur.next

示例

交换单链表里两个链点

在这个实验中，我们要给定两个值，如果这两个值都在单链表的链点中，即交换这两个链点在单链表的位置。

举例：

1->2->3->4->5

input:1 4 output:4->2->3->1->5

目标：

1. 交换两个链点在链表中的位置
2. 不改变其他链点在链表中的位置

思路：

• 采用 insert 的思想，对于要交换的两个链点 d1 d2，各自声明新的 D1 D2 ，使 D1=d1, D2=d2
• 然后把 然后再根据 d1 d2 的位置，改变索引的位置，即完成交换的全部操作

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Linkedlist:
    def __init__(self):
        self.head = None
    def print_list(self):   #遍历链表，并将元素依次打印出来
        print("linked_list:")
        temp=self.head
        new_list=[]
        while temp is not None:
            new_list.append(temp.data)
            temp=temp.next
        print(new_list)
    def insert(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
    def swapNodes(self, d1, d2):
        prevD1 = None
        prevD2 = None
        if d1 == d2:
            return
        else:
            D1 = self.head
            while D1 is not None and D1.data != d1:
                prevD1 = D1
                D1 = D1.next
            D2 = self.head
            while D2 is not None and D2.data != d2:
                prevD2 = D2
                D2 = D2.next
            if D1 is None and D2 is None:
                return
            if prevD1 is not None:
                prevD1.next = D2
            else:
                self.head = D2
            if prevD2 is not None:
                prevD2.next = D1
            else:
                self.head = D1
            temp = D1.next
            D1.next = D2.next
            D2.next = temp

if __name__ == '__main__':
    list = Linkedlist()
    list.insert(5)
    list.insert(4)
    list.insert(3)
    list.insert(2)
    list.insert(1)
    list.print_list()
    list.swapNodes(1, 4)
    print("After swapping")
    list.print_list()

队列

队列 (queue) 是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列符合先进先出[FIFO]的原则。因为要排队的第一个项目，最终将是第一个要出列的项目，如在现实生活中的队列，先来的站在队列前面，后来的就只能站在队列后面啦。

队列有两种实现形式，分为两种：数组和链表。

在接下来的内容里，我们将以链表的形式实现队列，逐步介绍具体功能是如何实现的。

1. 创建 Node 类

创建一个 Node 的类，作为基础数据结构：链点，并初始化对应的内参。

具体实现代码如下

class Node(object):
    def __init__(self,elem,next=None):
        self.elem = elem #表示对应的元素值
        self.next=next #表示下一个链接的链点

2. 创建 Queue 类

创建一个 Queue 的类，以链表形式的队列，并初始化对应的内参。

具体实现代码如下：

class Queue(object):
    def __init__(self):
        self.head = None #头部链点为 None
        self.rear = None #尾部链点为 None

3. 添加 is_empty 函数

添加一个 is_empty 的函数，功能是判断队列是否为空

具体实现代码如下：

    def is_empty(self):
        return self.head is None #判断队列是否为空

4. 添加 enqueue 函数

添加一个 enqueue(elem) 函数，功能是往队列中添加一个 elem 元素

流程如下：

1. Vertex vtx = new Vertex(v) 初始化一个新的点
2. tail.next = vtx 队列尾部的后继是这个新的点
3. tail = vtx 然后让队列尾部指针指向这个新的点

效果演示：往已知队列[29,9,53]里面添加一个 80 元素

具体实现代码如下：

    def enqueue(self, elem):
        p = Node(elem) #初始化一个新的点
        if self.is_empty():
            self.head = p #队列头部为新的链点
            self.rear = p #队列尾部为新的链点
        else:
            self.rear.next = p #队列尾部的后继是这个新的点
            self.rear =p #然后让队列尾部指针指向这个新的点

5. 添加 dequeue 函数

添加一个 dequeue() 函数，功能是从队列头部删除一个元素

流程如下：

1. 先判断队列是否为空，为空即退出 dequeue 操作，不为空即继续后续操作
2. temp = head 设置一个 temp 指针，使它的指针指向队列头部
3. head = head.next 队列头部指针，使之指向队列头部的后继(即队列头部元素出队)
4. delete temp 删除 temp 指针

效果演示：对已知队列[29,9,53,80] 删除头部元素

具体实现代码如下：

    def dequeue(self):
        if self.is_empty(): #判断队列是否为空
            print('Queue_is_empty') #若队列为空，则退出 dequeue 操作
        else:
            result = self.head.elem #result为队列头部元素
            self.head = self.head.next #改变队列头部指针位置
            return result #返回队列头部元素

6. 添加 peek 函数

添加一个 peek() 函数，功能是查看队列头部的元素

流程如下：

1. 判断队列是否为空，为空即返回 NOT_FOUND
2. 队列如果不为空，返回队列头部元素

具体代码实现如下:

    def peek(self):
        if self.is_empty(): #判断队列是否为空
            print('NOT_FOUND') #为空则返回 NOT_FOUND
        else:
            return self.head.elem #返回队列头部元素

7. 添加 print_queue 函数

添加一个 print_queue() 函数，功能是展现队列的元素

    def print_queue(self):
        print("queue:")
        temp=self.head
        myqueue=[] #暂时存放队列数据
        while temp is not None:
            myqueue.append(temp.elem)
            temp=temp.next
        print(myqueue)

最终代码如下：

class Node(object):
    def __init__(self,elem,next=None):
        self.elem = elem #表示对应的元素值
        self.next=next #表示下一个链接的链点
class Queue(object):
    def __init__(self):
        self.head = None #头部链点为 None
        self.rear = None #尾部链点为 None
    def is_empty(self):
        return self.head is None #判断队列是否为空
    def enqueue(self, elem):
        p = Node(elem) #初始化一个新的点
        if self.is_empty():
            self.head = p #队列头部为新的链点
            self.rear = p #队列尾部为新的链点
        else:
            self.rear.next = p #队列尾部的后继是这个新的点
            self.rear =p #然后让队列尾部指针指向这个新的点
    def dequeue(self):
        if self.is_empty(): #判断队列是否为空
            print('Queue_is_empty') #若队列为空，则退出 dequeue 操作
        else:
            result = self.head.elem #result为队列头部元素
            self.head = self.head.next #改变队列头部指针位置
            return result #返回队列头部元素
    def peek(self):
        if self.is_empty(): #判断队列是否为空
            print('NOT_FOUND') #为空则返回 NOT_FOUND
        else:
            return self.head.elem #返回队列头部元素
    def print_queue(self):
        print("queue:")
        temp=self.head
        myqueue=[] #暂时存放队列数据
        while temp is not None:
            myqueue.append(temp.elem)
            temp=temp.next
        print(myqueue)

复杂度分析

队列属于常见的一种线性结构，对于出队和进队而言，时间复杂度都为 O(1)

队列有两种实现形式，数组和链表。我们在前面已经介绍了如何用链表实现的队列，这里就不再赘述，直接给出另一种用数组实现的队列代码，供大家学习参考。

形式：用数组实现

class Queue():
    def __init__(self):
        self.entries = [] #表示队列内的参数
        self.length = 0 #表示队列的长度
        self.front=0 #表示队列头部位置
    def enqueue(self, item):
        self.entries.append(item) #添加元素到队列里面
        self.length = self.length + 1 #队列长度增加 1
    def dequeue(self):
        self.length = self.length - 1 #队列的长度减少 1
        dequeued = self.entries[self.front] #队首元素为dequeued
        self.front-=1 #队首的位置减少1
        self.entries = self.entries[self.front:] #队列的元素更新为退队之后的队列
        return dequeued
    def peek(self):
        return self.entries[0] #直接返回队列的队首元素

示例

设计队列的实现( 在这里我们要求用之前介绍的链表形式实现 )

在队列中实现这些步骤：

1. 初始化创建 Node, Queue 类
2. 依次添加 21 35 58 13 进队列
3. 返回队列头部元素
4. 删除此时队列头部元素
5. 返回此时队列头部元素

class Node(object):
    def __init__(self,elem,next=None):
        self.elem = elem #表示对应的元素值
        self.next=next #表示下一个链接的链点
class Queue(object):
    def __init__(self):
        self.head = None #头部链点为 None
        self.rear = None #尾部链点为 None
    def is_empty(self):
        return self.head is None #判断队列是否为空
    def enqueue(self, elem):
        p = Node(elem) #初始化一个新的点
        if self.is_empty():
            self.head = p #队列头部为新的链点
            self.rear = p #队列尾部为新的链点
        else:
            self.rear.next = p #队列尾部的后继是这个新的点
            self.rear =p #然后让队列尾部指针指向这个新的点
    def dequeue(self):
        if self.is_empty(): #判断队列是否为空
            print('Queue_is_empty') #若队列为空，则退出 dequeue 操作
        else:
            result = self.head.elem #result为队列头部元素
            self.head = self.head.next #改变队列头部指针位置
            return result #返回队列头部元素
    def peek(self):
        if self.is_empty(): #判断队列是否为空
            print('NOT_FOUND') #为空则返回 NOT_FOUND
        else:
            return self.head.elem #返回队列头部元素
    def print_queue(self):
        print("queue:")
        temp=self.head
        myqueue=[] #暂时存放队列数据
        while temp is not None:
            myqueue.append(temp.elem)
            temp=temp.next
        print(myqueue)
if __name__=="__main__":
    queue=Queue()
    queue.enqueue(21)
    queue.enqueue(35)
    queue.enqueue(58)
    queue.enqueue(13)
    queue.print_queue()
    print(queue.peek())
    queue.dequeue()
    queue.print_queue()
    print(queue.peek())

进阶知识点

• 树
• 字典树
• 堆
• 图
• 并查集

树

树 (tree) 是一种非常高效的非线性存储结构。树，可以很形象的理解，有根，有叶子，对应在数据结构中就是根节点、叶子节点，同一层的叶子叫兄弟节点，邻近不同层的叫父子节点，非常好理解。

注：定义来自百度百科。

其他概念解释

• 二叉树，就是每个节点都至多有二个子节点的树。
• 满二叉树，就是除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。
• 完全二叉树，就是叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

常见的二叉树如下图所示

在接下来的内容里，我们将逐步介绍二叉树的具体功能是如何实现的。

思路：

1. 先定义一个节点 node 类，存储数据 data 和左子节点 left 以及 右子节点 right。
2. 再实现二叉树 binary_tree 的类，应至少有以下属性和函数： 属性：有一个根节点（root) , 它是 node 类。 函数：添加子节点 add ，返回父节点 get_parent，删除子节点 delete。

步骤如下：

1. 创建 Node 类

创建一个 Node 的类，作为基础数据结构：链点，并初始化对应的内参。

具体实现代码如下：

class Node(object):
    def __init__(self,item):
        self.item = item #表示对应的元素
        self.left=None #表示左子节点
        self.right=None #表示右子节点
    def __str__(self):
        return str(self.item)  #print 一个 Node 类时会打印 __str__ 的返回值

2. 创建 Tree 类

创建一个 Tree 的类，定义根节点。

具体实现代码如下：

class Tree(object):
    def __init__(self):
        self.root=Node('root')  #根节点定义为 root 永不删除，作为哨兵使用。

3. 添加 add 函数

添加一个 add(item) 的函数，功能是添加子节点到树里面。

具体实现代码如下：

    def add(self,item):
        node = Node(item)
        if self.root is None:  #如果二叉树为空，那么生成的二叉树最终为新插入树的点
            self.root = node
        else:
            q = [self.root] # 将q列表，添加二叉树的根节点
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None: #左子树为空则将点添加到左子树
                    pop_node.left = node
                    return
                elif pop_node.right is None: #右子树为空则将点添加到右子树
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)

4. 添加 get_parent 函数

添加一个 get_parent(item) 函数，功能是找到 item 的父节点。

具体实现代码如下：

    def get_parent(self, item):
        if self.root.item == item:
            return None  # 根节点没有父节点
        tmp = [self.root] # 将tmp列表，添加二叉树的根节点
        while tmp:
            pop_node = tmp.pop(0)
            if pop_node.left and pop_node.left.item == item: #某点的左子树为寻找的点
                return pop_node #返回某点，即为寻找点的父节点
            if pop_node.right and pop_node.right.item == item: #某点的右子树为寻找的点
                return pop_node #返回某点，即为寻找点的父节点
            if pop_node.left is not None: #添加tmp 元素
                tmp.append(pop_node.left)
            if pop_node.right is not None:
                tmp.append(pop_node.right)
        return None

5. 添加 delete 函数

添加一个 delete(item) 函数，功能是从二叉树中删除一个子节点。

思路如下：

先获取待删除节点 item 的父节点。
    如果父节点不为空，判断 item 的左右子树：
        如果左子树为空，那么判断 item 是父节点的左孩子，还是右孩子；
            如果是左孩子，将父节点的左指针指向 item 的右子树，反之将父节点的右指针指向 item 的右子树。
        如果右子树为空，那么判断 item 是父节点的左孩子，还是右孩子；
            如果是左孩子，将父节点的左指针指向 item 的左子树，反之将父节点的右指针指向 item 的左子树。
        如果左右子树均不为空，寻找右子树中的最左叶子节点 x ，将 x 替代要删除的节点。
    删除成功，返回 True。
    删除失败, 返回 False。

效果演示：对已知二叉树删除元素 32

具体实现代码如下：

    def delete(self, item):
        if self.root is None:  # 如果根为空，就什么也不做
            return False

        parent = self.get_parent(item)
        if parent:
            del_node = parent.left if parent.left.item == item else parent.right  # 待删除节点
            if del_node.left is None:
                if parent.left.item == item:
                    parent.left = del_node.right
                else:
                    parent.right = del_node.right
                del del_node
                return True
            elif del_node.right is None:
                if parent.left.item == item:
                    parent.left = del_node.left
                else:
                    parent.right = del_node.left
                del del_node
                return True
            else:  # 左右子树都不为空
                tmp_pre = del_node
                tmp_next = del_node.right
                if tmp_next.left is None:
                    # 替代
                    tmp_pre.right = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right

                else:
                    while tmp_next.left:  # 让tmp指向右子树的最后一个叶子
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left
                    # 替代
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                if parent.left.item == item:
                    parent.left = tmp_next
                else:
                    parent.right = tmp_next
                del del_node
                return True
        else:
            return False

二叉搜索树

二叉搜索树又称二叉查找树，亦称二叉排序树，如下图所示：

它主要用于搜索。 它或者是一棵空树，或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 左、右子树也分别为二叉排序树。

平衡二叉树

平衡二叉树(平衡二叉树又被称为 AVL 树 )是基于二分法的策略提高数据的查找速度的二叉树的数据结构。

特点：平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则：

1. 非叶子节点只能允许最多两个子节点存在。
2. 每一个非叶子节点数据分布规则为左边的子节点小于前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如 hash 值)。

二叉树的遍历问题

遍历原理：

二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

这里有两个关键词：访问和次序。

访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等。它算作是一个抽象操作。

二叉树的遍历次序不同于线性结构，最多也就是从头到尾、循环和双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。

二叉树遍历方法

二叉树的遍历方式可以有很多，如果我们限制从左到右的顺序，就主要分为三种：

1. 中序遍历
2. 后序遍历
3. 前序遍历

中序遍历

1. 先处理左子树，然后处理当前节点，再处理右子树；
2. 对于一颗二叉查找树，所有的信息都是有序排列的，中序遍历可以是信息有序输出，且运行时间为 O(n)；
3. 递归实现中序遍历。

在之前的 Tree 类里面添加 inorder 函数

参考代码如下：

    def inorder(self,node):  # 中序遍历
        if node is None:
            return []
        result = [node.item]
        left_item = self.inorder(node.left)
        right_item = self.inorder(node.right)
        return left_item + result + right_item

中序遍历的效果演示:

后序遍历

1. 先处理左右子树，然后再处理当前节点，运行时间为 O（n）
2. 递归实现后序遍历

参考代码如下：

    def postorder(self,node):  # 后序遍历
        if node is None:
            return []
        result = [node.item]
        left_item = self.postorder(node.left)
        right_item = self.postorder(node.right)
        return left_item + right_item + result

先序遍历

1. 先处理当前节点，再处理左右子树；
2. 递归实现先序遍历。

参考代码：

    def preorder(self,node):  # 先序遍历
        if node is None:
            return []
        result = [node.item]
        left_item = self.preorder(node.left)
        right_item = self.preorder(node.right)
        return result + left_item + right_item

示例

设计二叉树三种遍历的实现

在代码中实现这些步骤：

1. 初始化创建 Node,Queue 类；
2. 将 1-9 添加到二叉树里面(使用 add 函数)；
3. 将三种遍历过程，最后打印出来。

效果:

input:

[1,2,3,4,5,6,7,8,9]

output:

中序遍历: [7,3,8,1,9,4,10,’root’,5,2,6] 个人理解：顺时针画圈

先序遍历: [‘root’,1,3,7,8,4,9,10,2,5,6]

后序遍历： [7,8,3,9,10,4,1,5,6,2,’root’] 个人理解：逆时针画圈

class Node(object):
    def __init__(self,item):
        self.item=item #表示对应的元素
        self.left=None #表示左节点
        self.right=None #表示右节点
    def __str__(self):
        return str(self.item)  #print 一个 Node 类时会打印 __str__ 的返回值
class Tree(object):
    def __init__(self):
        self.root=Node('root')  #根节点定义为 root 永不删除，作为哨兵使用。
    def add(self,item):
        node = Node(item)
        if self.root is None:  #如果二叉树为空，那么生成的二叉树最终为新插入树的点
            self.root = node
        else:
            q = [self.root] # 将q列表，添加二叉树的根节点
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None: #左子树为空则将点添加到左子树
                    pop_node.left = node
                    return
                elif pop_node.right is None: #右子树为空则将点添加到右子树
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)
    def get_parent(self, item):
        if self.root.item == item:
            return None  # 根节点没有父节点
        tmp = [self.root] # 将tmp列表，添加二叉树的根节点
        while tmp:
            pop_node = tmp.pop(0)
            if pop_node.left and pop_node.left.item == item: #某点的左子树为寻找的点
                return pop_node #返回某点，即为寻找点的父节点
            if pop_node.right and pop_node.right.item == item: #某点的右子树为寻找的点
                return pop_node #返回某点，即为寻找点的父节点
            if pop_node.left is not None: #添加tmp 元素
                tmp.append(pop_node.left)
            if pop_node.right is not None:
                tmp.append(pop_node.right)
        return None
    def delete(self, item):
        if self.root is None:  # 如果根为空，就什么也不做
            return False

        parent = self.get_parent(item)
        if parent:
            del_node = parent.left if parent.left.item == item else parent.right  # 待删除节点
            if del_node.left is None:
                if parent.left.item == item:
                    parent.left = del_node.right
                else:
                    parent.right = del_node.right
                del del_node
                return True
            elif del_node.right is None:
                if parent.left.item == item:
                    parent.left = del_node.left
                else:
                    parent.right = del_node.left
                del del_node
                return True
            else:  # 左右子树都不为空
                tmp_pre = del_node
                tmp_next = del_node.right
                if tmp_next.left is None:
                    # 替代
                    tmp_pre.right = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right

                else:
                    while tmp_next.left:  # 让tmp指向右子树的最后一个叶子
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left
                    # 替代
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                if parent.left.item == item:
                    parent.left = tmp_next
                else:
                    parent.right = tmp_next
                del del_node
                return True
        else:
            return False
    def preorder(self,node):  # 先序遍历
        if node is None:
            return []
        result = [node.item]
        left_item = self.preorder(node.left)
        right_item = self.preorder(node.right)
        return result + left_item + right_item

    def inorder(self,node):  # 中序遍历
        if node is None:
            return []
        result = [node.item]
        left_item = self.inorder(node.left)
        right_item = self.inorder(node.right)
        return left_item + result + right_item

    def postorder(self,node):  # 后序遍历
        if node is None:
            return []
        result = [node.item]
        left_item = self.postorder(node.left)
        right_item = self.postorder(node.right)
        return left_item + right_item + result
if __name__ == '__main__':
    t = Tree()
    for i in range(1,11):
        t.add(i)
    print('先序遍历:', t.preorder(t.root))
    print('中序遍历:', t.inorder(t.root))
    print('后序遍历:', t.postorder(t.root))

字典树

字典树，又称单词查找树，Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被==搜索引擎系统用于文本词频统计==。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

字典树的主要性质

它有 3 个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3. 每个节点的所有子节点包含的字符都不相同。

在接下来的内容里，我们将逐步介绍字典树的具体功能是如何实现的。

1. 创建 TrieNode 类

创建一个 TrieNode 的类,构建内置字典结构

具体实现代码如下

class TrieNode:
    def __init__(self):
        self.nodes = dict()  # 构建字典
        self.is_leaf = False

2. 添加 insert 函数

插入一个字到字典树中

具体实现代码如下：

    def insert(self, word: str):
        curr = self
        for char in word:
            if char not in curr.nodes:
                curr.nodes[char] = TrieNode()
            curr = curr.nodes[char]
        curr.is_leaf = True

4. 添加 search 函数

在字典树里面查询一个字

具体实现代码如下：

    def search(self, word: str):
        curr = self
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.is_leaf

class TrieNode:
    def __init__(self):
        self.nodes = dict()
        self.is_leaf = False

    def insert(self,word:str):
        curr = self
        for char in word:
            if char not in curr.nodes:
                curr.nodes[char] = TrieNode()
            curr = curr.nodes[char]
        curr.is_leaf = True

    def insert_many(self,words:[str]):
        for word in words:
            self.insert(word)
    def search(self,word:str):
        curr = self
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.is_leaf

堆

堆 (heap) 是一种经过排序的完全二叉树，其中任一非叶子节点的值均不大于（或不小于）其左孩子和右孩子节点的值。

注：定义来自百度百科。

堆，又被为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。

其他概念解释

• 最大堆 根结点的键值是所有堆结点键值中最大者。
• 最小堆 根结点的键值是所有堆结点键值中最小者。

最小堆

最大堆

堆有两点需要了解，一是堆一般采用完全二叉树；二是堆中的每一个节点都大于其左右子节点（大顶堆），或者堆中每一个节点都小于其左右子节点（小顶堆）。

1. 创建 heap 类

class heap(object):
    def __init__(self):
        #初始化一个空堆，使用数组来在存放堆元素，节省存储
        self.data_list = []

2. 添加 get_parent_index 函数

    def get_parent_index(self,index):
        #返回父节点的下标
        if index == 0 or index > len(self.data_list) -1:
            return None
        else:
            return (index -1) >> 1

3. 添加 swap 函数

def swap(self,index_a,index_b):
        #交换数组中的两个元素
        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a]

4. 添加 insert 函数

def insert(self,data):
        #先把元素放在最后，然后从后往前依次堆化
        #这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后
        self.data_list.append(data)
        index = len(self.data_list) -1
        parent = self.get_parent_index(index)
        #循环，直到该元素成为堆顶，或小于父节点（对于大顶堆)
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            #交换操作
            self.swap(parent,index)
            index = parent
            parent = self.get_parent_index(parent)

5. 添加 removeMax 函数

    def removeMax(self):
        #删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化
        remove_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]

        #堆化
        self.heapify(0)
        return remove_data

6. 添加 heapify 函数

    def heapify(self,index):
        #从上往下堆化，从index 开始堆化操作 (大顶堆)
        total_index = len(self.data_list) -1
        while True:
            maxvalue_index = index
            if 2*index +1 <=  total_index and self.data_list[2*index +1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +1
            if 2*index +2 <=  total_index and self.data_list[2*index +2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +2
            if maxvalue_index == index:
                break
            self.swap(index,maxvalue_index)
            index = maxvalue_index

示例

请将 元素 1-10 放进堆，并展示建堆情况，及删除堆顶元素情况

实例如下：

建堆: [10, 9, 6, 7, 8, 2, 5, 1, 4, 3]

删除堆顶元素： [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

class heap(object):

    def __init__(self):
        #初始化一个空堆，使用数组来在存放堆元素，节省存储
        self.data_list = []

    def get_parent_index(self,index):
        #返回父节点的下标
        if index == 0 or index > len(self.data_list) -1:
            return None
        else:
            return (index -1) >> 1

    def swap(self,index_a,index_b):
        #交换数组中的两个元素
        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a]

    def insert(self,data):
        #先把元素放在最后，然后从后往前依次堆化
        #这里以大顶堆为例，如果插入元素比父节点大，则交换，直到最后
        self.data_list.append(data)
        index = len(self.data_list) -1
        parent = self.get_parent_index(index)
        #循环，直到该元素成为堆顶，或小于父节点（对于大顶堆)
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            #交换操作
            self.swap(parent,index)
            index = parent
            parent = self.get_parent_index(parent)

    def removeMax(self):
        #删除堆顶元素，然后将最后一个元素放在堆顶，再从上往下依次堆化
        remove_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]

        #堆化
        self.heapify(0)
        return remove_data

    def heapify(self,index):
        #从上往下堆化，从index 开始堆化操作 (大顶堆)
        total_index = len(self.data_list) -1
        while True:
            maxvalue_index = index
            if 2*index +1 <=  total_index and self.data_list[2*index +1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +1
            if 2*index +2 <=  total_index and self.data_list[2*index +2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +2
            if maxvalue_index == index:
                break
            self.swap(index,maxvalue_index)
            index = maxvalue_index

if __name__ == "__main__":
    myheap = heap()
    for i in range(10):
        myheap.insert(i+1)
    print('建堆:',myheap.data_list)
    print("删除堆顶元素：", [myheap.removeMax() for _ in range(10)])

图

下面就通过一个例子来让大家快速地知道什么是图，如下图所示，G1 是有向图，G2 是无向图，每个数据元素称为顶点，在有向图中，从 V1 到 V3 称为一条弧，V3 到 V1 为另一条弧，V1 称为弧尾，V3 称为弧头，在无向图中，从 V1 到 V3 称为一条边。

有 n 个顶点，$$1/2n(n-1)$$条边的无向图称为完全图，有 $$n*(n-1)$$条弧有向图称为有向完全图，有很少条边或图称为稀疏图，反之称为稠密图。在 G2 无向图中，类似 V3 与 V1、V2 和 V4 之间有边的互称为邻接点，与顶点相关联的边数称为顶点的度，例如 V3 顶点的度为 3，而在 G1 有向图中，顶点的度是顶点的出度和入度之和，以顶点为头的弧的数目称为入度，为尾的弧的数目称为出度，例如 V1 顶点的出度为 2，入度为 1，它的度为 1+2=3。

从一个顶点到另一个顶点的顶点序列称为路径，在有向图中，路径是有方向的，路径上边或弧的数目称为路径的长度，如果一条路径中的起始顶点跟结束结点相同，那么称这个路径为环或回路，不出现重复顶点的路径称为简单路径。无向图中，如果一个顶点到另一个顶点有路径，那么它们就是连通的，如果图中的任意两个顶点都是连通的，那么这个图就是连通图，无向图中的极大连通子图称为连通分量，如果是有向图中的任意一对顶点都有路径，那么这个图就是强连通图，相应的它的极大连通子图就称为强连通分量。一个连通图的一个极小连通子图，它包含所有顶点，但足以构成一棵树的 n-1 条边，加一条边必定会形成环，这个就称为生成树。

概念介绍

• 无向图 图是若干个顶点(Vertices)和边(Edges)相互连接组成的。边仅由两个顶点连接，并且没有方向的图称为无向图。
• 有向图 在有向图中，边是单向的：每条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图：比如任务调度的依赖关系，社交网络的任务关系等等都是天然的有向图。
• 度 一个顶点的度是指与该顶点相关联的边的条数，顶点 v 的度记作 d(v)。

表示图通常有四种方法：

• 数组表示法、

• 邻接表、

• 十字链表

• 邻接多重表。

  邻接表是图的一种链式存储结构，十字链表是有向图的另一种链式存储结构，邻接多重表是无向图的另一种链式存储结构。这里主要讲解一下邻接表的表示和实现，邻接表中有两种结点，一种是头结点，另一种是表结点，头结点中存储一个顶点的数据和指向链表中第一个结点，表结点中存储当前顶点在图中的位置和指向下一条边或弧的结点，表头结点用链式或顺序结构方式存储，如下图所示就是上图 G2 无向图的邻接表表示。

对于有向图的邻接表表示形式，图的边可以使用字典数据结构来表示。

下面给出无向图的参考代码(对于有向图，请自行修改，这里不再提示)

class Graph(object):
    def __init__(self):
        self.nodes=[] #表示图的点集
        self.edge={} #表示图的边集
    def insert(self,a,b):
        if not(a in self.nodes): #如果a 不在图的点集里，则添加a
            self.nodes.append(a)
            self.edge[a]=list()
        if not(b in self.nodes): #如果b 不在图的点集里，则添加b
            self.nodes.append(b)
            self.edge[b]=list()
        self.edge[a].append(b) #a连接b
        self.edge[b].append(a) #b连接a
    def succ(self,a):
        return self.edge[a] #返回与a连接的点
    def show_nodes(self): #返回图的点集
        return self.nodes
    def show_edge(self):
        print( self.edge)
graph = Graph()
graph.insert('0','1')
graph.insert('0','2')
graph.insert('0','3')
graph.insert('1','3')
graph.insert('2','3')
graph.show_edge()

该 graph 储存形式为：

{‘0’: [‘1’, ‘2’, ‘3’], ‘1’: [‘0’, ‘3’], ‘2’: [‘0’, ‘3’], ‘3’: [‘0’, ‘1’, ‘2’]}

邻接矩阵表示法，用两个数组表示，一个一维数组和一个二维数组。

一维数组存储节点信息，二维数组存储节点之间的关系。

通常图的遍历有两种：深度优先搜索和广度优先搜索。

深度优先搜索

深度优先搜索(DFS) 是树的先根遍历的推广，它的基本思想是：

从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。

演示：从给定图中，实现 DFS

参考代码如下：

def dfs(G,s,S=None,res=None):
    if S is None:
        # 储存已经访问节点
        S=set()
    if res is None:
        # 存储遍历顺序
        res=[]
    res.append(s)
    S.add(s)
    for u in G[s]:
        if u in S:
            continue
        S.add(u)
        dfs(G,u,S,res)

    return res

G = {'0': ['1', '2'],
     '1': ['2', '3'],
     '2': ['3', '5'],
     '3': ['4'],
     '4': [],
     '5': []}

print(dfs(G, '0'))

['0', '1', '2', '3', '4', '5']

效果如下：

广度优先搜索

广度优先搜索(BFS)是树的按层次遍历的推广，它的基本思想是：

首先访问初始点 vi，并将其标记为已访问过，接着访问 vi 的所有未被访问过的邻接点 vi1,vi2,…, vin，并均标记已访问过，然后再按照 vi1,vi2,…, vin 的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点 vi 有路径相通的顶点都被访问过为止。

演示：从给定图中，实现 BFS

参考代码如下：

def bfs(graph, start):
    explored, queue = [], [start]  #explored：已经遍历的节点列表，queue:寻找待遍历的节点队列
    explored.append(start)
    while queue:
        v = queue.pop(0) #v:将要遍历的某节点
        for w in graph[v]: #w:节点v的邻居
            if w not in explored: #w:如果w未被遍历，则遍历
                explored.append(w) #添加w节点到已遍历的节点列表
                queue.append(w) #添加w节点到寻找待遍历的节点队列
    return explored

G = {'0': ['1', '2'],
     '1': ['2', '3'],
     '2': ['3', '5'],
     '3': ['4'],
     '4': [],
     '5': []}

print(bfs(G, '0'))

结果：

['0', '1', '2', '3', '5', '4']

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。给定一个图，和一个源顶点 src，找到从 src 到其它所有所有顶点的最短路径，图中可能含有负权值的边。在这里我们介绍两种常见的求解最短路径问题的算法。

Dijkstra 的算法是一个贪婪算法，时间复杂度是 O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用，Bellman-Ford 适合这样的图。在网络路由中，该算法会被用作距离向量路由算法。

Bellman-Ford 也比迪杰斯特拉算法更简单和同时也适用于分布式系统。但 Bellman-Ford 的时间复杂度是 O(VE)，这要比迪杰斯特拉算法慢。（V 为顶点的个数，E 为边的个数）。

Dijkstra 算法

Dijkstra 算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

对下图进行 dijkstra

注意：Dijkstra 算法不能处理包含负边的图！

参考代码如下：

import heapq
def dijkstra(graph, start, end):
    heap = [(0, start)]  # cost from start node,end node
    visited = []
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.append(u)
        if u == end:
            return cost
        for v, c in G[u]:
            if v in visited:
                continue
            next = cost + c
            heapq.heappush(heap, (next, v))
    return (-1, -1)

G = {'0': [['1', 2], ['2', 5]],
     '1': [['0', 2], ['3', 3], ['4', 1]],
     '2': [['0', 5], ['5', 3]],
     '3': [['1', 3]],
     '4': [['1', 1], ['5', 3]],
     '5': [['2', 3], ['4', 3]]}
shortDistance = dijkstra(G, '4', '2')
print(shortDistance)

结果：

6

演示：从顶点 4 进行 dijkstra 找最短路径

bellman_ford 算法

含负权边的带权有向图的单源最短路问题。（不能处理带负权边的无向图）。

算法伪码如下：

procedure BellmanFord(list vertices, list edges, vertex source)

   // 该实现读入边和节点的列表，并向两个数组（distance 和 predecessor）中写入最短路径信息

   // 步骤 1：初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // 步骤 2：重复对每一条边进行松弛操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 步骤 3：检查负权环
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "图包含了负权环"

演示：从顶点 4 进行 bellman_ford 找最短路径

并查集

并查集是一种数据结构，用于处理对 N 个元素的集合划分和判断是否属于同集合的问题。让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

注：定义来自百度百科。

并查集的主要性质

用集合中的某个元素来代表这个集合，该元素称为集合的代表元。一个集合内的所有元素组织成以代表元为根的树形结构。对于每一个元素 parent[x]指向 x 在树形结构上的父亲节点。如果 x 是根节点，则令 parent[x] = x。对于查找操作，假设需要确定 x 所在的的集合，也就是确定集合的代表元。可以沿着 parent[x]不断在树形结构中向上移动，直到到达根节点。判断两个元素是否属于同一集合，只需要看他们的代表元是否相同即可。

基本功能介绍

在接下来的内容里，我们将逐步介绍并查集的具体功能是如何实现的。

创建 union_find 类

创建一个 union_find 的类,并初始化。初始化两个字典，一个保存节点的父节点，另外一个保存父节点的大小。初始化的时候，将节点的父节点设为自身，size 设为 1。

并查集的应用

1、维护无向图的连通性。支持判断两个点是否在同一连通块内，和判断增加一条边是否会产生环。

2、用在求解最小生成树的 Kruskal 算法里。

示例

根据参考的 union_find ，完成以下功能的实现

在代码中实现这些步骤：

1. 初始 a = [1,2,3,4,5],并将其添加到并查集里
2. 分别合并[1,2] [3,5] [3,1]
3. 然后判断 2 5 是否为同一个集合

class union_find(object):
    def __init__(self, data_list):
        self.father_dict = {} #保存节点的父节点
        self.size_dict = {} #保存父节点的大小
        for node in data_list:
            self.father_dict[node] = node
            self.size_dict[node] = 1
    def find(self, node):
        father = self.father_dict[node]
        if(node != father): #递归查找父节点
            father = self.find(father)
        self.father_dict[node] = father #在查找父节点的时候，顺便把当前节点移动到父节点上面这个操作算是一个优化
        return father
    def is_same_set(self, node_a, node_b):
        return self.find(node_a) == self.find(node_b)
    def union(self, node_a, node_b):
        if node_a is None or node_b is None: # 对合并的两个节点做初步判断，判断是否为空
            return

        a_head = self.find(node_a) #分别查找两个节点的父节点
        b_head = self.find(node_b)

        if(a_head != b_head): #当两个节点的父节点不一样时，才能做合并操作
            a_set_size = self.size_dict[a_head]
            b_set_size = self.size_dict[b_head]
            if(a_set_size >= b_set_size): #根据集合的大小做判断，尽量使小集合并到大集合
                self.father_dict[b_head] = a_head
                self.size_dict[a_head] = a_set_size + b_set_size
            else:
                self.father_dict[a_head] = b_head
                self.size_dict[b_head] = a_set_size + b_set_size
if __name__ == '__main__':
    a = [1,2,3,4,5]
    union_find = union_find(a)
    union_find.union(1,2)
    union_find.union(3,5)
    union_find.union(3,1)
    print(union_find.is_same_set(2,5))  # True

结果：

True

总结

由于数据结构的类型变化很多，本节仅对常见的非线性结构做了简单讲解。回顾下本节内容主要包含了以下内容：

• 树
• 字典树
• 堆
• 图
• 并查集

请把文档中所有的示例代码都手动完成并运行对比结果，只有这样才能更加熟练的掌握对应的相关知识。