数据结构之树

对于树的一些基本操作函数

1.InitTree(* T) :构造空树T

2.DestoryTree(* T) : 销毁树T

3.CreateTree(* T ,definition):按照definiton中给出的树的定义来进行构造树

4.ClearTree(* T): 若树T存在，则将树T清空

5.TreeEmpty(T): 若树T为空树，则返回true，否则返回 false

6.TreeDepth(T): 返回树T的深度

7.Root(T):返回树T的根节点

8.Value(T, cur_e):cur_e是树T的一个节点，返回此节点的值

9.Assign(T, cur_e, value) :给树T的cur_e节点赋值为value

10.Parent(T, cur_e):若cur_e是树T的非根节点，则返回他的双亲，否则返回空

11.LeftChild(T, cur_e): 若cur_e是树T的非叶节点，则返回他的左孩子，否则返回空

12.RightSibling(T,cur_e):若cur_e有右兄弟，则返回他的右兄弟，否则返回空

13.InsertChild(*T, *p, i, c): 若p指向树T的某个节点，i为所指节点p得到度上加1，非空树c与T不相交，操作结果为插入c为树T中p指节点的第i棵子树

14 DeleteChild(*T, *p, i):其中p指向树T的某个节点，i为所指节点p的度，操作结果为删除T中p所指节点的第i棵子树

二叉树的特点

1.每个结点最多有俩棵子树，所依二叉树不存在度大于2的结点（没有子树或者有一棵子树也是可以的）

2.左子树和右子树都是有顺序的，次序不能不能随意颠倒

3.即使树中某结点只有一颗子树，也要区分他是左子树还是右子树，

二叉树的5种基本形态

1.空二叉树

2.只有一个根节点

3.根节点只有左子树

4.根节点只有右子树

5.根节点既有左子树还有右子树

完全二叉树的特点

1.叶子节点只能出现在最下俩层

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

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

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

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

二叉树的性质

性质1：在二叉树的第i层上至多有2^（i-1）个结点(i>=1)

性质2：深度为k的二叉树至多有(2^k)-1个结点（k>=1）

性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1

性质4：具有n个结点的完全二叉树的深度为[log2n] + 1 ([x]代表不大于x的最大整数)

性质5：如果对一颗有n个结点的完全二叉树（深度为[log2n] + 1）的结点按层序编号（从第1层到第[log2n] + 1 层，每层从左到右），对任一结点i(1<=i<=n)有：

如果i=1 ，则结点i是二叉树的根，无双亲，；如果i>1,则其双亲是结点[i/2]

如果2i > n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子的结点为2i

如果2i+1 > n， 则结点无右孩子 ，否则其右孩子的结点为 2i+1

二叉树的储存结构

1.顺序结构一般只用于完全二叉树

2.链式结构适用于各种二叉树

typedef struct BiTNode{
  TElemType data;
  struct BiTNode *lchild, *rchild;

}BiTNode,*BiTree;

ps:

lchild

data

rchild

遍历二叉树

定义：从根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每一个结点最终被访问一次有且仅有一次

遍历方法

1.前序遍历

总结：根-左-右

算法实现：

void PreOrderTraverse(BiTree T){
    if(T == NULL){
    return ;
    }
    printf("%c", T -> data); //显示数据，可以更改为其他对结点的操作

    PreOrderTraverse(T -> lchild); //先序遍历左子树

    PreOrderTraverse(T -> rchild); //先序遍历右子树
}

2.中序遍历

总结：左-根-右(先是左子树，根节点，右子树)

算法实现：

void InOrderTraverse(BiTree T){
    if(T == NULL){
    return;
    }
    InOrderTraverse(T -> lchild); //中序遍历左子树

    printf("%c", T -> data); // 显示数据，可以更改为对其他结点的操作

    InOrderTraverse(T -> rchild); // 中序遍历右子树
}

3.后序遍历

总结：左-右-根（以先叶子后结点的顺序先访问左右子树）

void PostOrderTraverse(BiTree T){
    if(T == NULL){
    return;
    }
    PostOrderTraverse(T -> lchid);
    PostOrderTraverse(T -> rchild);
    printf("%c", T -> data);
}

