Python二叉树详解

二叉树是一种特殊的树,最直观地体现于它的每个节点至多有两个子节点。二叉树是非常实用的一种数据结构,常常用于实现二叉查找树及二叉堆等,使得数据的存储和搜索效率大大提高。

每个二叉树的节点至多有两棵子树,它们又分为左子树和右子树。根据这种特性,可以把二叉树的形态分为 5 种,如图 1 所示。
不同的二叉树
图 1:不同的二叉树

二叉树的性质

了解了二叉树的主要性质后,对建立和使用二叉树以及求解相关题目都十分有用。下面就介绍二叉树的几条主要性质以及它们的证明。

1) 在二叉树的第 i 层上至多有 2i-1 个节点,i ≥1

当 i=1 时,树中只有一个根节点,2i-1=20=1。每多一层,这一层的最大节点数就是前一层的两倍。比如说,第 i-1 层有 2(i-1)-1 个节点,而第 i 层有 2i-1 个节点,恰好等于第 i-1 层节点的两倍,2×2(i-1)-1=2i-1

2) 深度为 k 的二叉树中至多有 2k-1 个节点

由性质(1)可得,第 i 层上至多有 2i-1 个节点。那么,深度为 k 的树中节点数最大时即为每一层都达到最大节点数时。此时,树中节点的总数为 20+21+22+…+2k-1=2k-1(个)。

3) 非空二叉树上叶子节点的数量等于双分支节点的数量+1,即 n0=n2+1

设 n0, n1, n分别为树中度为 0, 1, 2 的节点数,此时总节点数 n=n0+n1+n2。设 B 为二叉树的分支数(分支即为连接两个节点的路径)。除根节点外,每个节点都有且仅有一条分支,所以 n =B+1。而每个分支都由度为 1 或 2 的节点发出,度为 1 的节点发出一条分支,而度为 2 的节点发出两条分支,所以 B=n1+2n2

最后,n=B+1=n1+2n2+1=n0+n1+n2,所以 n0=n2+1。

创建二叉树

二叉树有两种表示形式,一种是以列表的形式存储,所有元素的下标从 1 开始依次向后排列,编号为 i 的元素的左孩子编号为 2i,右孩子编号为 2i+1。

另一种表示形式不需要元素按顺序存储,而是在存储每个元素的同时存储左右孩子的位置。
#类的定义
class TreeNode:        
    def __init__(self, val):
        self.val = val             #二叉树的值
        self.left = None            #左孩子节点
        self.right = None            #右孩子节点

完成了类的定义后,我们开始创建这棵树:
Input = [0]                  #Input列表用于存储输入
tree = [0]                   #tree列表用于存储节点
Input = Input + input().split()
cnt = 1
for item in Input:               #将所有节点转换为treenode类型
    tmp = TreeNode(item)
    tree.append(tmp)
for item in tree:
    if item.val == "null":       #若节点为“null”,则不加入tree中
        continue
    if 2 * cnt <= len(Input) and tree[2*cnt].val != "null":  #找到每个节点的左子节点
        item.left = tree[2*cnt]
    if 2 * cnt + 1 <= len(Input) and tree[2*cnt+1].val != "null": #找到每个节点的右子节点
        item.right = tree[2*cnt+1]
    cnt += 1

输入格式应为:

1 2 3 4 5 null 6 null null 7