树
2018-07-20 本文已影响0人
pangdong
树(Tree)
定义
树(Tree) 是n个(n≥0)个结点的有限集。n=0时称为空树。
在任何一个非空树中：
(1) 有且仅有一个特定的称为根(root)的结点；
(2) 当n>1时，其余结点可分为m个互不相交的有限集。(子树)
结点分类
结点拥有的子树数称为结点的度(Degree)；
度为0的结点称为叶结点(Leaf) 或终端结点；
度不为0的结点称为非终端结点或分支结点；
除根结点之外，分支结点也称为内部结点；
树的度是树内各结点的度的最大值。
抽象数据类型
ADT 树(tree)
Data
树是由一个根结点和若干棵子树构成。数中结点具有相同的数据类型和层次关系
Operation
InitTree(*T):
DestroyTree(*T):
CreatTree(*T,definition):
ClearTree(*T):
TreeEmpty(T):
TreeDepth(T):
Root(T):
Value(T,cur_e):
Assign(T,cur_e,value):
parent(T,cur_e):
LeftChild(T,cur_e):
RightSibling(T,cur_e):
InsertChild(*T,*p,i,c):
DeleteChild(*T,*p,i):
endADT
树的存储结构
双亲表示法:在每个结点中，附设一个指示器指示其双亲结点在数组中的位置
// 树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef char TElemType; /*树结点的数据类型*/
typedef struct PTNode{ /*结点结构*/
TElemType data; /*结点数据*/
int parent; /*双亲位置*/
}PTNode;
typedef struct{ /*树结构*/
PTNode nodes[MAX_TREE_SIZE]; /*结点数组*/
int r,n; /*根的位置和结点数*/
}PTree;
每个结点有多个指针域，其中每个指针指向一棵子树的根结点。(多重链表表示法)造成浪费
孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构。则n个孩子有n个孩子链表。
如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组。
// 树的孩子表示法结构定义
#define MAX_TREE_SIZE 100
typedef struct CTNode{ /* 孩子结点 */
int child;
struct CTNode *next;
}*ChilePtr;
typedef struct{ /* 表头结构 */
TElemType data;
ChildPtr firstchild;
}CTBox;
typedef struct{ /* 树结构 */
CTBox nodes[MAX_TREE_SIZE];
int r,n; /* 根的位置和结点数 */
}Ctree;
孩子兄弟表示法：任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
// 树的孩子表示法结构定义
typedef struct CSNode {
TElemType data;
struct CSNode *firstchild,*rightsib;
}CSNode,*CSTree;
二叉树(Binary Tree)
是n个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。
特点：
满二叉树：
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的树叫~；
完全二叉树：
对一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
满二叉树一定是一棵完全二叉树，但是完全二叉树不一定是满的。
满二叉树特点：
叶子只能出现在最下一层；
非叶子结点的度一定是2；
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树特点：
叶子结点只能出现在最下两层；
最下层的叶子一定集中在左部连续位置；
倒数二层，若有叶子结点，一定都在右部连续部分；
如果结点度为1，则该结点只有左孩子，集不存在只有右子树的情况；
同样结点数的二叉树，完全二叉树的深度最小。
性质：
性质1：在二叉树的第i层上至多有2^(i-1)个结点;
性质2：深度为k的二叉树至多有2^k-1个结点;
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1;
性质4：具有n个结点的完全二叉树的深度为|log2 n|+1;(|x|为不大于x的最大整数)
性质5：如果对一棵有n个结点的完全二叉树，对任一结点i：
1)如果i=1，则结点i是二叉树的根；如果i>1，则其双亲是结点；
2)如果2i>n，则结点i无左孩子，否则其左孩子是结点2i；
3)如果2i+1>n,则结点i无右孩子，否则其右孩子是结点2i+1。
二叉树的存储结构
顺序存储结构：完全二叉树
链式存储结构：
/* 二叉树的二叉链表结点结构定义*/
/* lchild data rchild */
typedef struct BiTNode{ /* 结点结构 */
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
遍历二叉树：
二叉树的遍历(traversing binary tree)
指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被且仅被访问一次 ；
前序遍历：
若二叉树为空，则返回；否则先访问根结点，然后前序遍历左子树，再前序遍历右子树；
/* 二叉树的前序遍历递归算法 */
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);
}
层序遍历：
若二叉树为空，则返回；否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问；
建立二叉树：
/* 默认用户按前序遍历序列输入二叉树数据 */
/* #表示空树，构建二叉链表来表示二叉树T */
void CreatBiTree(BiTree *T) {
TElemType ch;
scanf("%c",&ch);
if(ch=='#')
*T=NULL;
else{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(0);
(*T)->data = ch;
CreatBiTree(&(*T)->lchild);
CreatBiTree(&(*T)->rchild);
}
}
线索二叉树(Threaded Binary Tree)
指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。
lchild ltag data rtag rchild
ltag为0时，指向该结点的左孩子，为1时指向该结点的前驱；
rtag为0时，指向该结点的右孩子，为1时指向该结点的后继；
线索二叉树的结构实现：
/* 二叉树的二叉线索存储结构定义 */
typedef enum{Link,Thread} PointerTag; /*Link == 0 表示指向左右孩子指针 */
/*Thread == 0 表示指向前驱或后继的线索 */
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); /*递归右子树线索化 */
}
}
/*中序遍历二叉线索链表表示的二叉树 */
Status InOrderTraverse_Thr(BiThrTree T){
BiThrTree p;
p = T->lchild;
while( P!= T){
while( p->LTag == Link){
p = p->lchild;
}
printf("%c",p->data);
while( p->RTag == Thread && p->rchild != T){
p = p->rchild;
printf("%c",p->data);
}
p = p->rchild;
}
return Ok;
}
实例：创建一棵线索二叉树，并中序遍历该二叉树
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
// 线索存储标志位
// Link(0)：表示指向左右孩子的指针
// Thread(1) ：表示指向前驱后继的线索
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode {
ElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag ltag;
PointerTag rtag;
} BiThrNode,*BiThrTree;
// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreatBiThrTree(BiThrTree *T) {
char c;
scanf("%c",&c);
if(' ' == c)
*T = NULL;
else {
*T = (BiThrNode *)malloc(sizeof(BiThrNode));
(*T)->data = c;
(*T)->ltag = Link;
(*T)->rtag = Link;
CreatBiThrTree(&(*T)->lchild);
CreatBiThrTree(&(*T)->rchild);
}
}
// 中序遍历线索化（递归）
BiThrTree pre; //全局变量，始终指向刚刚访问过的结点
void InThreading(BiThrTree T) {
if(T) {
InThreading(T->lchild);
if(!T->lchild) {
T->ltag = Thread;
T->lchild = pre;
}
if(!pre->rchild) {
pre->rtag = Thread;
pre->rchild = T;
}
pre = T;
InThreading(T->rchild);
}
}
void InOrderThreading(BiThrTree *p,BiThrTree T) {
*p = (BiThrNode *)malloc(sizeof(BiThrNode));
(*p)->ltag = Link;
(*p)->rtag = Thread;
(*p)->rchild = *p;
if(!T){
(*p)->lchild = *p;
}
else{
(*p)->lchild = T;
pre = *p;
InThreading(T);
pre->rchild = *p;
pre->rtag = Thread;
(*p)->rchild = pre;
}
}
// 中序遍历二叉树，非递归
void InOrederTraverse(BiThrTree T){
BiThrTree p;
p = T->lchild;
while( p!= T){
while( p->ltag == Link)
p = p->lchild;
printf("%c",p->data);
while( p->rtag == Thread && p->rchild != T){
p = p->rchild;
printf("%c",p->data);
}
p = p->rchild;
}
}
int main(int argc, char *argv[]) {
BiThrTree p,T = NULL;
CreatBiThrTree(&T);
InOrderThreading(&p,T);
printf("中序遍历输出结果为：");
InOrederTraverse( p ) ;
printf("\n");
return 0;
}
实例：创建一棵二叉树，并分别按前序、中序、后序方式遍历二叉树。
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct BiTNode {
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
// 创建一棵二叉树 ,约定用户遵照前序遍历的方式输入数据
CreateBiTree(BiTree *T) {
char c;
scanf("%c",&c);
if(' '==c) {
*T = NULL;
} else {
*T = (BiTNode *)malloc(sizeof(BiTNode));
(*T)->data = c;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
// 前序遍历二叉树
PreOrderTraverse(BiTree T) {
if( T ) {
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
// 中序遍历二叉树
InOrderTraverse(BiTree T) {
if( T ) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
// 后序遍历二叉树
PostOrderTraverse(BiTree T) {
if( T ) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
int main(int argc, char *argv[]) {
printf("建一棵二叉树 ,约定用户遵照前序遍历的方式输入数据\n");
BiTree T = NULL;
CreateBiTree(&T) ;
printf("\n 前序遍历结果是：\n");
PreOrderTraverse(T);
printf("\n 中序遍历结果是：\n");
InOrderTraverse(T);
printf("\n 后序遍历结果是：\n");
PostOrderTraverse(T);
return 0;
}
