实验八、数据结构之二叉树用非递归方法遍历二叉树 C语言版

布满荆棘的人生 2023-06-11 03:21 13阅读 0赞

1. 题目：

![20191028203651461.png][]

用给递归方法遍历二叉树。

2. 实验过程及结果：

得到需要输入的二叉树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70][]

那么，**按先序序列输入二叉树的时候**，需要输入: ab\#d\#\#c\#e\#\# (注意，输入后，按enter键即可)

实验结果：

![2019102817101270.png][]

3. 源代码：

注：递归方法的代码如下，如果要改为非递归的，可以查看实验六博文：

[https://blog.csdn.net/sinat\_29891353/article/details/102747205][https_blog.csdn.net_sinat_29891353_article_details_102747205]

或者把\#define NORECURSIVE这一行注释掉皆可。

1 #include <stdio.h>
      2 #include <stdlib.h>
      3 
      4 typedef struct Binnode
      5 {
      6     char data;
      7     struct Binnode *lchild;
      8     struct Binnode *rchild;
      9 } Binnode, *Bintree;
     10 
     11 typedef struct {
     12     Bintree link;
     13     int flag;
     14 }stacktype;
     15 #define MAXNODE 100
     16 #define NORECURSIVE
     17 void Create_Bintree(Bintree *root)
     18 {
     19     char ch;
     20 
     21     if ((ch = getchar()) == '#') {
     22         *root = NULL;
     23     } else {
     24         *root = (Binnode *)malloc(sizeof(Binnode));
     25         (*root)->data = ch;
     26         Create_Bintree(&(*root)->lchild);
     27         Create_Bintree(&(*root)->rchild);
     28     }
     29 }
     30 
     31 void Preorder(Bintree *t)
     32 {
     33 #ifdef  NORECURSIVE
     34     Bintree stack[MAXNODE], p;
     35     int top;
     36     if (*t == NULL)
     37       return;
     38     top = 0;
     39     p = *t;
     40     while(!(p == NULL && top == 0)){
     41         while(p != NULL){
     42             printf("%c", p->data); //访问节点的数据域
     43             if (top<(MAXNODE-1)){  //将当前指针p入栈
     44                 stack[top] = p;
     45                 top++;
     46             } else {
     47                 printf("error\n");
     48                 return;
     49             }
     50             p = p->lchild;         //指向p的左孩子
     51         }
     52         if (top <= 0)
     53           return;                  //栈空时结束
     54         else {
     55             top--;
     56             p = stack[top];        //从栈中弹出栈顶元素
     57             p = p->rchild;         //指针指向p的右孩子节点
     58         }
     59     }
     60 #else
     61     if (*t != NULL){
     62         printf("%c", ((*t)->data));
     63         Preorder(&(*t)->lchild);
     64         Preorder(&(*t)->rchild);
     65     }
     66 #endif
     67 }
     68 
     69 void Inorder(Bintree *t)
     70 {
     71 #ifdef  NORECURSIVE
     72     Bintree stack[MAXNODE], p;
     73     int top;
     74     if (*t == NULL)
     75       return;
     76     top = 0;
     77     p = *t;
     78     while(!(p == NULL && top == 0)){
     79         while(p != NULL){
     80             if (top<(MAXNODE-1)){
     81                 stack[top] = p;
     82                 top++;
     83             } else {
     84                 printf("error\n");
     85                 return;
     86             }
     87             p = p->lchild;
     88         }
     89         if (top <= 0){
     90           return;
     91         } else {
     92             top--;
     93             p = stack[top];
     94             printf("%c", p->data);
     95             p = p->rchild;
     96         }
     97     }
     98 #else
     99     if (*t != NULL){
    100         Inorder(&(*t)->lchild);
    101         printf("%c", (*t)->data);
    102         Inorder(&(*t)->rchild);
    103     }
    104 #endif
    105 }
    106 
    107 void Posorder(Bintree *t)
    108 {
    109 #ifdef NORECURSIVE
    110     stacktype stack[MAXNODE];
    111     Bintree p;
    112     int top, sign;
    113     if (*t == NULL)
    114       return;
    115     top = -1;                           //栈顶位置初始化
    116     p = *t;
    117     while (!(p == NULL && top == -1)){
    118         if (p != NULL){
    119             top++;                      //节点第一次进栈
    120             stack[top].link = p;
    121             stack[top].flag = 1;
    122             p = p->lchild;              //找该节点的左节点
    123         } else {
    124             p = stack[top].link;
    125             sign = stack[top].flag;
    126             top--;
    127             if (sign == 1){             //节点第二次进栈
    128                 top++;
    129                 stack[top].link = p;
    130                 stack[top].flag = 2;    //标记第二次出栈
    131                 p = p->rchild;
    132             } else {
    133                 printf("%c", p->data);  //访问该节点数据阈值
    134                 p = NULL;
    135             }
    136         }
    137     }
    138 #else
    139     if (*t != NULL){
    140         Posorder(&(*t)->lchild);
    141         Posorder(&(*t)->rchild);
    142         printf("%c", (*t)->data);
    143     }
    144 #endif
    145 }
    146 
    147 int main()
    148 {
    149     Bintree T;
    150     printf("Tree Create Start!\n");
    151     Create_Bintree(&T);
    152     printf("Tree Create OK!\n");
    153     printf("先序遍历:\n");
    154     Preorder(&T);
    155     printf("\n中序遍历:\n");
    156     Inorder(&T);
    157     printf("\n后序遍历:\n");
    158     Posorder(&T);
    159     printf("\n");
    160     return 0;
    161 }

[20191028203651461.png]: /images/20230531/62fb9163e7fb4a6fa2a72e5af71373d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzI5ODkxMzUz_size_16_color_FFFFFF_t_70]: /images/20230531/9044ac26e90442bfbb0531357020e740.png
[2019102817101270.png]: /images/20230531/d2ad79badf014082b3e3ade191fce157.png
[https_blog.csdn.net_sinat_29891353_article_details_102747205]: https://blog.csdn.net/sinat_29891353/article/details/102747205