首页 > 代码库 > 第十章 基本数据结构——二叉树

第十章 基本数据结构——二叉树

摘要

  书中第10章10.4小节介绍了有根树,简单介绍了二叉树和分支数目无限制的有根树的存储结构,而没有关于二叉树的遍历过程。为此对二叉树做个简单的总结,介绍一下二叉树基本概念、性质、二叉树的存储结构和遍历过程,主要包括先根遍历、中根遍历、后根遍历和层次遍历。

1、二叉树的定义

  二叉树(Binary Tree)是一种特殊的树型结构,每个节点至多有两棵子树,且二叉树的子树有左右之分,次序不能颠倒。

  由定义可知,二叉树中不存在度(结点拥有的子树数目)大于2的节点。二叉树形状如下下图所示:

2、二叉树的性质

(1)在二叉树中的第i层上至多有2^(i-1)个结点(i>=1)。备注:^表示此方

(2)深度为k的二叉树至多有2^k-1个节点(k>=1)。

(3)对任何一棵二叉树T,如果其终端结点数目为n0,度为2的节点数目为n2,则n0=n2+1。

满二叉树:深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。

完全二叉树:深度为k具有n个结点的二叉树,当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。

可以得到一般结论:满二叉树和完全二叉树是两种特殊形态的二叉树,满二叉树肯定是完全二叉树,但完全二叉树不不一定是满二叉树。

举例如下图是所示:

(4)具有n个节点的完全二叉树的深度为log2n + 1。

3、二叉树的存储结构

  可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法,因为其非常灵活,方便二叉树的操作。二叉树的二叉链表存储结构如下所示:

第十章 基本数据结构——二叉树