二叉树的创建+递归遍历+非递归遍历

落日映苍穹つ 2022-05-19 01:58 398阅读 0赞 
  1. #include<iostream>
  2. #include<stdlib.h>
  3. #define MAXSIZE 100
  4. typedef char ElementType; 
  5. using namespace std;
  7. typedef struct BTNode{
  8.     ElementType data;
  9.     struct BTNode *lChild;
  10.     struct BTNode *rChild;
  11. }BTNode;
  12. void createBinaryTree(BTNode *&bt)
  13. {
  14.     ElementType data;
  15.     bt = (BTNode *)malloc(sizeof(BTNode));
  16.     cin>>data;
  17.     if(data == '#')
  18.     {
  19.         bt = NULL;
  20.     }
  21.     else
  22.     {
  23.         bt->data = data;
  24.         createBinaryTree(bt->lChild);
  25.         createBinaryTree(bt->rChild);
  26.     }
  27. }
  28. void preOrderRecursionVisit(BTNode *bt)
  29. {
  30.     if(bt == NULL)
  31.         return;
  32.     else
  33.     {
  34.         cout<<bt->data<<" ";
  35.         preOrderRecursionVisit(bt->lChild);
  36.         preOrderRecursionVisit(bt->rChild);
  37.     }
  38. }
  40. void preOrderNonRecursionVisit(BTNode *bt)
  41. {
  42.     if(bt == NULL)
  43.         return;
  44.     BTNode *stack[MAXSIZE], *tNode;
  45.     int top = -1;
  46.     stack[++top] = bt;
  47.     while(top != -1)
  48.     {
  49.         tNode = stack[top--];
  50.         cout<<tNode->data<<" ";
  51.         if(tNode->rChild != NULL)
  52.             stack[++top] = tNode->rChild;
  53.         if(tNode->lChild != NULL)
  54.             stack[++top] = tNode->lChild;
  55.     }
  56.     cout<<endl; 
  57. }
  59. void inOrderRecursionVisit(BTNode *bt)
  60. {
  61.     if(bt == NULL)
  62.         return;
  63.     else
  64.     {
  65.         inOrderRecursionVisit(bt->lChild);
  66.         cout<<bt->data<<" ";
  67.         inOrderRecursionVisit(bt->rChild);
  68.     }
  69. }
  70. void inOrderNonRecursionVisit(BTNode *bt)
  71. {
  72.     if(bt == NULL)
  73.         return;
  74.     BTNode *stack[MAXSIZE], *tNode;
  75.     int top = -1;
  76.     tNode = bt;
  77.     while(top != -1 || tNode != NULL)
  78.     {
  79.         while(tNode != NULL)
  80.         {
  81.             stack[++top] = tNode; 
  82.             tNode = tNode->lChild; 
  83.         }
  84.         if(top != -1)
  85.         {
  86.             tNode = stack[top--];
  87.             cout<<tNode->data<<" ";
  88.             if(tNode->rChild != NULL)
  89.                 tNode = tNode->rChild;
  90.             else
  91.                 tNode = NULL;
  92.         }
  93.     }
  94.     cout<<endl; 
  95. } 
  98. void postOrderRecursionVisit(BTNode *bt)
  99. {
  100.     if(bt == NULL)
  101.         return;
  102.     else
  103.     {
  104.         postOrderRecursionVisit(bt->lChild);
  105.         postOrderRecursionVisit(bt->rChild);
  106.         cout<<bt->data<<" ";
  107.     }
  108. }
  109. void postOrderNonRecursionVisit(BTNode *bt)
  110. {
  111.     if(bt == NULL)
  112.         return;
  114.     BTNode *tNode, *stack1[MAXSIZE], *stack2[MAXSIZE];
  115.     int top1 = -1, top2 = -1;
  116.     stack1[++top1] = bt;
  117.     while(top1 != -1)
  118.     {
  119.         tNode = stack1[top1--];
  120.         stack2[++top2] = tNode;
  121.         if(tNode->lChild != NULL)
  122.             stack1[++top1] = tNode->lChild;
  123.         if(tNode->rChild != NULL)
  124.             stack1[++top1] = tNode->rChild;
  125.     }
  126.     while(top2 != -1)
  127.     {
  128.         tNode = stack2[top2--];
  129.         cout<<tNode->data<<" ";
  130.     }
  131.     cout<<endl;
  132. }
  133. int main()
  134. {
  135.     BTNode *bt = NULL;
  136.     //124##57##8##3#69###
  137.     createBinaryTree(bt);
  138.     preOrderRecursionVisit(bt);
  139.     cout<<endl; 
  140.     preOrderNonRecursionVisit(bt);
  142.     inOrderRecursionVisit(bt);
  143.     cout<<endl;
  144.     inOrderNonRecursionVisit(bt);
  145.     postOrderRecursionVisit(bt);
  146.     cout<<endl;
  147.     postOrderNonRecursionVisit(bt);
  149. }

发表评论

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

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

相关阅读