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

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

发表评论

表情:
评论列表 (有 0 条评论,302人围观)

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

相关阅读