二叉树定义

术语

• 根 ( root )，即 A ，为树中 最顶节点 ，该节点 没有父节点 ；
• A 为 B 的 父节点 ( parent )；
• E 为 B 的 子节点 ( child )；
• A 、 B 为 E 的 祖先节点 ( ancestor )；
• B 、 E 为 A 的 子孙节点 ( descendent )；
• I 、 J 互为 兄弟节点 ( sibling )， 父节点相同 ；

• 高度 ( height )，节点到最远子孙的距离；

  • A 高度为 3 ；
  • H 高度为 1 ；
  • I 高度为 0 ；

• 深度 ( Depth )，节点到根的距离；

  • A 深度为 0 ；
  • H 深度为 2 ；
  • I 高度为 3 ；

• 节点可按深度分 层 ( level )；

  • 根为第 0 层；
  • I 、 J 为第 3 层；

• H 及其全部子孙节点组成一颗 子树 ( subtree )；

满二叉树

满二叉树 ( Full Binary Tree )中，每个节点要么没有子节点( child )，要么有两个子节点。

满二叉树

完全二叉树

完全二叉树 ( Complete Binary Tree )，有以下两个性质：

1. 除了最后一层，其他所有层都是满的；
2. 最后一层节点尽可能地靠着最左边；

完全二叉树

由于完全二叉树逐层从左到右排列， 因此对于给定节点数的树， 形态只有一种 。 因此，完全二叉树可以用一个数组来表示：

完全二叉树数组表示

为每个节点编号， 根节点 为 0 ，那么编号即是节点在数组中的 下标 ：

对于节点 \(i\) ，其：

• 父节点 为： \(\frac{i - 1}{2}\) ；
• 左子节点 为： \(2i + 1\) ；
• 右子节点 为： \(2i + 2\) ；

下一步

订阅更新，获取更多学习资料，请关注我们的 微信公众号 ：

小菜学编程