一、二叉树
根节点：树上的节点
左叶子节点
右叶子节点
子树
- 完整的子树
- 一个根节点，左右叶子节点组成
- 不完整的子树
- 根节点：左叶子节点
- 根节点：右叶子节点
- 根节点：
- 特点：每一个节点都可以作为某一棵子树的根节点
class Node:
def __init__(self, item):
self.item = item
self.left = None # 指向该节点的左叶子节点
self.right = None # 指向该节点的右叶子节点
class Tree:
def __init__(self): # 构建一棵空树
self.root = None # 永远指向二叉树中的根节点
def insert(self, item): # 添加节点
node = Node(item)
# 如果是个空树
if self.root is None:
self.root = node
return
# 如果树不是空树
cur = self.root
q = [cur] # 将根节点放入列表中
while True:
n = q.pop(0) # 取出列表中的节点判断它的左右两个子节点是否为空
if n.left is not None:
q.append(n.left) # 如果左子节点不为空就把它当做下一个主节点放入列表中
else:
n.left = node # 如果左子节点为空就把加入的新节点插入
break
if n.right is not None:
q.append(n.right) # 同上判断右节点
else:
n.right = node
break
def travel(self): # 查看所有节点
cur = self.root
q = [cur]
while q:
n = q.pop(0)
print(n.item)
if n.left is not None:
q.append(n.left)
if n.right is not None:
q.append(n.right)
tree = Tree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.travel()
# 输出
1
2
3
4
5
6
二、二叉树的遍历
广度遍历：横向遍历
- 上述代码中的遍历就是广度遍历。自上到下逐行遍历叫做广度遍历。
深度遍历：纵向遍历。前中后序遍历形式需要作用到子树中，前中后序的前中后指的是子树中根节点的位置。
- 前序：根左右——>先遍历子树的根节点，在遍历子树的左节点然后是右节点
- 中序：左根右
- 后续：左右根
深度遍历的实现思路：
- 深度遍历是需要作用到每一棵子树中
- 子树和子树之间的区别体现在跟节点中
- 如果写一个函数，该函数可以将一个子树中的节点进行遍历，则将改函数作用到其他子树中就可以将整棵树进行深度遍历
class Node:
def __init__(self, item):
self.item = item
self.left = None # 指向该节点的左叶子节点
self.right = None # 指向该节点的右叶子节点
class Tree:
def __init__(self): # 构建一棵空树
self.root = None # 永远指向二叉树中的根节点
def insert(self, item): # 添加节点
node = Node(item)
# 如果是个空树
if self.root is None:
self.root = node
return
# 如果树不是空树
cur = self.root
q = [cur] # 将根节点放入列表中
while True:
n = q.pop(0) # 取出列表中的节点判断它的左右两个子节点是否为空
if n.left is not None:
q.append(n.left) # 如果左子节点不为空就把它当做下一个主节点放入列表中
else:
n.left = node # 如果左子节点为空就把加入的新节点插入
break
if n.right is not None:
q.append(n.right) # 同上判断右节点
else:
n.right = node
break
# 查看所有节点
def travel(self):
cur = self.root
q = [cur]
while q:
n = q.pop(0)
print(n.item)
if n.left is not None:
q.append(n.left)
if n.right is not None:
q.append(n.right)
# 前序遍历
# 参数root表示的是子树的根节点，需要给递归调用的forward传入不同子树的根节点
def forward(self, root):
if root is None: # 直到传入的节点为空才停止递归
return
print(root.item)
self.forward(root.left)
self.forward(root.right)
# 中序遍历
def middle(self, root): # 左跟右
if root is None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)
# 后续遍历
def back(self, root): # 左右根
if root is None:
return
self.back(root.left)
self.back(root.right)
print(root.item)
tree = Tree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.insert(7)
tree.forward(tree.root)
# 输出
1
2
4
5
3
6
7
三、排序二叉树
排序二叉树就是在二叉树插入数据的时候，和根节点做对比，大于根节点就插入右侧，小于就插入左侧，右侧或左侧有就和对应节点做对比，再次判断插入数据。
class Node:
def __init__(self, item):
self.item = item
self.left = None # 指向该节点的左叶子节点
self.right = None # 指向该节点的右叶子节点
class SortTree:
def __init__(self): # 构建一棵空树
self.root = None # 永远指向二叉树中的根节点
def insert(self, item): # 添加节点
node = Node(item)
if self.root is None: # 树为空的情况
self.root = node
return
cur = self.root
while True: # 循环开始从根节点开始
if cur.item > item: # 插入的值小于根节点，该节点需要插入到根节点的左侧
if cur.left is None:
cur.left = node
break # 插入即退出
else: # 左节点不为空，那么就再次循环从左节点开始
cur = cur.left
else:
if cur.right is None: # 插入的值大于根节点，就插入该节点右侧
cur.right = node
break
else:
cur = cur.right # 同上，不为空再次从此节点循环
# 中序遍历
def middle(self, root): # 左跟右
if root is None:
return
self.middle(root.left)
print(root.item)
self.middle(root.right)
alist = [3, 8, 5, 4, 7, 6, 2, 1]
tree = SortTree()
for item in alist:
tree.insert(item)
tree.middle(tree.root)
# 输出
1
2
3
4
5
6
7
8