4.层序遍历：

总结：从根节点开始，每层从左到右进行逐个遍历

二叉树的建立

原理：利用扩展二叉树来进行遍历确定一颗二叉树(扩展出来的每个叶或者根用#来代替)

代码实现：

void CreateBiTree(BiTree *T){
  TElemType ch;
  scanf("%c", ch);

  if(ch == '#'){
    *T = NULL;
  }else{
    *T = (BiTree)malloc(sizeof(BiNode));

     if(!*T){
     exit(OVERFLOW);
     (*T) -> data = ch; //生成根节点

     CreateBiTree(&(*T) -> lchild); //构造生成左子树

     CreateBiTree(&(*T) -> rchild); //构造生成右子树
     }
  }
}

线索二叉树

指向前驱和后继的指针叫做线索，加上线索的二叉链表就是线索链表，相应的二叉树称为线索二叉树。

总结：线索二叉树其实等于把一颗二叉树转变成一个双向链表

为了解决某一节点的lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要在每个结点加入俩个标志ltag，rtag。

说明： ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。

rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

typedef enum{
  Link,Thread; //Link == 0 表示指向左右孩子的指针 Thread == 1表示指向前驱或者后继的线索
}PointerTag;


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 -> lchid); //递归左子树线索化

  if(!p -> lchid){    //没有左孩子
     p -> LTag = Thread;  //前驱线索
     p -> lchid = pre;   //左孩子指针指向前驱
  }
  if(!pre -> rchild){        //前驱没有右孩子
     pre -> RTag = Thread;   //后继线索
     pre -> rchild = p ;   //右孩子指针指向后继
  }
  pre = p ;                  //保持pre指向p的前驱
  InThreading(p -> rchild); // 递归右子树线索化
    }
}

注意：if（! p -> lchid）表示如果某结点的左指针域为空，因为其前驱点刚刚访问过了，赋值给了pre，所以可以将pre赋值给 p->lchild ，并修改 p->LTag = Thread（也就是定义为1），以完成前驱点的线索化

后继稍微麻烦些，因为此时的p结点的后继还没有访问到，因此只能对他的前驱结点pre的右指针rchild做判断， if（！pre -> rchild）,如果为空，则p就是pre的后继，于是pre->rchild = p；并且设置 pre->RTag = Thread,完成后续结点的线索化

线索二叉树的遍历

总结：首先在二叉树线索链表上添加一个头结点，其rchild域的指针指向中序遍历是访问的最后一个结点，反之，令二叉树的中序序列中的第一个结点和最后一个结点中，lchild域指针和最火=后一个结点的rchild域均指向头结点。这样既可以从第一个结点开始顺后继遍历，也可以从最后一个结点顺前驱进行遍历

遍历代码实现：

// T指向头结点，头结点左链lchild指向根节点，头结点右链rchild指向中序遍历的最后一个结点，T表示的就是中序遍历的线索二叉树双向链表

Status InOrderTraverse_Thr(BiThrTree T){

   BiThrTree p ;

   p -> T -> lchid //p指向根节点

   while(p != T){  //空树遍历结束时 p == T

   while(p -> LTag == Link) //Link表示左右孩子指针，也就是为了找出左孩子

        p = p -> lchild;  //此时找到左孩子

        printf("%c", p -> data); //显示结点数据，可以更改为对其他结点的操作，打印第一个结点

        while( p -> RTag == Tread && p -> rchild != T){

           p = p -> rchild;        //此时代表第一个结点的后继（仅仅是第一次循环时）

           printf("%c", p -> data);

        }

        p = p -> rchild;             //此时p指向第一个结点后继的右孩子
   }

   return OK;
}

// 其实中心思想还会中序遍历，左根右 只是添加了前驱，后继。

树，森林与二叉树的转换

1.树转化为二叉树：

加线，在所有兄弟之间加一条线
去线，只把刘树中每个结点和他的第一个孩子的连线，删除其他的连线
层次调整，以树的根节点为轴心，然后将整棵树旋转一定的角度，使之结构分明，注意第一个孩子是结点的左孩子，兄弟结点转换过来是结点的右孩子

