链式二叉树遍历具体程序演示

1437阅读　0评论2012-08-25　高傲的活着
分类：C/C++

点击(此处)折叠或打开

  1. 二叉树操作
  2.                 遍历
  3.                       
  4.                       先序遍历【先访问根节点】
  5.                               先访问根节点
  6.                               再先序访问左子树
  7.                               再先序访问右子树
  8.                       
  9.                       中序遍历【中间访问根节点】
  10.                               中序遍历左子树
  11.                               再访问根节点
  12.                               再中序遍历右子树
  13.                               
  14.                       后序遍历【最后访问根节点】
  15.                               先后序遍历左子树
  16.                               再后序遍历右子树
  17.                               再访问根节点

点击(此处)折叠或打开

  1. 链式二叉树.cpp
  2. --------------------------------------
  3. #include <stdio.h>
  4. #include <malloc.h>
  5. typedef struct BTNode
  6. {
  7.      char data;
  8.      struct BTNode * pLchild;
  9.      struct BTNode * pRchild;
  10. }BTNode;

  12. BTNode * CreateBTree(void);
  13. void PreTraverseBTree(BTNode *);
  14. void InTraverseBTree(BTNode *);
  15. void PostTraverseBTree(BTNode *);
  16. int main()
  17. {
  18.     BTNode * pT = CreateBTree();
  19.     //PreTraverseBTree(pT);
  20.     //InTraverseBTree(pT);
  21.     PostTraverseBTree(pT);

  23.     return 0;
  24. }

  26. BTNode * CreateBTree(void)
  27. {
  28.    BTNode * pA = (BTNode *)malloc(sizeof(BTNode));
  29.    BTNode * pB = (BTNode *)malloc(sizeof(BTNode));
  30.    BTNode * pC = (BTNode *)malloc(sizeof(BTNode));
  31.    BTNode * pD = (BTNode *)malloc(sizeof(BTNode));
  32.    BTNode * pE = (BTNode *)malloc(sizeof(BTNode));
  33.     
  34.    pA->data = 'A';
  35.    pB->data = 'B';
  36.    pC->data = 'C';
  37.    pD->data = 'D';
  38.    pE->data = 'E';
  39.     
  40.    pA->pLchild = pB;
  41.    pA->pRchild = pC;
  42.    pB->pLchild = pB->pRchild = NULL;
  43.    pC->pLchild = pD;
  44.    pC->pRchild =NULL;
  45.    pD->pLchild =NULL;
  46.    pD->pRchild =pE;
  47.    pE->pLchild = pE->pRchild = NULL;

  49.    return pA;
  50. }

  52. void PreTraverseBTree(BTNode * pT)
  53. {
  54.      if (NULL!=pT)
  55.      {
  56.          printf("%c\n",pT->data);
  57.     
  58.      if (NULL!=pT->pLchild)
  59.          {
  60.          PreTraverseBTree(pT->pLchild); //pLchild代表整个左子树
  61.          }
  62.      if (NULL!=pT->pRchild)
  63.          {
  64.          PreTraverseBTree(pT->pRchild);
  65.          }
  66.      }
  67. }

  69. void InTraverseBTree(BTNode * pT)
  70. {
  71.     if (NULL!=pT)
  72.     {
  73.      if (NULL!=pT->pLchild)
  74.      {
  75.          InTraverseBTree(pT->pLchild); //pLchild代表整个左子树
  76.      }
  77.        
  78.      printf("%c\n",pT->data);

  80.      if (NULL!=pT->pRchild)
  81.      {
  82.          InTraverseBTree(pT->pRchild);
  83.      }
  84.     }
  85. }

  87. void PostTraverseBTree(BTNode * pT)
  88. {
  89.     if (NULL!=pT)
  90.     {
  91.      if (NULL!=pT->pLchild)
  92.      {
  93.          PostTraverseBTree(pT->pLchild); //pLchild代表整个左子树
  94.      }

  96.      if (NULL!=pT->pRchild)
  97.      {
  98.         PostTraverseBTree(pT->pRchild);
  99.      }
  100.      printf("%c\n",pT->data);
  101.     }
  102. }
上一篇：堆与栈的区别
下一篇：java 集合ArrayList及LinkList源码分析