二叉树基本概念：Python 描述

#二叉树 #数据结构

目录

1. 定义

# 二叉树的节点定义
class TreeNode:
    def __init__(self, val: int):
        self.val = x
        self.left = None
        self.right = None

# 你可以这样构建一棵二叉树：
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)

# 构建出来的二叉树是这样的：
#     1
#    / \
#   2   3
#  /   / \
# 4   5   6

图片

2. 常见术语

图片

3. 完美二叉树：满二叉树

图片

4. 完全二叉树：只有最底层没被填满

图片

这里着重说下完全二叉树：

  • 叶子节点都在 最底下两层
  • 最后一层叶子节都靠左排列
  • 并且除了最后一层，其他层的节点个数都要达到最大

5. 完满二叉树

完满二叉树（full binary tree）除了叶节点之外，其余所有节点都有两个子节点。

图片

6. 平衡二叉树

平衡二叉树（balanced binary tree）中任意节点的左子树和右子树的高度之差的绝对值不超过 1

图片

二叉树中任意一个节点的左右子树的高度相差不能大于 1

|568

7. 二叉树的退化 → 单链表

图片

图片