Chinaunix首页 | 论坛 | 博客
  • 博客访问: 35735
  • 博文数量: 24
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 246
  • 用 户 组: 普通用户
  • 注册时间: 2016-02-14 20:13
  • 认证徽章:
文章分类

全部博文(24)

文章存档

2017年(5)

2016年(19)

我的朋友

分类: C/C++

2016-04-08 15:30:57


  1. /*
  2.  * 根据郝斌老师视频整理
  3.  * 编译环境:
  4.  * guo@linux:~$ gcc --version
  5.  * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
  6.  * 静态二叉树
  7.  */
  8. #include <stdio.h>
  9. #include <malloc.h>

  10. struct BTNode
  11. {
  12.     int data;
  13.     struct BTNode *pLiftChild;
  14.     struct BTNode *pRightChild;
  15. };

  16. /**********************声明**********************************/
  17. /*创建一个静态二叉树*/
  18. struct BTNode *CreatBinaryTree(void);
  19. /*先序遍历输出*/
  20. void PreTraverseBinaryTree(struct BTNode *pT);
  21. /*中序遍历输出*/
  22. void InTraverseBinaryTree(struct BTNode *pT);
  23. /*后序遍历输出*/
  24. void PostTraverseBinaryTree(struct BTNode *pT);


  1. /*
  2.  * 函数名称:CreatBinaryTree。
  3.  * 输入参数:无。
  4.  * 输出参数:静态二叉树的根节点地址pA。
  5.  * 函数说明:新建一个静态二叉树。
  6.  */
  7. struct BTNode *CreatBinaryTree(void)
  8. {
  9.     struct BTNode *pA = (struct BTNode *)malloc(sizeof(struct BTNode));
  10.     struct BTNode *pB = (struct BTNode *)malloc(sizeof(struct BTNode));
  11.     struct BTNode *pC = (struct BTNode *)malloc(sizeof(struct BTNode));
  12.     struct BTNode *pD = (struct BTNode *)malloc(sizeof(struct BTNode));
  13.     struct BTNode *pE = (struct BTNode *)malloc(sizeof(struct BTNode));
  14.     struct BTNode *pF = (struct BTNode *)malloc(sizeof(struct BTNode));
  15.     struct BTNode *pL = (struct BTNode *)malloc(sizeof(struct BTNode));
  16.     struct BTNode *pM = (struct BTNode *)malloc(sizeof(struct BTNode));
  17.     struct BTNode *pN = (struct BTNode *)malloc(sizeof(struct BTNode));
  18.     struct BTNode *pQ = (struct BTNode *)malloc(sizeof(struct BTNode));

  19.     pA->data = 'A';
  20.     pB->data = 'B';
  21.     pC->data = 'C';
  22.     pD->data = 'D';
  23.     pE->data = 'E';
  24.     pF->data = 'F';
  25.     pL->data = 'L';
  26.     pM->data = 'M';
  27.     pN->data = 'N';
  28.     pQ->data = 'Q';

  29.     pA->pLiftChild = pB;
  30.     pA->pRightChild = pF;
  31.     pB->pLiftChild = NULL;
  32.     pB->pRightChild = pC;
  33.     pC->pLiftChild = pD;
  34.     pC->pRightChild = pE;
  35.     pD->pLiftChild = NULL;
  36.     pD->pRightChild = NULL;
  37.     pE->pLiftChild = NULL;
  38.     pE->pRightChild = NULL;
  39.     pF->pLiftChild = pL;
  40.     pF->pRightChild = pM;
  41.     pL->pLiftChild = NULL;
  42.     pL->pRightChild = NULL;
  43.     pM->pLiftChild = pN;
  44.     pM->pRightChild = NULL;
  45.     pN->pLiftChild = NULL;
  46.     pN->pRightChild = pQ;
  47.     pQ->pLiftChild = NULL;
  48.     pQ->pRightChild = NULL;

  49.     return pA;
  50. }

  51. /*
  52.  * 函数名称:PreTraverseBinaryTree。
  53.  * 输入参数:pT二叉树的根节点地址。
  54.  * 输出参数:无。
  55.  * 函数说明:先序遍历输出二叉树。
  56.  * 1. 先访问根节点
  57.  * 2. 再先序遍历左子树
  58.  * 3. 再先序遍历右子树
  59.  */
  60. void PreTraverseBinaryTree(struct BTNode *pT)
  61. {
  62.     if (NULL != pT)
  63.     {
  64.         printf("%c\n", pT->data);
  65.         if (NULL != pT->pLiftChild)
  66.         {
  67.             PreTraverseBinaryTree(pT->pLiftChild);
  68.         }
  69.         if (NULL != pT->pRightChild)
  70.         {
  71.             PreTraverseBinaryTree(pT->pRightChild);
  72.         }
  73.     }
  74.     
  75.     return ;
  76. }

  77. /*
  78.  * 函数名称:InTraverseBinaryTree。
  79.  * 输入参数:pT二叉树的根节点地址。
  80.  * 输出参数:无。
  81.  * 函数说明:中序遍历输出二叉树。
  82.  * 1. 先中序遍历左子树
  83.  * 2. 再访问根节点
  84.  * 3. 再中序遍历右子树
  85.  */
  86. void InTraverseBinaryTree(struct BTNode *pT)
  87. {
  88.     if (NULL != pT)
  89.     {
  90.         if (NULL != pT->pLiftChild)
  91.         {
  92.             InTraverseBinaryTree(pT->pLiftChild);
  93.         }
  94.         printf("%c\n", pT->data);
  95.         if (NULL !=pT->pRightChild)
  96.         {
  97.             InTraverseBinaryTree(pT->pRightChild);
  98.         }
  99.     }
  100. }

  101. /*
  102.  * 函数名称:PostTraverseBinaryTree。
  103.  * 输入参数:pT二叉树的根节点地址。
  104.  * 输出参数:无。
  105.  * 函数说明:后序遍历输出二叉树。
  106.  * 1. 先后序遍历左子树
  107.  * 2. 再后序遍历右子树
  108.  * 3. 再访问根节点
  109.  */
  110. void PostTraverseBinaryTree(struct BTNode *pT)
  111. {
  112.     if (NULL != pT)
  113.     {
  114.         if (NULL != pT->pLiftChild)
  115.         {
  116.             PostTraverseBinaryTree(pT->pLiftChild);
  117.         }
  118.         if (NULL != pT->pRightChild)
  119.         {
  120.             PostTraverseBinaryTree(pT->pRightChild);
  121.         }
  122.         printf("%c\n", pT->data);
  123.     }
  124. }


  125. int main(void)
  126. {
  127.     struct BTNode *pTree;

  128.     pTree = CreatBinaryTree();

  129.     printf("先序遍历输出:\n");
  130.     PreTraverseBinaryTree(pTree);

  131.     printf("中序遍历输出:\n");
  132.     InTraverseBinaryTree(pTree);

  133.     printf("后序遍历输出:\n");
  134.     PostTraverseBinaryTree(pTree);

  135.     return 0;
  136. }


阅读(594) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册