【Python-AI篇】数据结构和算法
1. 算法概念
1.1 什么是数据结构
- 存储，组织数据的方式
1.2 什么是算法
- 实现业务目的的各种方法和思路
- 算法是独立的存在，只是思想，不依附于代码和程序，可以使用不同语言实现（java，python，c）
1.2.1 算法的五大特性
- 输入： 算法具有0个或多个输入
- 输出： 算法至少有1个或多个输出
- 有穷性： 算法在有限的步骤之后会自动结束循环而不会无限循环，并且每一个步骤可以在可接受的时间内完成
- 确定性： 算法中每一个步骤都有确定的含义，不会出现二义性
- 可行性： 算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
穷举法： 将问题的答案一一列举，根据判断条件判断答案是否合适
# 如果a+b+c=1000且a^2+b^2=c^2(a，b，c为自然数)，求出a, b, c所有可能的组合
import time
start_time = time.time()
for a in range(0, 1001):
for b in range(0, 1001):
for c in range(0, 1001):
if a**2 + b**2 == c**2 and a+b+c == 1000:
print("a={0}, b={1}, c={2}".format(a, b, c))
end_time = time.time()
all_time = end_time-start_time
print(all_time)
执行结果：
穷举法计算完成需要261秒
方法二：
# 如果a+b+c=1000且a^2+b^2=c^2(a，b，c为自然数)，求出a, b, c所有可能的组合
# 列举a，b，c所有可能的数值
import time
start_time = time.time()
for a in range(0, 1001):
for b in range(0, 1001):
c = 1000-a-b
if a**2 + b**2 == c**2:
print("a={0}, b={1}, c={2}".format(a, b, c))
end_time = time.time()
all_time = end_time-start_time
print(all_time)
执行结果：
方法二计算完成仅需要0.3秒
1.3 时间复杂度
1.3.1 穷举法
- 循环次数
三次循环分别为：1001次 1001次 1001次 - 每次循环的步骤
1000 = a+b+c 3次
a**2 + b**2 = c**2 5次
print打印 2次
代码总执行次数： T = 1001 * 1001 * 1001 * (5+3+2) 次
总结成时间复杂度表达式： 当问题规模为n时： T(n) = 10 * n³ - 时间复杂度表示算法随着问题规模不断变化的最主要趋势, 衡量算法的量级
- 大O计法：将次要关系全部省略掉，由最高次项表示，最终生成一个表达式：T(n) = O(n³)
1.3.2 方法二
- T(n) = O(n2)
1.3.3 时间复杂度计算规则
- 基本操作： 时间复杂度为O(1)
- 顺序结构： 时间复杂度按加法计算
- 循环结构： 时间复杂度按乘法计算
- 分支结构： 时间复杂度取最大值
- 判断算法效率： 只需要关注操作数量的最高次项，其他次要项和常数项可忽略
- 在没有特殊说明时，我们所分析的算法时间复杂度都是指最坏时间复杂度
1.3.4 常见时间复杂度
| 举例 | 时间复杂度 | 非正式术语 | ||||||
|---|---|---|---|---|---|---|---|---|
|
|
|
| ||||||
|
|
|
| ||||||
|
|
|
| ||||||
|
|
|
| ||||||
|
|
|
| ||||||
消耗时间从小到大： O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(n!)
1.4 空间复杂度
- 空间复杂度(S(n))定义该算法所消耗的存储空间，临时占用存储空间大小的度量
2. 数据结构
- 概念： 存储、组织数据的方式，相互之间存在一种或多种特定关系的数据元素的集合，往往同高效的算法有关
- 作用： 相同的数据用不同的方式也就是不同的数据结构存储，那么带来的运行或存储效率也是不同的
示例
存储方式一：列表
people1 =[{"name":"aaa", "age":18}, {"name":"bbb","age":19}]
# 查找bbb
for peo in people1:
if peo["name"] == "bbb":
print("over")
时间复杂度为：O(n)
存储方式二：字典
people1 ={{"name":"aaa", "age":18}, {"name":"bbb","age":19}}
# 查找bbb
if "bbb" in people1:
print("over")
时间复杂度为：O(1)
- 算法和数据结构的区别：
- 数据结构只是静态描述了数据元素的关系，高效的程序需要再在数据结构的基础上设计和选择算法
- 算法是为了解决实际问题而设计的，数据结构是算法需处理问题的载体
2.1 数据结构的分类
- 线性结构：表中各个节点具有线性关系(栈，队列)
- 非线性结构： 表中各个节点具有多个对应关系(树，图)
3. 顺序表
- 顺序表： 将元素顺序的放在一块连续的存储区里，元素间的关系由他们的存储顺序自然表示
- 链表： 将元素存放在通过链接构造起起来的一系列存储块中，存储区是非连续的
3.1 顺序表分类
- 一体式结构
- 分离式结构
- 无论是一体式结构还是分离式结构，在获取数据的时候直接通过下标偏移就可以找到数据所在空间的地址，而无需遍历后才可以获取地址，所以顺序表在获取地址操作的时间复杂度为：O(1)
- 顺序表完整信息：
- 数据区
- 信息区：即元素存储容量和当前表中已有元素的个数
- 顺序表的扩充
- 每次扩充增加固定数目和存储位置，如每次扩充10个位置，可称为线性增长
特点：节省空间，但扩充操作频繁，操作次数多 - 每次扩充容量加倍，如每次扩充增加一倍的存储空间
特点：减少了扩充的次数，但可能会浪费空间资源，以空间换取时间，推荐的方式
- 每次扩充增加固定数目和存储位置，如每次扩充10个位置，可称为线性增长
- 元素存储区替换：顺序表存储连续空间，如果下方扩充空间被占用，只能整体搬迁
3.2 顺序表增加删除元素
3.2.1 增加元素
- 尾端加入元素，时间复杂度为O(1)
- 非保序的加入元素（不常见），时间复杂度为O(1)
- 保序的元素加入，时间复杂度为O(n)
3.2.2 删除元素
- 尾端删除元素，时间复杂度为O(1)
- 非保序的删除元素（不常见），时间复杂度为O(1)
- 保序的元素删除，时间复杂度为O(n)
4. 链表
4.1 链表结构
- 单链表： 链表的一种形式，每个节点包含两个域，一个元素域和一个链接域，这个链接指向链表中下一个节点，而最后一个节点的链接域指向一个空值
- 表元素域elem：用来存放具体的数据
- 链接域next：用来存放下一个节点位置
- 变量head：指向链表的头结点的位置，从head出发能找到表中任意节点
# item 存放元素
# next 标识下一个节点
class SingleNode:
def __init__(self, item):
self.item = item
# 标识下一个节点
self.next = None
# 单链表实现
# head 首结点
class SingleLink:
def __init__(self, node=None):
# 首结点
self.head = node
# 结点
node1 = SingleNode(10)
print(node1.item)
print(node1.next)
# 链表
link1 = SingleLink()
print(link1.head)
link2 = SingleLink(node1)
print(link2.head)
print(link2.head.item)
4.2 链表的代码实现
---- 判空，长度，遍历，增加，删除
# 链表节点实现
# item 存放元素
# next 标识下一个节点
class SingleNode:
def __init__(self, item):
self.item = item
# 标识下一个节点
self.next = None
# 单链表实现
# head 首结点
class SingleLink:
def __init__(self, node=None):
# 首结点
self.head = node
# 判断链表是否为空
def is_empty(self):
if self.head is None:
return True
elif self.head is not None:
return False
# 获取链表的长度
def length(self):
cur = self.head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
# 遍历链表
def traverse(self):
cur = self.head
while cur is not None:
print(cur.item)
cur = cur.next
# 头部增加结点
def add(self, item):
node = SingleNode(item)
node.next = self.head
self.head = node
# 尾部增加结点
def append(self, item):
node = SingleNode(item)
# 判断是否为空链表
if self.is_empty():
self.head = node
else:
cur = self.head
# 找到尾结点
while cur.next is not None:
cur = cur.next
cur.next = node
# 指定位置增加结点
def insert(self, pos, item):
if pos <= 0:
#头部增加新结点
self.add(item)
elif pos >= self.length():
self.append(item)
else:
# 游标
cur = self.head
# 计数
count = 0
# 新结点
node = SingleNode(item)
# 找到插入位置的前一个结点
while count < pos -1:
cur = cur.next
count += 1
# 完成插入新结点
node.next = cur.next
cur.next = node
# 删除结点
def remove(self, item):
cur = self.head
pre = None
while cur is not None:
# 找到了删除元素
if cur.item == item:
# 要删除的元素在头部
if cur == self.head:
self.head = cur.next
else:
# 要删除元素不在头部
pre.next = cur.next
return
else:
# 没有找到要删除元素
pre = cur
cur = cur.next
def search(self, item):
# 游标
cur = self.head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == '__main__':
# 结点
node1 = SingleNode(10)
print(node1.item)
print(node1.next)
# 链表hy
link1 = SingleLink()
print(link1.head)
link2 = SingleLink(node1)
print(link2.head)
print(link2.head.item)
# 判空
print(link1.is_empty())
print(link2.is_empty())
# 长度
print(link1.length())
print(link2.length())
# 遍历
print(link2.traverse())
# 头部增加结点
link2.add(9)
link2.traverse()
# 尾部增加结点
link2.append(11)
link2.traverse()
# 指定位置增加结点
link2.insert(2, 7)
link2.traverse()
link2.insert(-1, 7)
link2.traverse()
link2.insert(9, 7)
link2.traverse()
# 删除结点
link2.remove(9)
link2.traverse()
# 查找结点是否存在
print(link2.search(7))
print(link2.search(9))
5. 栈
运算受限的线性表，只允许在表的一端进行插入和删除，这一端被称为栈顶，另一端被称为栈底
符合先进后出的特点
5.1 栈的作用
- 计算机系统里面CPU结构的一部分
- 局部变量在函数使用完毕后销毁，存放进栈即不浪费空间，又能及时销毁
# 使用列表封装改造为栈，尾部操作效率更高
class Stack:
"""栈"""
def __init__(self):
self.__items = []
def push(self, item):
"""进栈"""
self.__items.append(item)
def pop(self):
"""出栈"""
self.__items.pop()
def travel(self):
"""遍历"""
a = []
for item in self.__items:
a.append(item)
return a
if __name__ == '__main__':
my_stack = Stack()
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)
print('-------进栈---------')
a = my_stack.travel()
print(a)
my_stack.pop()
print('-------出栈后---------')
a = my_stack.travel()
print(a)
6. 队列
特殊的线性表，只允许在头部进行删除操作，在尾部进行添加操作，插入操作端称为队尾，删除操作称为队头
符合先进先出的特点
6.1 队列的作用
- 任务处理类系统：先把用户发送过来的请求存储在队列中，然后开启多个应用程序从队列中取任务进行处理，起到缓冲压力的作用
6.2 队列代码实现
# 使用列表封装改造成队列
# 创建一个空队列
class Queue:
def __init__(self):
self.items = []
# 队列尾部添加元素
def enqueue(self, item):
self.items.append(item)
# 队列头部删除数据
def dequeue(self):
self.items.pop(0)
# 判断队列为空
def is_empty(self):
return self.items == []
# 返回队列大小
def size(self):
return len(self.items)
def traverse(self):
item_list = []
for i in self.items:
item_list.append(i)
return item_list
if __name__ == '__main__':
print('--------进队列--------')
q = Queue()
q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
item_list = q.traverse()
print(item_list)
print('--------出队列--------')
q.dequeue()
item_list = q.traverse()
print(item_list)
is_empty = q.is_empty()
print('--------判断队列为空--------')
print(is_empty)
print('--------返回队列大小--------')
print(q.size())
6.3 双端队列
具有队列和栈的数据结构，元素可以从两端任意插入弹出，其限定插入弹出操作必须在两端进行
可以在队列任意一端入队和出队
6.4 双端队列代码实现
class Dequeue:
"""双端队列"""
def __init__(self):
self.items = []
def is_empty(self):
"""是否为空判断"""
return self.items == []
def size(self):
"""返回队列大小"""
return len(self.items)
def add(self, item):
"""头部增加数据"""
self.items.insert(0, item)
def add_last(self, item):
"""尾部添加数据"""
self.items.append(item)
def remove(self):
"""头部删除数据"""
self.items.pop(0)
def remove_last(self):
"""尾部删除数据"""
self.items.pop()
def traverse(self):
item_list = []
for item in self.items:
item_list.append(item)
return item_list
if __name__ == '__main__':
dequeue = Dequeue()
print(dequeue.is_empty())
print(dequeue.size())
print('--------头部添加数据--------')
dequeue.add(1)
dequeue.add(2)
item_list = dequeue.traverse()
print(item_list)
print('--------尾部添加数据--------')
dequeue.add_last(3)
dequeue.add_last(4)
dequeue.add_last(5)
item_list = dequeue.traverse()
print(item_list)
print('--------头部删除数据--------')
dequeue.remove()
item_list = dequeue.traverse()
print(item_list)
print('--------尾部删除数据--------')
dequeue.remove_last()
item_list = dequeue.traverse()
print(item_list)
7. 算法
排序算法稳定性：在待排序的序列中，存在多个关键字记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的，否则是不稳定的
- 不稳定的排序算法：选择排序，快速排序，希尔排序，堆排序
- 稳定的排序算法：冒泡排序，插入排序，归并排序，基数排序
7.1 冒泡排序
时间复杂度：最差：O(n2)，最优O(n)，算法稳定性：稳定
def bubble_sort(alist):
"""冒泡排序"""
# 控制比较轮数
for j in range(0, len(alist)-1):
# 计数
count = 0
# 控制每一轮的比较次数
for i in range(0, len(alist)-j-1):
# 比较相邻的两个数字，不符合要求交换位置
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count += 1
# 如果遍历一遍发现没有数字交换，退出循环，证明数列是有序的
if count == 0:
break
if __name__ == '__main__':
alist = [5, 4, 3, 2, 1]
bubble_sort(alist)
print(alist)
7.2 选择排序
工作原理：第一次从待排序的数据中选出最小或最大的元素，存放在序列的起始位置，然后再从剩余的未排序的元素中找出最小或最大的元素，然后放到已排序的序列的末尾，以此类推，直到全部待排序的数据元素个数为0
时间复杂度：最差：O(n2)，最优O(n2)，算法稳定性：不稳定
def select_sort(alist):
"""选择排序"""
# 列表的长度
n = len(alist)
# 控制比较轮数
for j in range(0, n-1):
# 假定最小值下标
min_index = j
# 控制比较次数
for i in range(j+1, n):
# 进行比较最小值
if alist[i] < alist[min_index]:
min_index = i
# 如果假定的最小值发生了变化，那么我们就进行交换
if min_index != j:
alist[min_index], alist[j] = alist[j], alist[min_index]
if __name__ == '__main__':
alist = [5, 4, 3, 2, 1]
select_sort(alist)
print(alist)
7.3 快速排序
基本思路：通过一趟排序将要排序的数据独立分割成两个部分，其中一部分的所有数据都比另一部分所有数据都要小，然后以此方法对这两部分的数据分别进行快速排序，整个排序过程可以递归执行，以此达到整个数据变成有序序列
排序流程如下：
- 首先设定一个分界值，通过分界值将数组分为左右两个部分
- 将大于或等于分界值的数据集中分布在右边，小于分界值的数据集中分布在左边，此时左边部分中各元素都小于分界值，右边部分各元素都大于等于分界值
- 左边和右边的数据可以独立排序，对于左侧数据，又可以取一个分界值，将该部分分为左右两部分，同样在左边放置最小值，右边放置最大值，右侧数据也做类似处理
- 重复上述步骤，可以看出这是一个递归定义，通过递归将左侧排好序后，再递归排好右侧部分顺序，当左右两个部分各数据排序完成后，整个数组排序也就完成了
时间复杂度：最差：O(n2)，最优O(nlogn)，算法稳定性：不稳定
def quick_sort(alist, start, end):
"""快速排序"""
# 递归结束条件
if start >= end:
return
# 界限值
mid = alist[start]
# 左右游标
left = start
right = end
while left < right:
while alist[right] >= mid and left < right:
right = right - 1
# 从右边开始找寻小于mid的值，归类到左边
alist[left] = alist[right]
# 从左边开始找寻小于mid的值，归类到右边
while alist[left] <= mid and left < right:
left = left + 1
alist[right] = alist[left]
# 循环一旦结束 证明找到了mid的值
alist[left] = mid
# 递归操作
quick_sort(alist, start, left - 1)
quick_sort(alist, right + 1, end)
if __name__ == '__main__':
alist = [10, 9, 8, 7, 7, 6, 5, 9, 3, 2, 1]
quick_sort(alist, 0, len(alist) - 1)
print(alist)
7.4 插入排序
直接将一个数据插入到已经排好序的有序的数据中，从而得到一个新的，个数加一的有序数据，算法适用于少量数据排序
组成：
- 有序的数字（默认数组的第一个数字为有序的第一部分）
- 部分无序的数字（除了第一个数字之外的数字可以认为是无序的第二部分）
时间复杂度：最差：O(n2)，最优O(n)，算法稳定性：稳定
def insert_sort(alist):
"""插入排序"""
n = len(alist)
# 控制轮数
for j in range(1, n):
# 找到合适的位置存放无序数据
for i in range(j, 0, -1):
if alist[i - 1] > alist[i]:
alist[i], alist[i - 1] = alist[i - 1], alist[i]
else:
break
if __name__ == '__main__':
alist = [10, 8, 9, 7, 5, 4, 2, 3, 1]
insert_sort(alist)
print(alist)
7.5 二分查找
折半查找，效率较高的查找方法
原理：
- 将数值分为三部分，中值前，中值和中值后
- 将要查找的值依次与中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找等于中值则返回
- 必须采用顺序表存储结构，必须按关键字大小有序排列
时间复杂度：最差：O(logn)，最优O(1)，算法稳定性：稳定
7.5.1 递归版本
def binary_search(alist, item):
"""二分查找"""
# 数列长度
n = len(alist)
# 递归结束条件
if n == 0:
return False
# 中间值
mid = n // 2
if alist[mid] == item:
return True
elif alist[mid] > item:
return binary_search(alist[:mid], item)
elif alist[mid] < item:
return binary_search(alist[mid + 1:], item)
if __name__ == '__main__':
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(my_list, 10))
print(binary_search(my_list, 11))
7.5.2 非递归版本
def binary_search(alist, item):
"""二分查找"""
# 数列长度
n = len(alist)
# 设置起始位置，获取中间值
start = 0
end = n - 1
while start <= end:
# 中间值
mid = start + end // 2
if alist[mid] == item:
return True
elif alist[mid] < item:
start = mid + 1
elif alist[mid] > item:
end = mid - 1
# 没有找到想要找的数字
return False
if __name__ == '__main__':
alist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(alist, 10))
print(binary_search(alist, 11))
8. 树
具有模拟树状结构性质的集合，它是由n(n>=1)个有限结点组成一个具有层次关系的集合，把他叫做树
- 每个节点有零个或多个子节点
- 没有父节点的节点叫做根节点
- 每一个非根节点只有一个父节点
- 除了根节点以外，每个子节点可以分为多个不相交的树
8.1 树的相关术语：
- 节点的度： 一个节点含有子节点的个数
- 树的度： 一棵树中，最大节点的度称为树的度
- 叶节点或终端节点： 度为0的节点
- 父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点
- 子节点： 一个节点含有的子树的根节点称为该节点的子节点
- 兄弟节点： 具有相同父节点的节点互称兄弟节点
- 节点层次： 从根开始定义，根为第一层，根的子节点为第二层，以此类推
- 树的高度和深度： 树种节点的最大层次
- 堂兄弟节点： 父节点的同一层节点互称为堂兄弟节点
- 节点祖先： 从根到该节点所经历分支上的所有节点
- 子孙： 以某节点为根的子树中任意节点
- 森林： 由m(m>=0)棵互不相交的树的集合
8.2 树的种类和存储
- 无序树： 树中任意节点的子节点之间没有顺序关系，也称为自由树
- 有序树： 树中任意节点的子节点之间有顺序关系
- 霍夫曼树（用于信息编码）： 带权路径最短的二叉树称为霍夫曼树或最优二叉树
- B树： 一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个的子树
- 二叉树： 每个节点最多含有两个子树
- 完全二叉树： 对于一颗二叉树，假设其深度为d(d>1)，除了第d层之外，其他各层的节点数目均已达到最大值，且d层所有节点从左到右连续的紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的二叉树
- 平衡二叉树（AVL树）： 当且仅当任何节点的两颗子树的高度差不大于1的二叉树
- 排序二叉树(二叉搜索树、有序二叉树)： 要求：①若左子树不空，则左子树上所有节点的值均小于它的根节点的值；②若右子树不空，则右子树上所有节点的值均大于根节点的值；③左右子树分别也为排序二叉树；④排序二叉树包含空树；
8.3 二叉树的存储
- 顺序存储： 将数据结构存储在固定的数组中，虽然遍历上有优势，但是所占空间大，是非主流的二叉树存储方式
- 链式存储： 由于对节点的个数无法掌握，常见的树的存储表示都转换成二叉树进行处理，子节点最多个数为2，主流二叉树存储方式（指针域个数不定）
8.4 树的应用场景
- xml、html等，编写这些东西的解析器的时候，不可避免的需要用到树
- 路由协议就是使用了树的算法
- mysql数据索引
- 文件系统的目录结构
- 很多经典的AI算法都是树搜索，机器学习中的decision tree也是树结构
8.5 二叉树的性质
- 在二叉树上的第i层上至多有2i-1个节点(i>0)
- 深度为k的二叉树至多有2k-1个节点(k>0)
- 对于任意一颗二叉树，如果其子叶节点数为N0，而度数为2的节点总数为N2，则N0 = N2 + 1
- 最多有n个节点的完全二叉树的深度必为log2(n+1)
- 对于完全二叉树，若从上到下，从左到右编号，则编号为i的节点，其左孩子编号必定为2i，右孩子编号必为2i+1，其父节点的编号必为i//2 (i=1时为根，除外)
8.6 二叉树的遍历
- 广度优先遍历： 可以找到最短路径
- 深度优先遍历：
8.6.1 广度优先遍历
class Node(object):
"""节点类"""
def __init__(self, item):
self.item = item
self.lchild = None
self.rchild = None
class BinaryTree(object):
"""完全二叉树"""
def __init__(self, node=None):
self.root = node
def add(self, item):
"""添加节点"""
if self.root is None:
self.root = Node(item)
# 队列
queue = []
# 从尾部添加数据
queue.append(self.root)
while True:
# 从头部取出数据
node = queue.pop(0)
# 判断左右子树是否为空
if node.lchild is None:
node.lchild = Node(item)
return
else:
queue.append(node.lchild)
if node.rchild is None:
node.rchild = Node(item)
return
else:
queue.append(node.rchild)
def breath_traversal(self):
"""广度优先遍历"""
if self.root is None:
return
# 队列
queue = []
tree_list = []
# 添加数据
queue.append(self.root)
while len(queue)>0:
# 取出数据
node = queue.pop(0)
print(node.item)
tree_list.append(node.item)
# 判断左右子节点是否为空
if node.lchild is not None:
queue.append(node.lchild)
if node.rchild is not None:
queue.append(node.rchild)
return tree_list
if __name__ == '__main__':
tree = BinaryTree()
tree.add('a')
tree.add('b')
tree.add('c')
tree.add('d')
tree.add('e')
tree.add('f')
tree.add('g')
tree.add('h')
tree.add('i')
tree.add('j')
tree.add('k')
tree_list = tree.breath_traversal()
print(tree_list)
8.6.2 深度优先遍历
- 先序优先遍历： 根 左 右
- 中序优先遍历： 左 根 右
- 后序优先遍历： 左 右 根
class Node(object):
"""节点类"""
def __init__(self, item):
self.item = item
self.lchild = None
self.rchild = None
class BinaryTree(object):
"""完全二叉树"""
def __init__(self, node=None):
self.root = node
def add(self, item):
"""添加节点"""
if self.root is None:
self.root = Node(item)
# 队列
queue = []
# 从尾部添加数据
queue.append(self.root)
while True:
# 从头部取出数据
node = queue.pop(0)
# 判断左右子树是否为空
if node.lchild is None:
node.lchild = Node(item)
return
else:
queue.append(node.lchild)
if node.rchild is None:
node.rchild = Node(item)
return
else:
queue.append(node.rchild)
def breath_traversal(self):
"""广度优先遍历"""
if self.root is None:
return
# 队列
queue = []
tree_list = []
# 添加数据
queue.append(self.root)
while len(queue)>0:
# 取出数据
node = queue.pop(0)
print(node.item)
tree_list.append(node.item)
# 判断左右子节点是否为空
if node.lchild is not None:
queue.append(node.lchild)
if node.rchild is not None:
queue.append(node.rchild)
return tree_list
def preorder_traversal(self, root=None):
"""先序遍历"""
if root is not None:
print(root.item, end='')
self.preorder_traversal(root.lchild)
self.preorder_traversal(root.rchild)
def inorder_traversal(self, root=None):
"""中序遍历"""
if root is not None:
self.inorder_traversal(root.lchild)
print(root.item, end='')
self.inorder_traversal(root.rchild)
def postorder_traversal(self, root=None):
"""后序遍历"""
if root is not None:
self.postorder_traversal(root.lchild)
self.postorder_traversal(root.rchild)
print(root.item, end='')
if __name__ == '__main__':
tree = BinaryTree()
tree.add('a')
tree.add('b')
tree.add('c')
tree.add('d')
tree.add('e')
tree.add('f')
tree.add('g')
tree.add('h')
tree.add('i')
tree.add('j')
tree.add('k')
tree.preorder_traversal(tree.root)
tree.inorder_traversal(tree.root)
tree.postorder_traversal(tree.root)