树：树（Tree）是n(n≤0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为的根的子树（SubTree）。

1、n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树只能有一个根结点。

2、m>0时，子树的个数没有限制，但它们一定互不相交。

---

结点分类：

        结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

        结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度（Depth）或高度，下图所示的树的深度为4。

         如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

        森林（Forest）是m（m≥0）棵互不相交的树的集合。

线性结构与树结构的特征

线性结构	树结构
第一个数据元素：无前驱	根结点：无双亲，唯一
最后一个数据元素：无后继	叶结点：无孩子，可以多个
中间元素：一个前驱一个后继	中间结点：一个双亲多个孩子

---

树的抽象数据类型

ADT 树（tree）
Data树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
OperationInitTree(*T)构造空树T.DestoryTree(*T)销毁树T。CreateTree(*T,definition):按definition中给出树的定义来构造树。ClearTree(*T):若树T存在，则将树T清空TreeEmpty(T):若T为空树，返回True，否则false。TreeDepth(T):返回T的深度Root(T):返回T的根结点。Value(T,cur_e):cur_e是树T中的一个结点，返回该结点的值Assign(T,cur_e,value):给树T的cur_e结点赋值valueParent(T,cur_e):若cur_e是树T的非根结点，则返回它的双亲，否则返回空。LeftChild(T,cur_e):若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空。RightSibling(T,cur_e):若cur_e由有右兄弟，则返回它的右兄弟，否则返回空。InsertChild(*T,*p,i,c):其中p指向树T的某个结点，i为所指结点p的度加上1，非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。DeleteChild（*T,*p,i）:其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i棵子树。endADT

---

树的存储结构

双亲表示法：在每个结点中，附设一个指示器指示双亲结点到链表中的位置。

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;    /*树结点的数据类型，目前暂定为整型。
typedef struct PTNode    /*结点结构*/
{TElemType data;    /*结点数据*/int parent;    /*双亲位置*/
}PTNode;
typedef struct        /*树结构*/
{PTNode nodes[MAX_TREE_SIZE]; /*结点数组*/int r，n;
}PTree;

        

         这样的存储结构，我们可以根据结点的parents指针很容易找到它的双亲结点，所用的时间复杂度为O(1),直到parent为-1为止，表示找到了树结点的根。可是如果我们要知道结点的孩子是什么，我们需要遍历整个结构（缺点）。

         此外还可将此结构扩展为双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等。

孩子表示法：

        把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如下图：

         为此书中提到两种结构，一个是孩子链表的孩子结点，其中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向某结点的下一个孩子结点的指针。

         另一个是表头数组的表头结点，其中data是数据域，存储结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针。

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef struct CTNode /*孩子结点*/
{int child;struct CTNode *next;
}*ChildPtr;typedef struct /*表头结构*/
{TElemType data;ChildPtr firstchild;
} CTBox;typedef struct    /*树结构*/
{CTBox nodes[MAX_TREE_SIZE];    /*结点数组*/int r,n;                    /*根的位置和结点数*/
}CTree;

---

        二叉树的定义

        二叉树（Binary Tree）是n(n≥0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点：

        1、每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。

        2、左子树和右子树是有顺序的，次序不能任意颠倒。

        3、即使树中某结点只有一棵树，也要区分它是左子树还是右子树。 

二叉树具有五种基本形态：

        1、空二叉树

        2、只有一个根结点

        3、根结点只有左子树

        4、根结点只有右子树

        5、根结点既有左子树又有右子树

---

特殊的二叉树：

        1、斜树

        所有的结点都只有左节点的二叉树叫左斜树。所有结点都只是右子树的二叉树叫右斜树。二者统称为斜树胡。

        2、满二叉树

        在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

         满二叉树的特点：

                1、叶子只能出现在最下一层。出现在其他层就不可能达到平衡。

                2、非叶子节点的度一定是2。

                3、在同样深度的二叉树中 ，满二叉树的结点个数最多，叶子数最多。

        3、完全二叉树

        对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

        满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

        完全二叉树的特点：

                1、叶子结点只能出现在最下两层。

                2、最下层的叶子一定集中在左部连续位置。

                3、倒数二层，若有叶子结点，一定都在右部连续位置。

                4、如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。

                5、同样结点数的二叉树，完全二叉树的深度最小。

---

二叉树的性质

性质1：在二叉树的第i层上至多有个结点（i≥1）

性质2：深度为k的二叉树至多有个结点（k≥1）

性质3：对任何一棵二叉树T,如果其终端结点数为，度为2的结点数为，

则= +1。

---

        二叉树的存储结构 

 二叉树顺寻存储结构：

 二叉链表：

         二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表。

         其中data是数据域，lchild和rlight都是指针域，分别存左孩子和有孩子的指针。

/*二叉树的二叉链表结点结构定义*/
typedef struct BiTNode    /*结点结构*/
{TElemType data;        /*结点数据*/struct BiTNode *lchild, *rchild;    /*左右孩子指针*/
}BiTNode, *BiTree;

 结构示意图：

---

遍历二叉树 

 二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问依次且仅被访问一次。

二叉树的遍历方法：

        1、前序遍历

        规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图，遍历顺序为：ABDGHCEIF。

        2、中序遍历

         规则是若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图，遍历顺序为：GDHBAEICF。

         3、后序遍历

        规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如下图：遍历顺序是：GHDBIEFCA

         4、层序遍历

        规则是若树为空，则空操作返回，否则从树的上一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如下图，遍历顺序：ABCDEFGHI。

 前序遍历算法：

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{if (T=NULL)return;printf("%c",T->data);    /*显示结点数据，可以更改为其他对结点操作*/PreOrderTraverse(T->lchild);    /*再先序遍历左子树*/PreOrderTraverse(T->rchild);    /*最后先序遍历右子树*/
}

 中序遍历算法：

/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{if (T=NULL)return;InOrderTraverse(T->lchild);    /*中序遍历左子树*/printf("%c",T->data);    /*显示结点数据，可以更改为其他对结点操作*/InOrderTraverse(T->rchild);    /*最后中序遍历右子树*/
}

 后序遍历算法： 

/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{if (T=NULL)return;PostOrderTraverse(T->lchild);    /*先后序遍历左子树*/PostOrderTraverse(T->rchild);    /*在后序遍历右子树*/printf("%c",T->data);    /*显示结点数据，可以更改为其他对结点操作*/
}

 两个二叉树遍历的性质：

        1、已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

        2、已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

---

---

二叉树的建立 

         

假设二叉树的结点均为一个字符，我们把刚才前序遍历序列AB#D##C##用键盘挨个输入。

/*按前序输入二叉树中结点的值（一个字符）*/
/* #表示空树，构造二叉链表表示二叉树T。*/
void CreateBiTree(BiTree *T)
{TElemType ch;scanf("%c",&ch);if(ch=='#')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)->data=ch;    /*生成根结点*/CreateBiTree(&(*T)->lchild);    /*构造左子树*/CreateBiTree(&(*T)->rchild);    /*构造右子树*/}
}