2.森林转换为二叉树

把每棵树都转化为二叉树

*第一棵二叉树不动，然后把后续的每颗二叉树根节点当做前一棵二叉树的根结点的右孩子。

3.二叉树转化为树

加线，如果某根节点的左孩子存在，就把他的左孩子的右孩子结点，以及他右孩子的右孩子结点，，右孩子的右孩子的右孩子几点…….把他们和此结点连接。
去线，删除原二叉树中所有结点与右孩子结点的连线。

*层次调整，使之结构分明。

4.二叉树转化为森林

只要判断二叉树的根节点有没有右孩子，从根节点开始，若右孩子存在，则把与右孩子结点的连线删除了，再查看分离的二叉树的根节点是否还有右孩子，若有的话，再次删除与之连线，以此类推，直到所有右孩子的连线都被删除，得到分离后的二叉树
把分离后的二叉树转换成树就行了

树和森林的遍历

树的遍历

1.先根遍历：先访问树的根节点，然后依次先根遍历根的每颗子树。

2.后根遍历：即线遍历根节点下的每棵子树，再访问遍历根节点。

森林的遍历

1.前序遍历：先访问第一棵子树的根节点，然后再依次先根遍历每颗子树，然后再以前边的方式遍历出去第一棵树二剩下的子树组成的森林。

2.后序遍历：先访问第一棵子树，后根遍历的方式遍历每颗子树，然后再访问根节点，依次类推，再次访问除第一棵树而剩下的其他的树组成的森林。

赫夫曼树及其应用

1.路径长度：从树中的一个结点到另一个结点之间的分支构成俩结点之间的路径，路径上的分支树目称为路径长度（就是一个结点到另一个结点的连线的个数）

2.赫曼夫树：假设有n个权值，构造一个有n个叶子结点的二叉树，每个叶子带权w 每个叶子的路径长度为l，我们通常把带权路径长度最小的二叉树称为赫夫曼树。

3.赫夫曼树建立的方法：

先把叶子结点的权值进行从小到大的排序

把权值最小的俩个孩子当做新节点N1的俩个孩子（注意权值最小的为左孩子）

计算N1权值，然后把N1加入当时已经排好序的权值结点中（已经除去权值最小的俩个叶子结点）

一直重复上述三步，直到排列出从小到大权值的二叉树称为最优二叉树即赫曼夫二叉树

切记，记住如果得到赫夫曼树是计算带权路径的长度时不用吧N1， N2 ,N3……Nn算进去

代码实现赫曼夫树的生成：

struct BTreeNode* CreateHuffman(ElemType a[] , int n){
    int i , j ;
    struct BTreeNode **b, *q;
    b = malloc(n*sizeof(struct BTreeNode));
    for(i = 0 ; i < n ; i ++){
        b[i] = malloc(sizeof(struct BTreeNode)); //初始化b指针数组，是每个指针元素指向a数组中对应的元素结点
        b[i] -> data = a[i];         //给data元组赋值
        b[i] -> left = b[i] -> right = NULL;  //初始化左右子树

    }

    for(i = 1 ; i < n ; i++){   //进行n-1次循环建立赫夫曼树
    // k1表示森林中具有最小权值的树根结点的下标，k2位次最小下标

     int k1 = -1, k2;

      for(j = 0 ; j < n ;j ++){
         if(b[j] != NULL && k1 == -1){
           k1 = j;
           continue;
         }
         if(b[j] != NULL){
           k2 =j;
           break;
         }
      }
      for(j = k2 ; j < n ; j ++){  //从当前森林中求出最小权值树和次小

        if(b[j] != NULL){

              if(b[j] -> data < b[k1] -> data){
              k2  = k1;
              k1 = j;
              }
              else if(b[j] -> data <b[k2] -> data){
              k2 =j;
              }
        }
      }
      //由最小权值树和次小权值树建立一颗新书，q指向树根结点

      q = malloc(sizeof(struct BTreeNode));
      q -> data = b[k1] -> data + b[k2] -> data;

      q ->left = b[k1];
      q-> right = b[k2];

      b[k1] = q; //将指向新书的指针赋给b指针数组中k1的位置
      b[k2] = NULL; // k2位置为空
    }
free(b);   //删除动态建立的数组b；
return q;   //返回整个赫夫曼树的树根指针
}

