树：是个结点的有限集合，时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足： 有且仅有一个特定的称为根的结点。 当时，其余结点可分为个互不相交的有限集合，其中每一个集合本身又是一棵树，并且称为根结点的子树。 显然树的定义是递归的，是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点： 树的根结点没有前驱结点，除根结点之外的所有结点有且仅有一个前驱结点。 树中所有结点可以有零个或者多个后继结点。 树适合于表示具有层次结构的数据。树中的某个结点（除了根结点之外）最多之和上一层的一个结点（其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中最多只有n-1条边。而树中每个结点与其下一层的零个或者多个结点（即其子女结点）有直接关系。 Alt text 对K来说：根结点A到K的唯一路径上的任意结点，称为K的祖先结点。如结点B是K的祖先节点，K是B的子孙结点。路径上最接近K的结点E称为K的双亲结点，K是E的孩子结点。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟节点，如K和L有相同的双亲结点E，即K和L是兄弟结点。 树中一个结点的子结点个数称为该结点的度，树中结点最大度数称为树的度。如B的度为2，但是D的度为3，所以该树的度为3. 度大于0的结点称为分支结点（又称为非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该节点的度。 结点的高度，深度和层次。 结点的层次从树根开始定义，根节点为第一层（有些教材将根节点定义为第0层），它的子结点为第2层，以此类推。 结点的深度是从根节点开始自顶向下逐层累加的。 结点的高度是从叶节点开始自底向上逐层累加的。 树的高度（又称深度）是树中结点的最大层数。 有序书和无序树：树中结点的子树从左到右是有次序的，不能交换，这样的树称为有序树。有序树中，一个结点其子结点从左到右顺序出现是有关联的。反之称为无序树。在上图中，如果将子结点的位置互换，则变为一棵不同的树。 路径和路径长度：树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。A和K的路径长度为3.路径为B，E。 森林：森林是m棵互不相交的树的集合。森林的概念和树的概念十分相近，因为只要把树的根节点删掉之后就变成了森林。反之，只要给n棵独立的树加上一个结点，并且把这n棵树作为该结点的紫书，怎森林就变成了树。 树具有如下最基本的性质。 树中结点数等于所有节点的度数+1. 度为m的树中第i层上之多有个结点。 高度为h的m叉树至多有个结点。 具有n个结点的m叉树的最小高度为。 二叉树的概念 二叉树和度为2的有序树的区别： 度为2的树至少有3个结点，而二叉树则可以为空； 度为2的有序树的孩子结点的左右次序是相对于另一个孩子结点而言的，如果某个结点只有一个孩子结点，这个孩子结点就无需区别其左右次序，但是二叉树无论孩子数是否为2，均需要确定其左右次序，也就是说二叉树结点次数不是相对于另一个结点而言，而是确定的。 Alt text 单解释一下完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号一一对应是称为完全二叉树。 二叉树的遍历 先序遍历 void PreOrder(BitTree T) { if(T!=NULL) { printf("%d\n",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } 中序遍历 void InOrder(BitTree T) { if(T!=NULL) { InOrder(T->lchild); printf("%d\n",T->data); InOrder(T->rchild) } } 后序遍历 void PostOrder(BitTree T) { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%d\n",T->data); } } 三种遍历算法中递归遍历左子树和右子树的顺序都是固定的，只是访问根节点的顺序不同。不管采用何种遍历方法，每个结点都是访问一次，所以时间复杂度就是。 在递归遍历中，递归工作栈的深度恰巧是树的深度，所以在最坏的情况下，二叉树是有n个结点且深度为n的单支树，递归遍历算法的时间复杂度是。 @[中序遍历的非递归算法如下] typedef struct BiTNode { int data; struct BiTNode *lchild,*rchild; }*BitTree; typedef struct { char data[MaxSize]; int top; }SqStack; void InitStack(SqStack &S) { S.top=-1; } void InOrder2(BitTree T) { InitStack(S); BitTree p=T; while(p||IsEmpty(s)) { if(p) { Push(S,p); p=p->lchild; } else { Pop(s,p); printf("%d\n",p->data); p=p->rchild; } } } 线索二叉树 遍历二叉树就是以一定的规则将二叉树中的结点排列为一个线性序列，从而得到二叉树中结点的各种遍历序列。其实质就是对一个非线性结构进行线性化操作，使在这个访问序列中的每一个结点（除了最后一个和第一个）都有一个直接前驱结点或者后继结点。 传统的链式储存能够体现出一种父子关系，不能直接得到结点在遍历中的前驱或者后继。通过观察，我们发现在二叉链表表示的二叉树中存在大量的空指针，若是利用这些空链域存放指向其直接的前驱或者后继的指针，则可以更加方便的运用某些二叉树的操作算法。引入线索二叉树是为了加快查找节点的前驱和后继的速度。 前面提到，在N个节点的二叉树中，有N+1个空指针。这是因为每个叶节点都有两个空指针，而每一个度为1的节点有一个空指针。总的空指针数目为，又有。意思是二倍的叶子节点加上1被的一个孩子的节点的数目。 线索二叉树的构造。 线索二叉树的存储结构描述如下： typedef struct ThreadNode { int data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; 表示lchild指向的是结点的左孩子 表示lchild指向的是结点的前驱 表示rchild指向的是结点的右孩子 表示rchild指向的是结点的后继 这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，称为线索。加上线索的二叉树称为线索二叉树。对二叉树进行以某种次序遍历使其变为线索二叉树的过程叫做线索化。 @[线索化二叉树的构造] 对二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中检查当前节点的左右指针是否为空，若为空，将他们改为指向前驱节点或者后继节点的线索。 @[P109] 度为2的有序树不是是二叉树：二叉树中如果某个节点只有一个孩子节点，那么这个孩子节点的左右次数是确定的，但是在有序树中如果某个节点只有一个孩子节点则这个节点无需区分其左右次序，所以度为2的树不是二叉树。 完全二叉树的节点数目和高度的关系是。 完全二叉树的节点排列是从左到右从上到下，所以如果一个节点没有左孩子，则它必定是叶节点。 二叉排序树 后面补上。 ---- 设层次遍历的结果为A，B，C。 则先序遍历的结果为A，B，C。 则中序遍历的结果为B，A，C。 则后续遍历的结果为B，C，A。 二叉树的中序遍历的最后一个节点一定是从根开始沿右子女指针链走到最低的结点。 树的存储结构 > 双亲表示法 这种存储方式采用一组连续空间来存储每个节点，同时在每个节点中增设一个尾指针指示双亲结点在数组中的位置。根节点下标为0，其伪指针域为-1. Alt text typedef struct // 数的结点定义 { int data; // 数据元素 int parent; // 双亲位置域 }PTNode; typedef struct // 树的类型定义 { PTNode nodes[Max_Tree_Size]; int n; // 双亲表示 }PTree; 这种结构利用了每个节点（根结点除外）只有唯一双亲的性质，可以很快的得到每个节点的双亲节点，但是求节点的孩子时却要遍历整个结构。 并查集 并查集是一种简单的集合表示，它支持一下三种操作： 把集合S中的子集合Root2，并入Root1中。要求Root1和Root2互不相交，否则不执行合并。 查找集合S中单元素x所在的子集合，并返回该子集合的名字。 将集合S中每一个元素都初始化为只有一个单元素的子集合。 通常用树（森林）的双琴表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组中。 并查集的结构定义如下： #define Size 100 int UFSets[Size]; void Initial(int S[]) { for(int i=0;i=0) x=S[x]; return x; } void Union(int S[],int Root1,int Root1) { S[Root1]=Root2; } 森林 由于二叉树和树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可以导出树与二叉树的一个对应关系，即给定一棵树，可以找出唯一的一棵二叉树与之对应。从物理结构上看，树的孩子兄弟表示法和二叉树的二叉链表表示法相同，即每个节点共有两个指针，分别指向结点的第一个孩子节点和结点的下一个兄弟节点，而二叉链表可以使用双指针。因此，就可以用同意存储结构的不同解释将一棵树转换为二叉树。 树转换为二叉树的规则：每个节点的左指针指向她的第一个孩子节点，右指针指向它在书中的相邻兄弟结点，可表示为左孩子有兄弟。由于根节点没有兄弟，所以由树转换而得的二叉树没有右子树。 Alt text 将森林转化为二叉树的规则和树类似。先将森林中的每一棵树转化为二叉树，再将第一棵树的根作为转换后的二叉树的根，第一棵树作为转化后的二叉树的根的左子树，第二颗数作为转换后二叉树的右子树，第三棵树作为转换后二叉树根右 子树的右子树，以此类推，就可将森林转换为二叉树。 树和二叉树的应用 二叉排序树：简称（BST），也称为二叉查找树。二叉排序树或者是一个空树，或者是一棵具有一下特性的非空二叉树： 若左子树非空，则左子树上所有节点关键字值均小于根节点的关键字值。 若右子树非空，则右子树上所有结点关键字值均大于根节点的关键字值。 左，右子树本身也是一棵二叉排序树 由二叉排序树的定义，有左子树根节点值根结点值右子树结点值，所以，对二叉树进行中序遍历，可以得到一个递增的有序序列。 Alt text 二叉排序树的查找是从根节点开始的，沿某一分值逐层向下进行比较的过程。若二叉排序树非空，将给定值与根结点的关键字比较，若相等，则查找成功；若不等免责当根节点的关键字较大的时候，在根节点的左子树中继续查找，否则在右子树中查找。这显然是一个递归的过程。 二叉排序树的查找 BSTNode *BST_Search(BitTree T,int key,BSTNode *&p) { // 返回指向关键字为key的结点指针，若不存在则返回NULL p=NULL; // p指向被查找结点的双亲，用于插入和删除操作中。 while(T!=NULL&&key!=T->data) { p=T; if(keydata) T=T->lchild; else T=T->rchild; } return T; } 二叉排序树的插入 int BST_Insert(BitTree &T,int k) { if(T==NULL) // 原树为空，新插入的记录为根节点。 { T=(BitTree)malloc(sizeof(BSTNode)); T->data=k; T->lchild=T->rchild=NULL; return 1; } else if(k==T->data) // 存在相同的结点。 return 0; else if(kdata) // 插入到T的左子树中 return BST_Insert(T->lchild,k); else return BST_Insert(T->rchild,k); } 由此可见，插入的新节点一定是某个叶节点。在一个二叉排序树先后依次插入结点28和58，虚线表示的边是其查找的路径。 二叉排序树的构造 void Create_BST(BitTree &T,int str[],int n) { T=NULL; int i=0; while(i

关键字：