树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中：
(1) 有且仅有一个特定的称为根的结点;
(2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集合
本身 又是一棵树, 并且称为根的子树(subtree)例如,在图6.1中,(a)是只有一个根
结点的树;(b)是有 13个结点的树,其中A是根,其余结点分成三个互不相交的子树：

　　树是一种数据结构 : Tree=(D,R) 其中：D是具有相同特性的数据元素的集合；若D只含一个数据元素,则R为空集,否则R是D上 个二元关系的集合，即R={H}。H为如下描述二元关系：

• (1) 在D中存在发唯一的称为根的数据元素,它在关系H下无前驱;

• (2) 若D-{root}≠φ，则存在D-{root}的一个划分D1,D2,...Dm(m>0),对任意一对j≠k ??? (l<=j,k<=m)有Dj∩Dk=φ，且对任意的i(l<=i<=m)，唯一存在数据元素Xi∈Di，有 ∈H;

• (3) 对应于D-{root}的划分，H-{ ,..., }有唯一的一个划分H1,H2,...，Hm(m>0),对任意一对j≠k(l<=j,K<=m)有，Hj∩Hk=φ，且对任意的i(l<=i<=m)Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。

一、树的基本术语
　　　　　　　
　　 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;
　　 2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；
　　 3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
　　 4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

• 结点的度：结点拥有的子树数。

• 叶子（终端结点）：度为零的结点。

• 非终端结点（分支结点）：度不为零的结点。

• 树的度：树内各结点的度的最大值。

二、树的表示
　　 树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
　　　　 (A(B(E(K,L),F),C(G),D(H(M),I,J)))

三、树的基本操作：

(1) INITIATE(T) 初始化操作，置T为空树。

(2) ROOT(T)\ROOT(X) 求根函数。求数T的根或求结点x所在的树的根结点。若T是空树或X不在任何一棵树上，则函数值为“空”。

(3) RARENT(T,x) 求双亲函数。求树T中结点x的双亲结点。若结点x是树T的根结点或结点x不在T中，则函数值为“空”。

(4) CHILD(T,x,i) 求孩子结点函数。求数T中结点x的第i个孩子结点。若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。

(5) RIGHT_SINLING(T,x)求右兄弟函数。求树T中结点x右边的兄弟。若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函树值为“空”。

(6) CRT_TREE(x,F) 建树操作。生成一棵以X结点为根，以森F为子树森林的树。

(7) INS_CHILD(y,i,x) 插入子树操作。置以结点x为根的树为结点y的第i棵子树。若原树中无结点y或结点y的子树个数&gti-1，则空操作。

(8) DEL_CHILD(x,i) 删除子树操作。删除结点x的第i棵子树。若无结点x或结点x的子树个数&gti，则空操作。

(9) TRAVERSE(T) 遍历操作。按某个次序依此访问树中各个结点，并使每个结点只被访问一次。

(10) CLEAR(T) 清除结构操作。将树T置为空树。

四、

5.2.1 二叉树定义与基本操作

   二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 . 二叉树是一种数据结构 :

                       Binary_tree=(D,R)

其中： D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合，即 R={H}，且
(1) D 中存在唯一的称为根的元素 r，它的关系 H下无前驱 ;
(2) 若 D-{r}不等于空，则 D-{r}={Dl,Dr}，且 Dl交 Dr等于空 ;
(3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H，且存在 Dl上的关系 Hl属于 H； 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈 　　r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定义的二叉树，称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。

其中，图 6.2 是各种形态的二叉树 .

(1) 为空二叉树  　 (2)只有一个根结点的二叉树 　   (3)右子树为空的二叉树  　 (4)左子树为空的二叉树  　 (5)完全二叉树

二叉树的基本操作：

(1)INITIATE(BT ） 初始化操作。置 BT为空树。

(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。
　 若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。

(3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点
　　 或二叉树 BT中无 x结点，则函数值为 “空 ”。

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。
　　 若结点 x为叶子结点或不在二叉树 BT中，则函数值为 “空 ”。

(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。
　　 若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。

(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树
　 分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树，则插入后是结点 x的右子树。

(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。
　　 若 x无左子树或右子树，则空操作。

(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。

(10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。

5.2.2   二叉树的存储结构

一 、顺序存储结构
        连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 .

二、 链式存储结构
    由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图 6.7(c)所示。

5.3  遍历二叉树         

         遍历二叉树 (traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根 )序遍历，中 (根 )序遍历和后 (根 )序遍历。

5.3.1 前序遍历

    前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：

    按前序遍历此二叉树的结果为： Hello!How are you?

proc preorder(bt:bitreprtr)
  if (bt<>null)[
    print(bt^);
    preorder(bt^.lchild);
    preorder(bt^.rchild);]
end;

5.3.2 中序遍历

    中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：

    按中序遍历此二叉树的结果为： a*b-c

proc inorder(bt:bitreprtr)
  if (bt<>null)[
    inorder(bt^.lchild);
    print(bt^);
    niorder(bt^.rchild);]
end;

5.3.3 后序遍历

    后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：

    按后序遍历此二叉树的结果为： Welecome to use it!

proc postorder(bt:bitreprtr)
  if (bt<>null)[
    postorder(bt^.lchild);
    postorder(bt^.rchild);]
    print(bt^);
end;

五、例：
　　 1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
　　 2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。
　　 3.给出一组数据：R={10.18,3,8,12,2,7,3}，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。
　　 4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。