赫夫曼编码

赫夫曼编码的应用：压缩文件，保密文件传输，电文传输

最后实现搜索二叉树的插入，查找，删除

简单再回顾一下搜索二叉树的概念：

二叉树搜索树又称为二叉排序树，它或者为一颗空树，或者是具有以下性质的二叉树：

若他的左子树不为空，则左子树上所有的结点的值都小于根节点的值

若他的右子树不为空，则右子树上所有结点的值都大于根节点的值。

他的左右姿势也为二叉搜索树

二叉树结构

typedef struct BSTreeNode{

   struct BSTreeNode *left;  //左子树

   struct BSTreeNode *right;  //右子树

   DataType data;  //数据集

}BSTreeNode;

二叉树结点的创建

BSTreeNode *CreateTreeNode(DataType x){  //创建结点
    BSTreeNode *node = (BSTreeNode)*malloc(sizeof(BSTreeNode));
    assert(node);  //设置断点，以后debug时会用到 需要引入头文件<assert.h>

    node -> data = x;
    node -> left = NULL;
    node -> right = NULL;

    return node;
}

二叉搜索树操作

搜索二叉树的插入：在二叉搜索树中插入新元素时，必须先检测该元素是否已经存在，如果已经存在，则不进行插入，否则将新元素加入到搜索停止的地方。

非递归型：

int BSTreeNodeInsert(BSTreeNode **pptree, DataType x){ // 搜索二叉树的插入
     BSTreeNode *parent = NULL;
     BSTreeNode *cur = *pptree;

     if(*pptree == NULL){
     *pptree = CreateTreeNode(x);
     return 0;
     }
     while(cur){
     parent = cur;
     if(cur -> data > x){
         cur = cur -> left ;
     }
     else if(cur -> data < x){
         cur = cur -> right;
     }
     else
          return -1;
     }

     if(parent -> data > x){
        parent -> left = CreateTreeNode(x);
     }
     else{

        parent -> right = CreateTreeNode(x);
    }

    return 0;
}

递归型

int BSTreeNodeInsertR(BSTreeNode **tree,DataType x){//搜索树的插入
  if(*tree == NULL){
       *tree = BuyTreeNode(x);
       return 0;
   }

   if((*tree) -> data > x){
       return BSTreeNodeInsertR(&(*tree) -> left ,x );
   }
   else if((*tree) -> dta < x){
     return BSTreeNodeInsertR(&(*tree) -> right ,x);
   }

   else

   return -1;

}

搜索二叉树的查找

非递归型：

BSTreeNode *BSTreeNodeFind(BSTreeNode *tree, DataType x){

 while(tree){
   if (tree -> data  == x ){
    return tree;
 }
 else if (tree -> data  < x){
    tree = tree -> right ;
 }
 else
    tree = tree -> left ;

return NULL;  }

递归型： BSTreeNodeFindR(BSTreeNode * tree ,DataType x){ //二叉树的查找

if(!tree){
return NULL;
}

if (tree -> data > x){
BSTreeNodeFindR(tree -> left ,x);
}
else if (tree -> data < x){
BSTreeNodeFindR(tree -> right , x);
}
else
return tree; }

搜索二叉树的删除

闪现查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分为以下四种情况：

a.要删除的结点为无孩子的结点

b.要删除的结点只有左孩子的结点

c.要删除的结点只有右孩子结点

d.要删除的结点有左，右孩子的结点

对应的删除方法如下：

a. 直接删除该结点

b. 删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点

c. 删除该结点且使被删除结点的双亲指向被删除结点的右孩子的节点

d. 在他的右子树中寻找中序下的第一个结点（关键码最小），用他的值填补到被删除结点中，再来处理该结点的删除问题