• 定义
• 性质
• 遍历

定义

二叉树（Binary tree）是每个节点最多只有两个分支的树结构，且分支左右次序不能随意颠倒。

在编程题中看到的二叉树通常使用Null值将其填充为完全二叉树后给出，如[1,2,3,None,4,5,None,6,7]表达的是下图的二叉树。

下面用python方式定义一个二叉树的类，并给出将上面的列表转换为二叉树的方式。

class TreeNode(object):
    """树节点类"""
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None


class BTree(object):
    """二叉树类"""
    def __init__(self,nodes=[]):
        """从列表初始化一个二叉树"""
        assert type(nodes) is list
        if not nodes:
             return None
        self.root = TreeNode(nodes[0])
        queue = [self.root]
        length = len(nodes)
        nums = 1
        while nums < length:
            node = queue.pop(0)
            if node:
                node.left = TreeNode(nodes[nums]) if nodes[nums] else None
                queue.append(node.left)
                if nums + 1 < length:
                    node.right = TreeNode(nodes[nums+1]) if nodes[nums+1] else None
                    queue.append(node.right)
                    nums += 1
                nums += 1

性质

• 第i层至多有$2^{i-1}$个节点
• 深度为k的二叉树至多有$2^k-1$个节点
• 如果叶节点数为$n_0$，为有两个子节点的节点数为$n_2$，有$n_0=n_2+1$
• 具有n个结点的完全二叉树的深度为$\lfloor{ {log}_2n}\rfloor+1$

遍历

二叉树遍历有先序遍历、中序遍历、后序遍历、层次遍历，下面是各种遍历的非递归写法。

    def MidOrder(self):
        """中序遍历"""
        valuelist = list()
        node = self.root
        stack = list()
        while(node != None or len(stack)>0):
            if node:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                valuelist.append(node.val)
                node = node.right
        return valuelist
    
    def PostOrder(self):
        """后序遍历"""
        valuelist = list()
        node = self.root
        stack1 = list()
        stack2 = list()
        stack1.append(node)
        while(len(stack1)>0):
            node = stack1.pop()
            if node.left:
                stack1.append(node.left)
            if node.right:
                stack1.append(node.right)
            stack2.append(node)
        while stack2:
            valuelist.append(stack2.pop().val)
        return valuelist
    
    def LevelOrder(self):
        """层序遍历"""
        valuelist = list()
        node = self.root
        queue = list()
        queue.append(node)
        while queue:
            node = queue.pop(0)
            valuelist.append(node.val)
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
        return valuelist

测试一下输出顺序是否正确。

B = BTree([1,2,3,None,4,5,None,6,7])

print(B.PreOrder())
print(B.MidOrder())
print(B.PostOrder())
print(B.LevelOrder())

得到的输出

[1, 2, 4, 6, 7, 3, 5]
[2, 6, 4, 7, 1, 5, 3]
[6, 7, 4, 2, 5, 3, 1]
[1, 2, 3, 4, 5, 6, 7]