C语言数据结构——二叉树的顺序存储结构

水深无声 2022-06-15 12:52 303阅读 0赞

1、二叉树的顺序存储结构就是用一维数组存储二叉树的结点，结点的存储位置就是数组下标要能体现结点间的逻辑关系。
2、顺序存储结构一般只适用于完全二叉树。

3、http://www.cnblogs.com/Alex-bg/archive/2012/08/12/2634203.html（代码原址）

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <malloc.h> 
  5. #include <math.h>
  7. #define TRUE 1
  8. #define FALSE 0
  9. #define OK 1
  10. #define ERROR 0
  12. #define MAX_TREE_SIZE 100
  13. #define MAX_QUEUE_SIZE 5
  14. #define Nil ' ' 
  16. typedef char TElemtype;    //将树的结点类型设置为字符型 
  17. typedef int QElemType;    //将队列的结点类型设置为整形 
  20. typedef struct{     
  21.     QElemType *base;    //队列的基地址 
  22.     int front;     
  23.     int rear;     
  24. }SqQueue;
  26. typedef TElemtype SqBiTree[MAX_TREE_SIZE];    //定义顺序存储二叉树的结构数组 
  28. typedef struct{
  29.     int level;    //树的层号 
  30.     int order;    //一层中的序号(从左向右) 
  31. }position;
  33. /**-------队列的函数声明------*/
  35. int InitQueue(SqQueue *);    //初始化队列 
  36. int DestroyQueue(SqQueue *);    //销毁队列 
  37. int ClearQueue(SqQueue *);    //清空队列 
  38. int QueueEmpty(SqQueue *);    //队列是否为空 
  39. int GetQueueLength(SqQueue *);    //获取队列的长度 
  40. int GetQueueHead(SqQueue *,QElemType *);    //获取队头元素 
  41. int EnterQueue(SqQueue *,QElemType);    //向队列中插入元素 
  42. int DeleteQueue(SqQueue *,QElemType *);    //向队列中删除元素 
  43. int (*QueueVisit)(QElemType);    //函数变量 
  44. int QueueTraverse(SqQueue *,int (*) (QElemType));    //遍历队列 
  47. /*---------二叉树的函数声明*/ 
  49. int InitBiTree(SqBiTree);    //初始化二叉树 
  50. int CreateBiTree(SqBiTree);    //创建二叉树 
  51. int BiTreeEmpty(SqBiTree);    //判断二叉树是否为空 
  52. int BiTreeDepth(SqBiTree);    //计算二叉树的深度 
  53. int GetRoot(SqBiTree,TElemtype *);    //获取二叉树的根结点 
  54. TElemtype GetNodeValue(SqBiTree,position);    //获取二叉树结点元素 
  55. int Assign(SqBiTree,position,TElemtype);    //给结点元素赋值 
  56. TElemtype GetParent(SqBiTree,TElemtype);    //获取结点的双亲结点 
  57. TElemtype GetLeftChild(SqBiTree,TElemtype);    //获取结点的左孩子 
  58. TElemtype GetRightChild(SqBiTree,TElemtype);    //获取结点的右孩子 
  59. TElemtype GetLeftSibling(SqBiTree,TElemtype);    //获取结点的左兄弟 
  60. TElemtype GetRightSibling(SqBiTree,TElemtype);    //获取结点的右兄弟 
  61. void Move(SqBiTree,int,SqBiTree,int);    //移动结点 
  62. int InsertChild(SqBiTree,TElemtype,int,SqBiTree);    //插入子结点 
  63. int DeleteChild(SqBiTree,position,int);    //删除子结点 
  64. int (*TreeVisit)(TElemtype);    //函数变量 
  65. int PreOrderTraverse(SqBiTree, int (*Visit)(TElemtype));    //先序遍历二叉树 
  66. int InOrderTraverse(SqBiTree,int (*Visit)(TElemtype));    //中序遍历二叉树 
  67. int PostOrderTraverse(SqBiTree,int (*Visit)(TElemtype));    //后序遍历二叉树 
  68. void LevelOrderTraverse(SqBiTree,int (*Visit)(TElemtype));    //层序遍历二叉树 
  69. void PrintTree(SqBiTree);    //打印二叉树 
  71. /*-----------队列的函数定义-----------*/ 
  73.  /*初始化队列*/ 
  74. int InitQueue(SqQueue *Q)
  75. {
  76.     //分配内存区域 
  77.     Q->base=(QElemType *)malloc(MAX_QUEUE_SIZE*sizeof(QElemType)); 
  78.     if(!Q->base)
  79.     {
  80.         printf("存储分配失败.\n");
  81.         return ERROR;
  82.     }
  83.     Q->front=Q->rear=0;    //将队列置空 
  84.     return OK;
  85. }
  87. /*销毁队列*/ 
  88. int DestroyQueue(SqQueue *Q)
  89. {
  90.     if(Q->base)
  91.     {
  92.         free(Q->base);
  93.     }
  94.     Q->front=Q->rear=0;
  95.     return OK;
  96. }
  98. /*清空队列*/ 
  99. int ClearQueue(SqQueue *Q)
  100. {
  101.     Q->front=Q->rear=0;
  102.     return OK;
  103. }
  105. /*判断队列是否为空*/ 
  106. int QueueEmpty(SqQueue *Q)
  107. {
  108.     if(Q->front==Q->rear)
  109.     {
  110.         return OK;
  111.     }
  112.     else
  113.     {
  115.         return ERROR;
  116.     }
  117. }
  119. /*获取队列长度*/
  120. int GetQueueLength(SqQueue *Q)
  121. {
  122.     return (Q->rear-Q->front);
  123. }
  125. /*获取队列头的元素*/ 
  126. int GetQueueHead(SqQueue *Q,QElemType *e)
  127. {
  128.     if(!QueueEmpty(Q))
  129.     {
  130.         *e=*(Q->base+Q->front);    
  131.         return OK;    
  132.     }
  133.     return ERROR;
  134. }
  136. /*使元素进队*/ 
  137. int EnterQueue(SqQueue *Q,QElemType e)
  138. {
  139.     if(Q->rear == MAX_QUEUE_SIZE)    //队列满了,重新分配内存区域,用realloc 
  140.     {
  141.         printf("队列已满,尝试增加存储单元...\n"); 
  142.         Q->base=(QElemType *)realloc(Q->base,MAX_QUEUE_SIZE+1);
  143.         if(!Q->base)        
  144.         {
  145.             printf("增加队列存储单元失败.\n");
  146.             return ERROR;
  147.         }
  148.     }
  149.     *(Q->base+Q->rear)=e;
  150.     Q->rear++;
  151.     return OK;
  152. }
  154. /*删除队头元素*/ 
  155. int DeleteQueue(SqQueue *Q,QElemType *e)
  156. {
  157.     if(QueueEmpty(Q))
  158.     {
  159.         //printf("队列为空.\n");
  160.         return ERROR;
  161.     }
  162.     *e=*(Q->base+Q->front);
  163.     Q->front++;
  164.     return OK;
  165. }
  167. /*遍历队列*/ 
  168. int QueueTraverse(SqQueue *Q,int (*QV)(QElemType) )
  169. {
  170.     int i=0;
  171.     while(i<Q->rear)
  172.     {
  173.         (*QV)(*(Q->base+i));
  174.         i++;
  175.     }    
  176. }
  178. /*访问队列中元素的函数,将元素值打印出来*/ 
  179. int QueueVisitFunc(QElemType e)
  180. {
  181.     printf("%d\n",e);
  182. }
  184. /*-------二叉树的函数定义-------*/
  186. /*初始化树*/ 
  187. int InitBiTree(SqBiTree T)
  188. {
  189.     int i;
  190.     for(i=0;i<MAX_TREE_SIZE;i++)
  191.     {
  192.         T[i]=Nil;    //将初值设为空格 
  193.     }
  195.     T[MAX_TREE_SIZE]='\0';    //给数组尾部加上结标致 
  196.     return OK;
  197. } 
  199. /*创建树*/ 
  200. int CreateBiTree(SqBiTree T)
  201. {
  202.     int i=0;
  203.     int l=0;
  204.     char s[MAX_TREE_SIZE];
  205.     printf("请按顺序输入结点的值,空格表示空结点,结点数<=%d\n",MAX_TREE_SIZE);
  206.     gets(s);
  207.     l=strlen(s);
  208.     for(;i<l;i++)
  209.     {
  210.         T[i]=s[i];
  211.         if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil)
  212.         {
  213.             printf("出现无双亲且不是根的结点.\n");
  214.             return ERROR;
  215.         }
  216.     }
  217.     for(;i<MAX_TREE_SIZE;i++)
  218.     {
  219.         T[i]=Nil; 
  220.     }
  221.     return OK;
  222. }
  224. #define ClearBiTree InitBiTree    //在顺序存储结构中,ClearBiTree和InitBiTree完全一样 
  226. /*判断树是否为空*/ 
  227. int BiTreeEmpty(SqBiTree T)
  228. {
  229.     if(T[0]==Nil)
  230.     {
  231.         printf("树为空.\n");
  232.         return TRUE;
  233.     }
  234.     else
  235.     {
  236.         return FALSE;
  237.     }
  238. }
  240. /*计算树的深度*/ 
  241. int BiTreeDepth(SqBiTree T)
  242. {
  243.     int j=-1;
  244.     int i=0;
  245.     if(BiTreeEmpty(T))
  246.     {
  247.         return ERROR;    
  248.     }
  249.     for(i=MAX_TREE_SIZE-1;i>=0;i--)
  250.     {
  251.         if(T[i]!=Nil)
  252.         {
  253.             break;
  254.         }
  255.     }
  256.     i++;
  257.     //printf("i = %d\n",i);
  258.     do
  259.     {
  260.         j++;
  261.     }while(i>=pow(2,j));
  262.     return j;
  263. }
  265. /*获取根结点的值*/ 
  266. int GetRoot(SqBiTree T,TElemtype * e)
  267. {
  268.     if(BiTreeEmpty(T))
  269.     {
  270.         return ERROR;
  271.     }
  272.     *e=T[0];
  273.     return OK;
  274. }
  276. /*根据位置获取某一结点的值*/ 
  277. TElemtype GetNodeValue(SqBiTree T,position p)
  278. {
  279.     return T[(int)pow(2,p.level)-1-(int)pow(2,p.level-1)+p.order-1];
  280. }
  282. /*根据结点的位置给某一结点元素赋值*/ 
  283. int Assign(SqBiTree T,position p,TElemtype e)
  284. {
  285.     int i = (int)pow(2,p.level)-1-(int)pow(2,p.level-1)+p.order-1;
  286.     if(e!=Nil&&T[(i+1)/2-1]==Nil)
  287.     {
  288.         printf("将要赋值的结点双亲为空,不合法.\n");
  289.         return ERROR;
  290.     }
  291.     if(e==Nil&&(T[2*i+1]!=Nil||T[2*i+2]!=Nil))
  292.     {
  293.         printf("将有子结点的结点赋空值,不合法.\n");
  294.         return ERROR;
  295.     }
  296.     T[i]=e;
  297.     //printf("T[%d] 已修改为: %c.\n",i,T[i]);
  298.     return OK;
  299. }
  301. /*获取结点元素的双亲结点*/ 
  302. TElemtype GetParent(SqBiTree T,TElemtype e)
  303. {
  304.     int i;
  305.     if(BiTreeEmpty(T))
  306.     {
  307.         return Nil;
  308.     }
  309.     for(i=0;i<MAX_TREE_SIZE;i++)
  310.     {
  311.         if(T[i]==e)
  312.         {
  313.             return T[(i+1)/2-1];
  314.         }
  315.     }     
  316.     printf("未找到双亲结点.\n");
  317.     return Nil;
  318. }
  320. /*获取结点元素的左孩子*/ 
  321. TElemtype GetLeftChild(SqBiTree T,TElemtype e)
  322. {
  323.     int i;
  324.     if(BiTreeEmpty(T))
  325.     {
  326.         return Nil;
  327.     }
  328.     for(i=0;i<MAX_TREE_SIZE;i++)
  329.     {
  330.         if(T[i]==e)
  331.         {
  332.             return T[2*i+1];
  333.         }
  334.     }
  335.     printf("未找到左孩子.\n");
  336.     return Nil;
  337. }
  339. /*获取结点元素的右孩子*/ 
  340. TElemtype GetRightChild(SqBiTree T,TElemtype e)
  341. {
  342.     int i;
  343.     if(BiTreeEmpty(T))
  344.     {
  345.         return Nil;
  346.     }
  347.     for(i=0;i<MAX_TREE_SIZE;i++)
  348.     {
  349.         if(T[i]==e)
  350.         {
  351.             return T[2*i+2]; 
  352.         }
  353.     }
  354.     printf("未找到右孩子.\n");
  355.     return Nil;
  356. } 
  358. /*获取结点元素的左兄弟*/ 
  359. TElemtype GetLeftSibling(SqBiTree T,TElemtype e)
  360. {
  361.     int i;
  362.     if(BiTreeEmpty(T))
  363.     {
  364.         return Nil;
  365.     }
  366.     for(i=1;i<MAX_TREE_SIZE;i++)
  367.     {
  368.         if(T[i]==e&&i%2==0)
  369.         {
  370.             return T[i-1];
  371.         }
  372.     }
  373.     printf("未找到左兄弟.\n");
  374.     return Nil;
  375. }
  377. /*获取结点元素的右兄弟*/ 
  378. TElemtype GetRightSibling(SqBiTree T,TElemtype e)
  379. {
  380.     int i;
  381.     if(BiTreeEmpty(T))
  382.     {
  383.         return Nil;
  384.     }
  385.     for(i=1;i<MAX_TREE_SIZE;i++)
  386.     {
  387.         if(T[i]==e&&i%2!=0)
  388.         {
  389.             return T[i+1];
  390.         }
  391.     }
  392.     printf("未找到右兄弟.\n");
  393.     return Nil;
  394. }
  396. /*把从T1中j结点开始的子树移到T2中i结点开始的子树*/ 
  397. void Move(SqBiTree T1,int i1,SqBiTree T2,int i2)
  398. {
  399.     if(T1[2*i1+1] != Nil)
  400.     {
  401.    /*左子树不空*/
  402.         Move(T1,2*i1+1,T2,2*i2+1);
  403.     }
  404.     if(T1[2*i1+2] != Nil)
  405.     {
  406.    /*右子树不空*/
  407.         Move(T1,2*i1+2,T2,2*i2+2);    
  408.     }
  409.     /*左右子树都为空,说明该结点为叶子结点,可以移动.*/
  410.     T2[i2]=T1[i1];
  411.     T1[i1]=Nil;
  412. }
  414. /*插入结点或子树*/ 
  415. int InsertChild(SqBiTree T,TElemtype e,int LR,SqBiTree S)
  416. {
  417.     int j,k,i=0;
  418.     if(BiTreeEmpty(T))
  419.     {
  420.         return ERROR;
  421.     }
  422.     for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++)
  423.     {
  424.         if(T[j]==e)
  425.         {
  426.             break;
  427.         }
  428.     }
  429.     k=2*j+LR;    //k为e结点的左或右孩子的序号
  430.      if(T[k]!=Nil)
  431.      {
  432.    /*e结点的左右孩子不空,即e结点不是叶子结点*/
  433.         Move(T,k,T,2*k+2);     
  434.     }
  435.     Move(S,i,T,k); 
  436. } 
  438. /*删除结点或子树*/ 
  439. int DeleteChild(SqBiTree T,position p,int LR)
  440. {
  441.     int i;
  442.     int k=OK;
  443.     SqQueue Q;
  444.     InitQueue(&Q);
  445.     i=(int)pow(2,p.level)-1-(int)pow(2,p.level-1)+p.order-1;
  446.     if(BiTreeEmpty(T))
  447.     {
  448.         return ERROR;
  449.     }
  450.     i=2*i+1+LR;
  451.     while(k)
  452.     {
  453.         if(T[2*i+1]!=Nil)
  454.         {
  455.             EnterQueue(&Q,2*i+1);
  456.         }
  457.         if(T[2*i+2]!=Nil)
  458.         {
  459.             EnterQueue(&Q,2*i+2);
  460.         }
  461.         T[i]=Nil;
  462.         k=DeleteQueue(&Q,&i);
  463.     }
  464.     return OK;
  465. }
  467. /*访问结点元素的函数*/ 
  468. int TreeVisitFunc(TElemtype e)
  469. {
  470.     printf(" %c -",e);
  471. }
  473. /*先序遍历二叉树的递归函数*/ 
  474. int PreTraverse(SqBiTree T,int i)
  475. {
  476.     TreeVisit(T[i]);
  477.     if(T[2*i+1]!=Nil)
  478.     {
  479.         PreTraverse(T,2*i+1);
  480.     }
  481.     if(T[2*i+2]!=Nil)
  482.     {
  483.         PreTraverse(T,2*i+2);
  484.     }
  485. }
  487. /*先序遍历二叉树*/ 
  488. int PreOrderTraverse(SqBiTree T,int (*TV) (TElemtype e))
  489. {
  490.     TreeVisit=TV;
  491.     if(BiTreeEmpty(T))
  492.     {
  493.         return ERROR;
  494.     }
  495.     PreTraverse(T,0);
  496. }
  498. /*中序遍历二叉树的递归函数*/ 
  499. int InTraverse(SqBiTree T,int i)
  500. {
  501.     if(T[2*i+1]!=Nil)
  502.     {
  503.         InTraverse(T,2*i+1);
  504.     }
  505.     TreeVisit(T[i]);
  506.     if(T[2*i+2]!=Nil)
  507.     {
  508.         InTraverse(T,2*i+2);
  509.     }
  510. }
  512. /*中序遍历二叉树*/
  513. int InOrderTraverse(SqBiTree T,int (*TV)(TElemtype))
  514. {
  515.     TreeVisit=TV;
  516.     if(BiTreeEmpty(T))
  517.     {
  518.         return ERROR;
  519.     }
  520.     InTraverse(T,0);
  521. }
  523. /*后序遍历二叉树的递归函数*/
  524. int PostTraverse(SqBiTree T,int i)
  525. {
  526.     if(T[2*i+1]!=Nil)
  527.     {
  528.         PostTraverse(T,2*i+1);
  529.     }
  530.     if(T[2*i+2]!=Nil)
  531.     {
  532.         PostTraverse(T,2*i+2);
  533.     }
  534.     TreeVisit(T[i]);
  535. }
  537. /*后序遍历二叉树*/
  538. int PostOrderTraverse(SqBiTree T,int (*TV)(TElemtype))
  539. {
  540.     TreeVisit=TV;
  541.     if(BiTreeEmpty(T))
  542.     {
  543.         return ERROR;
  544.     }
  545.     PostTraverse(T,0);
  546. }
  548. /*打印树*/ 
  549. void PrintTree(SqBiTree T)
  550. {
  551.     int j,k;
  552.     position p;
  553.     TElemtype e;
  554.     for(j=0;j<BiTreeDepth(T);j++)
  555.     {
  556.         p.level=j+1;
  557.         printf("第%d层:\n",p.level);
  558.         for(k=0;k<pow(2,p.level-1);k++)
  559.         {
  560.             p.order=k+1;
  561.             e=T[(int)pow(2,p.level)-1-(int)pow(2,p.level-1)+p.order-1];
  562.             printf(" %d : %c ",p.order,e);
  563.         }
  564.         printf("\n");
  565.     }
  566.     printf("\n");
  567. }
  569. /*程序入口函数,对二叉树及队列的操作的调用*/ 
  570. int main()
  571. {
  572.     /*
  573.     SqQueue queue;
  574.     InitQueue(&queue);
  575.     QueueEmpty(&queue);
  576.     ClearQueue(&queue);
  577.     QueueEmpty(&queue);
  578.     int length;
  579.     length = GetQueueLength(&queue);
  580.     printf("队列长度为: %d\n",length);
  581.     if(1==OK)
  582.     {
  583.         printf("-----------------------------\n\n");
  584.     }
  585.     EnterQueue(&queue,1);
  586.     EnterQueue(&queue,2);
  587.     EnterQueue(&queue,3);
  588.     EnterQueue(&queue,4);
  589.     EnterQueue(&queue,5);
  590.     QueueEmpty(&queue);
  591.     length=GetQueueLength(&queue);
  592.     printf("The Length of the Queue is : %d.\n",length);
  593.     QElemType headElem;
  594.     if(GetQueueHead(&queue,&headElem))
  595.     {
  596.         printf("The Head of the Queue is : %d.\n",headElem);
  597.     }
  598.     QueueVisit=QueueVisitFunc;
  599.     QueueTraverse(&queue,QueueVisit);
  600.     printf("销毁队列.\n");
  601.     DestroyQueue(&queue);
  602.     */
  604.     position p;
  605.     SqBiTree T;
  606.     SqBiTree S;
  607.     int depth;
  608.     int i;
  609.     TElemtype elem;
  610.     InitBiTree(T);
  611.     BiTreeEmpty(T);
  612.     CreateBiTree(T);
  613.     puts(T);
  614.     depth=BiTreeDepth(T);
  615.     printf("The Depth of the tree is %d.\n",depth);
  618.     GetRoot(T,&elem);
  619.     printf("The Root of the tree is %c.\n",elem);/*
  621.     printf("Please Enter the Level and Order of the Tree:\n");
  622.     scanf("%d",&p.level);
  623.     scanf("%d",&p.order);
  624.     fflush(stdin);
  625.     elem=GetNodeValue(T,p);
  626.     printf("The Node of level %d order %d is : %c \n",p.level,p.order,elem);
  627.     Assign(T,p,'C');*/
  628.     printf("--------------------------------\n\n");
  629. /*
  630.     printf("输入一个结点的值,我们可以找到其双亲,孩子和兄弟.\n");
  631.     scanf("%c",&elem);
  632.     fflush(stdin);
  633.     printf("%c 's parent is : %c.\n",elem,GetParent(T,elem));
  634.     printf("%c 's left child is : %c.\n",elem,GetLeftChild(T,elem));
  635.     printf("%c 's right child is : %c.\n",elem,GetRightChild(T,elem));
  636.     printf("%c 's left sibling is : %c.\n",elem,GetLeftSibling(T,elem));
  637.     printf("%c 's right sibling is : %c.\n",elem,GetRightSibling(T,elem));*/
  639.     printf("----------------------------------\n\n");
  640.     /*
  641.     InitBiTree(S);
  642.     CreateBiTree(S);
  643.     printf("Please enter the node value where you want to insert a child.\n");
  644.     scanf("%c",&elem);
  645.     InsertChild(T,elem,1,S);
  646.     puts(T);
  647.     printf("Please enter the node position you want to delete.\n");
  648.     scanf("%d%d",&p.level,&p.order);
  649.     printf("p.level=%d,p.order=%d\n",p.level,p.order);
  650.     DeleteChild(T,p,0);
  651.     puts(T);
  652.     */
  653.     printf("--------------遍历二叉树--------------------\n\n");
  654.     printf("先序遍历:\n");
  655.     PreOrderTraverse(T,TreeVisitFunc);
  656.     printf("\n中序遍历:\n");
  657.     InOrderTraverse(T,TreeVisitFunc);
  658.     printf("\n后序遍历:\n");
  659.     PostOrderTraverse(T,TreeVisitFunc);
  660.     printf("\n");
  661.     printf("--------------打印二叉树--------------------\n\n");
  662.     PrintTree(T); 
  663. }

发表评论

表情：
评论列表 （有 0 条评论，303人围观）

还没有评论，来说两句吧...

相关阅读