---

       线索二叉树 

我们把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree ）

 线索二叉树的结构的实现：

/*二叉树的二叉线索存储结构定义*/
typedef enum {Link,Thread} PointerTag; /*Link==0表示指向左右孩子的指针*//*Thread==1表示指向前驱或后继的线索*/
typedef struct BiThrNode        /*二叉线索存储结点结构*/
{TElemType data;        /*结点数据*/struct BiThrNode *lchild, *rchild;    /*左右孩子指针*/PointerTag LTag;PointerTag RTag;        /*左右标识*/
}BiThrNode, *BiThrTree;

         线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

         中序遍历线索化的递归函数代码：

BiThrTree pre;    /*全局变量，始终指向刚刚访问过的结点*/
/*中序遍历进行中序线索化*/
void InThreading(BiThrTree p)
{if(p){InThreading(p->lchild);    /*递归左子树线索化*/if(!p->lchild)            /*没有左孩子*/{p->LTag=Thread;    /*前驱线索*/p->lchild=pre;        /*左孩子指针指向前驱*/    }if(!pre->rchild)        /*前驱没有右孩子*/{pre->RTag=Thread;    /*后继线索*/pre->rchild=p;    /*前驱右孩子指针指向后继（当前结点p）*/}pre=p;                /*保持pre指向p的前驱*/InThreading(p->rchild);    /*递归右子树线索化*/}
}

---

树、森林、二叉树的转换

树转换为二叉树的步骤如下：

        1、加线。在所有兄弟之间加一条线。

        2、去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。

        3、层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。 

 森林转换为二叉树的步骤如下：

1、把每个树转换为二叉树。

2、第一课二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

  二叉树转换为树的步骤如下：

二叉树转树是树转换为二叉树的逆过程。

1、加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点，就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

2、去线。删除原二叉树中所有结点与其右孩子结点的连线。

3、层次调整。使之结构层次分明。

   二叉树转换为森林的步骤如下：

        判断一棵二叉树能够转换成一棵树还是森林，就是看这棵二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树。

1、从根结点开始，若右孩子存在，则把右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除......，直到所有的右孩子连线都删除为止，得到分离的二叉树。

2、再将每棵分离后的二叉树转换为树即可。