算法之树结构（Python）

1. 树的相关术语及定义

树是一种基本的“非线性”数据结构。跟自然界中的树一样， 数据结构树也分为：根、 枝和叶等三个部分。一般数据结构的图示把根放在上方，叶放在下方。

1.1 树的相关术语

1.2 定义

树由若干节点， 以及两两连接节点的边组成， 并有如下性质：

• 其中一个节点被设定为根；
• 每个节点n(除根节点)，都恰连接一条来自节点p的边， p是n的父节点；
• 每个节点从根开始的路径是唯一的，如果每个节点最多有两个子节点，这样的树称为“二叉树”

2. 二叉树

这篇文章主要的研究对象就是二叉树

2.1 二叉树的基本性质

二叉树（Binary Tree） 是一种特殊的树型结构，它的特点是每个结点至多有两棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。

根据二叉树的定义，其具有下列重要性质：

1. 在二叉树的第层上至多有个结点。
2. 深度为的二叉树至多有个结点。
3. 对任何一棵二叉树，如果其叶子节点数为,度为2的结点数为，则。
4. 具有个结点的完全二叉树的深度为,其中表示不大于x的最大整数。
5. 对完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲的编号必为i/2(i=1时为根，除外)

2.1 二叉树的实现及遍历

2.1.1 二叉树的实现

# 二叉树类
class TreeNode(object):
    # 初始化
    def __init__(self, val=None, left=None, right=None):
        self.val = val    # 数据域
        self.left = left    # 左子树
        self.right = right  # 右子树
    # 添加节点
    def add_node(self,root = None,item):
        # 创建节点对象
        node = BTree(item)
        if not root:
            root = node
            return 
        queue = []
        queue.append(root) # 如果根节点存在，添加根节点
        while queue:  # 该循环是为了找出新节点添加的位置
            node_data = queue.pop(0) # 取出节点
            if node_data.left == None : # 如果该节点左孩子为空，添加新节点为该节点左孩子
                node_data.left = node
                return
            elif node_data.right == Node: # 如果该节点右孩子为空，添加新节点为该节点右孩子
                node.data.right = node
                ruturn
            else： # 如果都不为空，则继续向下寻找
                queue.append(node_data.left)
                queue.append(node.data.right)
复制代码

2.1.2 二叉树的遍历

二叉树的两种重要的遍历模式是深度优先遍历和广度优先遍历：

1. 深度优先遍历：沿着树的深度遍历树的结点，尽可能深的搜索树的分支。

# 深度优先又分为三种：先序遍历、中序遍历、后序遍历。它们的区别在于输出的先后顺序不同。

#先序遍历
def p(tree):
    if tree == None:
        return
    print(tree.val,end=" ")
    p(tree=tree.left)
    p(tree=tree.right)
    
#中序遍历
def m(tree):
    if tree == None:
        return
    m(tree=tree.left)
    print(tree.val,end=" ")
    m(tree=tree.right)
    
# 后序遍历
def e(tree):
    if tree == None:
        return
    e(tree=tree.left)
    e(tree=tree.right)
    print(tree.val,end=" ")
    
 
"""
构建一个二叉树:
       _3
      /  \ 
     9   _20
        /   \
       15    7
"""
root = TreeNode(3)
root_l = TreeNode(9)
root_r = TreeNode(20)
root.left = root_l
root.right = root_r
root_r_l = TreeNode(15)
root_r_r = TreeNode(7)
root_r.left = root_r_l
root_r.right = root_r_r
# 分别打印先序、中序、后序遍历结果
print("先序:" ,end="")
p(tree=root)
print("中序:" ,end="")
m(tree=root)
print("后序:" ,end="")
e(tree=root)
# 先序:3 9 20 15 7 中序:9 3 15 20 7 后序:9 15 7 20 3
复制代码

2. 广度优先遍历：沿着树的度遍历树的节点，即一层一层遍历。

def b(tree):
    if not tree:
        return None
    queue = [tree] # 根节点不为空，添加根节点
    while queue:
        node = queue.pop(0)
        print(node.val,end=" ")
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

"""
构建一个二叉树:
       _3
      /  \ 
     9   _20
        /   \
       15    7
"""
root = TreeNode(3)
root_l = TreeNode(9)
root_r = TreeNode(20)
root.left = root_l
root.right = root_r
root_r_l = TreeNode(15)
root_r_r = TreeNode(7)
root_r.left = root_r_l
root_r.right = root_r_r
# 打印 广度优先遍历结果
print("广度优先：",end="")
b(tree=root)
# 广度优先：3 9 20 15 7



# 拓展：二叉树的层序遍历（体现层级）
def levelOrder(tree):
    queue = []
    result = []
    if not tree:
        return []
    else:
        queue.append(tree)
    while queue:
        data = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            data.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(data)
    return result
   
# 用上面的实例运行出的结果为：[[3], [20, 9], [7, 15]]
复制代码

以上就是关于树结构简单的介绍，主要还是要理解二叉树的实现以及遍历。