树结构依靠节点、叶子节点、子树将自身的数据扩展为像一棵倒过来的树
树结构
1. 什么是树结构
树结构依托路径、节点、叶子节点将自身的数据结构展现得就行一棵倒过来的树一样，因此称之为树结构。
- 根节点(root): 树的最上层的节点，任何非空的树都有一个节点
- 路径(path): 从起始节点到终止节点经历过的边
- 父亲(parent)：除了根节点，每个节点的上一层边连接的节点就是它的父亲(节点)
- 孩子(children): 每个节点由边指向的下一层节点
- 兄弟(siblings): 同一个父亲并且处在同一层的节点
- 子树(subtree): 每个节点包含它所有的后代组成的子树
- 叶子节点(leaf node): 没有孩子的节点成为叶子节点
2. 二叉树
二叉树属于树的一种分类，是简单且较为常用的一种树结构，它的每个节点最多包含两个孩子。
2.1 满二叉树
每个非叶子节点都有两个孩子称之为满二叉树
2.2 完美二叉树
从根节点到叶子节点，每一层都是满二叉树结构
2.3 完全二叉树
除了叶子节点一层外，剩余的层是完美二叉树
2.4 二叉查找树
应用二叉树的结构，对数据按照左边大（小）右边小（大）的结构进行分布。
2.5 一些概念
节点深度(depth): 节点对应的 level 数字
树的高度(height): 二叉树的高度就是 level 数 + 1，因为 level 从 0开始计算的
树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数
树的 size：二叉树的节点总个数。
2.6 二叉树的表示
可以直接利用数组依照层级关系从上（根节点）到下（叶子节点），每一层按照从左到右的方式进行数组展示。
二叉树的数组表示
3. 代码
3.1 树结构
树结构的实现方式和双链式结构的实现方式类似，在节点上添加左右指向。
node_list = [
{'data': 'A', 'left': 'B', 'right': 'C', 'is_root': True},
{'data': 'B', 'left': 'D', 'right': 'E', 'is_root': False},
{'data': 'D', 'left': None, 'right': None, 'is_root': False},
{'data': 'E', 'left': 'H', 'right': None, 'is_root': False},
{'data': 'H', 'left': None, 'right': None, 'is_root': False},
{'data': 'C', 'left': 'F', 'right': 'G', 'is_root': False},
{'data': 'F', 'left': None, 'right': None, 'is_root': False},
{'data': 'G', 'left': 'I', 'right': 'J', 'is_root': False},
{'data': 'I', 'left': None, 'right': None, 'is_root': False},
{'data': 'J', 'left': None, 'right': None, 'is_root': False},
]
class Node:
def __init__(self, data, left=None, right=None):
self.data, self.right, self.left = data, right, left
class Tree:
def __init__(self, root=None):
self.root = root
# 数据解析
def init_data(self, datas):
node_dict = {}
for data in datas:
node = Node(data['data'], data['left'], data['right'])
node_dict[data['data']] = node
for data in datas:
node = node_dict[data['data']]
if node.left:
node.left = node_dict[node.left]
if node.right:
node.right = node_dict[node.right]
if data['is_root']:
self.root = node
3.2 二叉查找树
node_list = [
{'data': 60, 'left': 12, 'right': 90, 'is_root': True},
{'data': 12, 'left': 4, 'right': 41, 'is_root': False},
{'data': 4, 'left': 1, 'right': None, 'is_root': False},
{'data': 1, 'left': None, 'right': None, 'is_root': False},
{'data': 41, 'left': 29, 'right': None, 'is_root': False},
{'data': 29, 'left': 23, 'right': 37, 'is_root': False},
{'data': 23, 'left': None, 'right': None, 'is_root': False},
{'data': 37, 'left': None, 'right': None, 'is_root': False},
{'data': 90, 'left': 71, 'right': 100, 'is_root': False},
{'data': 71, 'left': None, 'right': 84, 'is_root': False},
{'data': 100, 'left': None, 'right': None, 'is_root': False},
{'data': 84, 'left': None, 'right': None, 'is_root': False},
]
class Node:
def __init__(self, data, left=None, right=None):
self.data, self.right, self.left = data, right, left
def __str__(self):
return '数据是：{}'.format(self.data)
class Tree:
def __init__(self, root=None):
self.root = root
def init_data(self, datas):
node_dict = {}
for data in datas:
node = Node(data['data'], data['left'], data['right'])
node_dict[data['data']] = node
for data in datas:
node = node_dict[data['data']]
if node.left:
node.left = node_dict[node.left]
if node.right:
node.right = node_dict[node.right]
if data['is_root']:
self.root = node
# 通过递归查找某个值
def search(self, subtree, value):
if subtree is None:
return None
elif subtree.data > value:
return self.search(subtree.left, value)
elif subtree.data < value:
return self.search(subtree.right, value)
else:
return subtree
# 获取二叉查找树的最小值
def get_min(self, subtree):
if subtree is None:
return None
elif subtree.left is None:
return subtree
else:
return self.get_min(subtree.left)
def insert_data(self, subtree, value):
if subtree is None:
subtree = Node(value)
elif subtree.data > value:
subtree.left = self.insert_data(subtree.left, value)
else:
subtree.right = self.insert_data(subtree.right, value)
return subtree
def add(self, value):
# 查找数据 是否已存在
node = self.search(self.root, value)
if node:
return False
else:
self.root = self.insert_data(self.root, value)
return True
# 利用递归删除节点，并清理关系
def remove_node(self, subtree, value):
if subtree is None:
return None
elif subtree.data > value:
subtree.left = self.remove_node(subtree.left, value)
return subtree
elif subtree.data < value:
subtree.right = self.remove_node(subtree.right, value)
else:
# 找到数据节点 ： 1，2，3
if subtree.left is None and subtree.right is None:
return None
elif subtree.left is None or subtree.right is None:
if subtree.left is not None:
return subtree.left
else:
return subtree.right
else:
node = self.get_min(subtree.right)
subtree.data = node.data
subtree.right = self.remove_node(subtree.right, node.data)
return subtree
def remove(self, value):
# 判断树中是否包含要删除的数据
if self.search(self.root, value):
self.remove_node(self.root, value)
return True
return False
