算法与数据结构（五）--树【1】树与二叉树是什么

一.树的定义

树是一个具有层次结构的集合，是由一个有限集和集合上定义的一种层次结构关系构成的。不同于线性表，树并不是线性的，而是有分支的。

树（Tree）是n（n>=0）个结点的有限集。
若n=0，称为空树；
若n>0，则它满足如下两个条件：
（1）有且仅有一个特定的称为根（Root）的结点
（2）其余结点可分为m（m>=0）个互不相交的有限集T1,T2,T3,...,Tm,其实每一个集合本身又是一颗树，并称为根的子树（Sub Tree）。
显然，树的定义是一个递归的定义。

二.树的基本术语

结点：数据元素以及指向子树的分支
根结点：非空树中无前驱结点的结点
结点的度：结点拥有的子数树
树的度：树内各节点的度的最大值
叶子结点/终端节点：度=0的结点
非终端结点：根结点以外的分支结点称为内部结点

结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
兄弟：同一个双亲的结点      堂兄弟：双亲在同一层的结点
结点的祖先：从根到该结点所经分支上的所有结点。
结点的子孙：以某结点为根的子树中的任一结点。

树的深度：树中的结点的最大层次，就是说有几层。
有序树：树中结点的各子树从左至右有次序
无序树：树种结点的各子树无次序

就像这棵树，如果规定了T1，T2，T3有次序，也就是说规定T1一定要在左边，T2一定要在中间，T3一定要在右边，如果更换次序，那么就成了另一颗树。那么这种树就叫作有序树。
如果规定更换次序仍是同一棵树，那么这种树是无序树。

森林：是m（m>=0）棵互不相交的树的集合。把根结点删除树就变成了森林。
一颗树可以看成是一个特殊的森林。
给森林中的各子树加上一个双亲结点，森林就变成了树。
树一定是森林，但森林不一定是树。
 

三.二叉树的定义

为什么要重点研究每结点最多只有两个“叉”的树？
二叉树的结构简单，规律性强；可以证明，所有的树都能转为唯一对应的二叉树，不失一般性。
普通树（多叉树）若不转化为二叉树，则运算很难实现。

二叉树是n（n>=0）个结点的有限集，它或者是空集（n=0）,或者由一个根结点及两科互不相交的分别称为这个根的左子树和右子树的二叉树组成。
特点：（1）每个结点最多有俩孩子【二叉树中不存在度大于2的结点】
（2）子树有左右之分，其次序不能颠倒。
（3）二叉树可以是空集合，根可以有空的左子树或空的右子树。

注：二叉树不是树的特殊情况，它们是两个概念。
二叉树结点的子树要区分左子树和右子树，即使只有一颗子树也要进行区分，说明它是左子树，还是右子树。
树当结点只有一个孩子时，就无须区分它是左还是右的次序。因此，二者是不同的。这是二叉树与树的最主要差别。

 

注：虽然二叉树与树的概念不同，但是关于树的基本术语对二叉树都适用。

四.二叉树案例引入--利用二叉树求解表达式的值

若表达式为“第一操作数 运算符 第二操作数”的形式，则对应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身又为表达式。