树及二叉树

拼搏现实的明天。 2022-09-20 15:08 99阅读 0赞

关于数据结构部分的内容，大家可以参考该网站内容：[http://student.zjzk.cn/course\_ware/data\_structure/web/main.htm][http_student.zjzk.cn_course_ware_data_structure_web_main.htm]

**3.树的表示**  
（1）树形图表示  
　树形图表示是树结构的主要表示方法。  
树的树形图表示中：结点用圆圈表示，结点的名字写在圆圈旁边（有时亦可写在圆圈内）。  
  
 　用该定义来分析上图(a)所示的树：  
图中的树由结点的有限集T=\{A，B，C，D，E，F，C，H，I，J\}所构成，其中A是根结点，T中其余结点可分成三个互不相交的子集：  
T1=\{B，E，F，I，J\}，  
T2=\{C\}，  
T3=\{D，G，H\}。  
T1、T2和T3是根A的三棵子树，且本身又都是一棵树。例如T1，其根为B，其余结点可分为两个互不相交的的子集T11=\{E\}和T12=\{F，I，J\}，它们都是B的子树。显然T11是只含一个根结点E的树，而T12的根F又有两棵互不相交的子树\{I\}和\{J\}，其本身又都是只含一个根结点的树。  
　　  
（2）树的其他表示法  
**① 嵌套集合表示法**  
　是用集合的包含关系来描述树结构。  
上图(a)树的嵌套集合表示法如图(b)  
  
**② 凹入表表示法**  
　类似于书的目录，上图(a)树的凹入表示法如图(c)  
  
**③ 广义表表示法**  
　用广义表的形式表示的。上图(a)树的广义表表示法如图(d)  
　　（A（B（E，F（I，J）），C，D（G，H）））

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

[http_student.zjzk.cn_course_ware_data_structure_web_main.htm]: http://student.zjzk.cn/course_ware/data_structure/web/main.htm