Python之数据结构--树形结构
树形结构
基础概念
1. 定义
树（Tree）是n（n≥0）个节点的有限集合T，它满⾜两个条件：有且仅有⼀个特定的称为根（Root）的节点；其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每⼀个集合⼜是⼀棵树，并称为其根的⼦树（Subtree）。
2. 基本概念
⼀个节点的⼦树的个数称为该节点的度数，⼀棵树的度数是指该树中节点的最⼤度数。
度数为零的节点称为树叶或终端节点，度数不为零的节点称为分⽀节点。
二叉树公式⼀个节点的⼦树之根节点称为该节点的⼦节点，该节点称为它们的⽗节点，同⼀节点的各个
⼦节点之间称为兄弟节点。⼀棵树的根节点没有⽗节点，叶节点没有⼦节点。
节点的层数等于⽗节点的层数加⼀，根节点的层数定义为⼀。树中节点层数的最⼤值称为该树的⾼度或深度。
⼆叉树
1. 定义
⼆叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由⼀个根节点以及两棵互不相交的、分别称为左⼦树和右⼦树的⼆叉树组成。⼆叉树与普通有序树不同，⼆叉树严格区分左孩⼦和右孩⼦，即使只有⼀个⼦节点也要区分左右。
2. 特征
⼆叉树第i（i≥1）层上的节点最多为个。
深度为k（k≥1）的⼆叉树最多有 个节点。
在任意⼀棵⼆叉树中，树叶的数⽬⽐度数为2的节点的数⽬多⼀。
满⼆叉树 ：深度为k（k≥1）时有 个节点的⼆叉树。
⼆叉树的遍历
遍历 ：沿某条搜索路径周游⼆叉树，对树中的每⼀个节点访问⼀次且仅访问⼀次。
先序遍历： 先访问树根，再访问左⼦树，最后访问右⼦树；
中序遍历： 先访问左⼦树，再访问树根，最后访问右⼦树；
后序遍历： 先访问左⼦树，再访问右⼦树，最后访问树根；
层次遍历: 从根节点开始，逐层从左向右进⾏遍历。
例如：
先序遍历结果：A B D E G H C F
中序遍历结果：D B G H E A C F
后序遍历结果：D H G E B F C A
层次遍历结果：A B C D E F G H
递归思想和实践
1. 什么是递归？
所谓递归函数是指⼀个函数的函数体中直接调⽤或间接调⽤了该函数⾃⾝的函数。这⾥的直接调⽤是指⼀个函数的函数体中含有调⽤⾃⾝的语句，间接调⽤是指⼀个函数在函数体⾥有调⽤了其它函数，⽽其它函数⼜反过来调⽤了该函数的情况。
2. 执⾏过程
递推阶段：从原问题出发，按递归公式递推从未知到已知，最终达到递归终⽌条件。
回归阶段：按递归终⽌条件求出结果，逆向逐步代⼊递归公式，回归到原问题求解。
3. 优点与缺点
优点：递归可以把问题简单化，让思路更为清晰，代码更简洁
缺点：递归因系统环境影响⼤，当递归深度太⼤时，可能会得到不可预知的结果
⽰例：
"""
求⼀个数n的阶乘
"""
# 递归函数
def recursion(n):
# 递归的终⽌条件
if n <= 1:
return 1
return n * recursion(n - 1)
print(recursion(3))
# 3 * 2 * 1 = 6
⼆叉树的代码实现
⼆叉树顺序存储
⼆叉树本⾝是⼀种递归结构，可以使⽤Python list 进⾏存储。但是如果⼆叉树的结构⽐较稀疏的话浪费的空间是⽐较多的。                空结点⽤None表⽰
⾮空⼆叉树⽤包含三个元素的列表[d,l,r]表⽰，其中d表⽰根结点，l，r左⼦树和右⼦树。
⼆叉树链式存储
⽰例：
"""
链式存储⼆叉树
"""
class TreeNode:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.left = left
self.right = right
class BiTree:
def __init__(self, root=None):
< = root
def is_empty(self):
is None
# 先序遍历
def pre_order(self, node):
if node is None:
return
print(node.data, end=" ")
self.pre_order(node.left)
self.pre_order(node.right)
# 中序遍历
def mid_order(self, node):
if node is None:
return
self.mid_order(node.left)
print(node.data, end=" ")
self.mid_order(node.right)
# 后序遍历
def post_order(self, node):
if node is None:
return
self.mid_order(node.left)
self.mid_order(node.right)
print(node.data, end=" ")
# 层次排序
@staticmethod
def tier_order(node):
queue = [node]
while queue:
temp = queue.pop(0)
print(temp.data, end=' ')
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
if __name__ == '__main__':
d = TreeNode('D')
e = TreeNode('E')
f = TreeNode('F')
g = TreeNode('G')
b = TreeNode('B', d, e)
c = TreeNode('C', f, g)
a = TreeNode('A', b, c)
tree = BiTree(a)
tree.pre_)  # A B D E C F G    tree.mid_)  # D B E A F C G    tree.post_)  # D B E F C G A    tree.tier_)  # A B C D E F G