数据结构树的专题

• 2019 年 12 月 2 日
• 笔记

一、二叉树的基本操作

#include<stdio.h>  #include<stdlib.h>    typedef char ElemType;    typedef struct Node  {      ElemType data;      struct Node *lchild, *rchild;  } BiTree;    BiTree *createBT()  //键盘输入创建二叉树  {      BiTree *b;      ElemType ch;      scanf("%c", &ch);      fflush(stdin);  // 清空键盘缓冲      if(ch != '#')   // #表示空      {          b = (BiTree *)malloc(sizeof(BiTree));          b->data = ch;          printf("请输入%c的左孩子：", ch);          b->lchild = createBT();          printf("请输入%c的右孩子：", ch);          b->rchild = createBT();      }      else          b = NULL;      return b;  }    void createBT(BiTree *&b, char *s)  //用括号表示法的字符串s生成二叉树b  {      BiTree *st[100], *t;    //st存放树结点的栈      int top = -1;      int k;      //k=1表示左孩子， k=2表示右孩子        b = NULL;      while(*s)      {          switch(*s)          {          case '(':              top++;              st[top] = t;              k = 1;      //准备处理左孩子              break;          case ')':              top--;              break;          case ',':              k = 2;      //准备处理右孩子              break;          default:              t = (BiTree *)malloc(sizeof(BiTree));              t->data = *s;              t->lchild = t->rchild = NULL;              if(b == NULL)                  b = t;              else              {                  switch(k)                  {                  case 1:                      st[top]->lchild = t; break;                  case 2:                      st[top]->rchild = t; break;                  }              }          }          s++;      }  }    BiTree *createBT_PreIn(char *pre, char *in, int n)  //由先序序列pre和中序序列in的n个字符构造二叉树并返回  {      BiTree *b;      int i;      if(n<=0)          return NULL;      b = (BiTree *)malloc(sizeof(BiTree));      b->data = *pre;      for(i=0; i<n; i++)          if(in[i] == *pre)              break;      b->lchild = createBT_PreIn(pre+1, in, i);      b->rchild = createBT_PreIn(pre+i+1, in+i+1, n-i-1);        return b;  }    BiTree *createBT_InPost(char *in, char *post, int n)    //由中序序列in和后序序列post的n个字符构造二叉树并返回  {      BiTree *b;      int i;      if(n <= 0)          return NULL;      b = (BiTree *)malloc(sizeof(BiTree));      b->data = *(post + n - 1);      for(i=0; i<n; i++)          if(in[i] == b->data)              break;      b->lchild = createBT_InPost(in, post, i);      b->rchild = createBT_InPost(in+i+1, post+i, n-i-1);        return b;  }    void preOrder(BiTree *b)    //先序遍历二叉树  {      if(b)      {          printf("%c", b->data);          preOrder(b->lchild);          preOrder(b->rchild);      }  }    void inOrder(BiTree *b)     //中序遍历二叉树  {      if(b)      {          inOrder(b->lchild);          printf("%c", b->data);          inOrder(b->rchild);      }  }    void postOrder(BiTree *b)   //后序遍历二叉树  {      if(b)      {          postOrder(b->lchild);          postOrder(b->rchild);          printf("%c", b->data);      }  }    void dispBT(BiTree *b)      //括号法输出二叉树  {      if(b)      {          printf("%c", b->data);          if(b->lchild || b->rchild)          {              printf("(");              dispBT(b->lchild);              if(b->rchild)                  printf(",");              dispBT(b->rchild);              printf(")");          }      }  }    int BT_depth(BiTree *b)     //返二叉树的高度  {      int dep1, dep2;      if(b == NULL)          return 0;        dep1 = BT_depth(b->lchild);      dep2 = BT_depth(b->rchild);        return (dep1 > dep2 ? dep1 :dep2) + 1;  }    int leafNum(BiTree *b)      //统计叶子节点的个数  {      if(b == NULL)          return 0;      if(b->lchild == NULL && b->rchild == NULL)          return 1;      return leafNum(b->lchild) + leafNum(b->rchild);  }    BiTree *findNode(BiTree *b, ElemType x)     //查找二叉树b中值为x的结点，并返回该结点的指针  {      BiTree *p;      if(b == NULL)          return NULL;      else if(b->data == x)          return b;      else      {          p = findNode(b->lchild, x);          if(p != NULL)              return p;          else              return findNode(b->rchild, x);      }  }    void destroyBT(BiTree *&b)  //销毁二叉树  {      if(b)      {          destroyBT(b->lchild);          destroyBT(b->rchild);          free(b);          b = NULL;      }  }    void main()  {      BiTree *b;      char *s = "A(B(,X),C)";      char *pre = "ABXC";      char *in = "BXAC";      char *post = "XBCA";        //键盘输入二叉树      //printf("输入根结点(#表示空)：");      //b = createBT();        //括号表示法输入二叉树      //createBT(b, s);        //先序序列和中序序列输入二叉树      //b = createBT_PreIn(pre, in, 4);        //中序序列和后序序列输入二叉树      b = createBT_InPost(in, post, 4);        printf("n先序序列："); preOrder(b);      printf("n中序序列："); inOrder(b);      printf("n后序序列："); postOrder(b);      printf("n括号表示法："); dispBT(b);      printf("n深度：%d" , BT_depth(b));      printf("n叶子数：%dn", leafNum(b));      destroyBT(b);  }  

二、树、森林与二叉树的转换

1、树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是： （1）加线。就是在所有兄弟结点之间加一条连线； （2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线； （3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

2、森林转换为二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是： （1）先把每棵树转换为二叉树； （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

3、二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是： （1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来； （2）删除原二叉树中所有结点与其右孩子结点的连线； （3）整理（1）和（2）两步得到的树，使之结构层次分明。

4、二叉树转换为森林

二叉树转换为森林比较简单，其步骤如下： （1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树； （2）把分离后的每棵二叉树转换为树； （3）整理第（2）步得到的树，使之规范，这样得到森林。

根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。

三、AVL平衡二叉树

四、哈夫曼树的应用