|
二叉树是树形结构的一个重要类型许多实际问题抽象出来的数据结构往往是二叉树的形式即使是一般的树也能简单地转换为二叉树而且二叉树的存储结构及其算法都较为简单因此二叉树显得特别重要 二叉树的定义 二叉树的递归定义 二叉树(BinaryTree)是n(n≥)个结点的有限集它或者是空集(n=)或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成 ．二叉树的五种基本形态 二叉树可以是空集根可以有空的左子树或右子树或者左右子树皆为空 二叉树的五种基本形态如下图所示 ．二叉树不是树的特例 （）二叉树与无序树不同 二叉树中每个结点最多只能有两棵子树并且有左右之分 二叉树并非是树的特殊情形它们是两种不同的数据结构 （）二叉树与度数为的有序树不同 在有序树中虽然一个结点的孩子之间是有左右次序的但是若该结点只有一个孩子就无须区分其左右次序而在二叉树中即使是一个孩子也有左右之分 【例】下图中(a)和(b)是两棵不同的二叉树它们同右图中的普通树(作为有序树或无序树)很相似但却不等同于这棵普通树若将这三棵树均看做普通树则它们就是相同的了 二叉树并非是树的特殊情形它们是两种不同的数据结构 |
