跳到主要内容

树

简介​

树是一种数据结构，由n个有限节点组成的一个具有层次关系的集合。二叉树则是每个节点最多有两个子树的树结构。二叉树一般有以下性质：

  • 二叉树第k层上的节点数目最多为 2k−12^{k-1}
  • 深度为 h 的二叉树至多有 2h−12^{h-1} 个节点。
  • 包含 n 个节点的二叉树的高度至少为 log2(n+1)log_2(n+1)
  • 在任意一棵二叉树中，若叶子节点的个数为n0n_0，度为2的节点数为n2n_2，则n0=n2+1n_0 = n_2 + 1​

常见相关术语​

  • 根节点（root node）：位于二叉树顶层的节点，没有父节点
  • 叶节点（leaf node）：没有子节点的节点
  • 边（edge）：连接两个节点的线段
  • 节点所在的层（level）：从顶至底递增，根节点所在层为1
  • 节点的度（degree）：节点的子节点数量。在二叉树中，度的取值范围为0、1、2
  • 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量
  • 节点的深度（depth）：从根节点到该节点所经过的边的数量
  • 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

常见的二叉树​

  • 满二叉树（Perfect binary tree）。如果一棵二叉树的节点要么是叶子节点，要么它有两个子节点，那么这样的树就是满二叉树。
  • 完全二叉树（Complete binary tree）。如果一棵具有n个节点的深度为k的二叉树，它的每个节点都与深度k的满二叉树中编号为1 ~ n的节点一一对应，那么这棵二叉树被称为完全二叉树。（PS: mermaid绘图，叶子节点可能比较奇怪）
  • 平衡二叉树（balanced binary tree）。一棵空树或它的做优两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
  • 二叉搜索树。若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

示例代码​

python实现二叉树​

class Node(object):
    def __init__(self,val=None,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

class Tree(object):
    def __init__(self,node=None):
        self.root = node

    def add(self,item=None):
        node =Node(val=item)
        if not self.root or self.root.val is None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            while True:
                current_node = queue.pop(0)
                if current_node.val is None:
                    continue
                if not current_node.left:
                    current_node.left = node
                    return
                elif not current_node.right:
                    current_node.right = node
                    return
                else:
                    queue.append(current_node.left)
                    queue.append(current_node.right)

if __name__ == '__main__':
    tree = Tree()
    for i in range(10):
        if i == 3:
            i = None
        tree.add(i)