小白对二叉树非递归中序遍历的若干问题

仓鼠爱跑圈

最近在学习二叉树非递归中序遍历，盗来的代码如下：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define A 100      //栈的空间初始分配大小
   
4. 
   
5. typedef struct BiNode{   //定义二叉链表
   
6.         char data;
   
7.         struct BiNode *lchild,*rchild;
   
8. }BiNode,*BiTree;                           //BiNode->struct BiNode      BiTree-> struct BiNode *    -> BiTree * 双重指针
   
9. 
   
10. typedef struct{ //定义栈
    
11.         BiTree *base;
    
12.         BiTree *top;
    
13.         int stacksize;//分配的存储空间的大小
    
14. }Sqstack;                   //Sqstack->struct
    
15. 
    
16. void initstack(Sqstack *S)  //初始化栈
    
17. {
    
18.         S->base=(BiTree* )malloc(sizeof(A))        ;
    
19.         S->top=S->base;
    
20.         S->stacksize=A;
    
21. }
    
22. 
    
23. int emptystack(Sqstack* S) //判断栈是否为空，若为空则返回1
    
24. {
    
25.         if(S->base!=S->top)
    
26.         {
    
27.                 return 0;
    
28.         }
    
29.         else
    
30.         {
    
31.                 return 1;
    
32.         }
    
33. }
    
34. 
    
35. 
    
36. void push(Sqstack *S,BiTree e)  //将元素进栈  这里e不用指针->因为不用返回e，而是输入e
    
37. {
    
38.         if(S->top-S->base==S->stacksize)
    
39.         {
    
40.                 printf("此时栈满，不能插入啦。\n");
    
41.         }
    
42.         else
    
43.         {
    
44.                 *(S->top)=e;
    
45.                 (S->top)++;
    
46.         }
    
47. }
    
48. 
    
49. 
    
50. void pop(Sqstack *S,BiTree *e)  //将元素出栈    这里e要用指针->因为出栈有返回栈顶
    
51. {
    
52.         if(S->base==S->top)
    
53.         {
    
54.                 printf("为空，不能弹出\n");
    
55.         }
    
56.         else
    
57.         {
    
58.                 S->top--;
    
59.                 *e=*(S->top);
    
60.         }
    
61. }
    
62. 
    
63. void initBitree(BiTree *T)   //初始化树，即建造一棵空树   * 用来返回值
    
64. {
    
65.         *T=NULL;
    
66.         printf("空树构造成功。\n");
    
67. }
    
68. 
    
69. 
    
70. void CreatBitree(BiTree* T) //先序建立一个二叉树   *用来返回值   *T仍然是一个指针->因为BiTree本身是一个指针类型
    
71. {
    
72.         char c;
    
73.         scanf("%c",&c);
    
74.         if(c=='*')
    
75.         {
    
76.                 *T=NULL;
    
77.         }
    
78.         else
    
79.         {
    
80.                 *T=(BiTree)malloc(sizeof(BiNode));
    
81.                 (*T)->data=c;//生成的根节点里输入数据
    
82.                 CreatBitree(&(*T)->lchild);  //递归创建左子树
    
83.                 CreatBitree(&(*T)->rchild);  //递归创建右子树
    
84.         }
    
85. }
    
86. 
    
87. void inorderbitree(BiTree T)  //中序遍历，非递归    没有改变树的结构 没必要用指针
    
88. {
    
89.         BiTree p=T;
    
90.         Sqstack S;
    
91.         initstack(&S);//初始化栈，构造结点
    
92.         while(p||!emptystack(&S))
    
93.         {
    
94.                 if(p)         //一直遍历到左子树的最下边 便遍历边入栈
    
95.                 {
    
96.                         push(&S,p);
    
97.                         p=p->lchild;
    
98.                 }
    
99.                 else         //当p为空时，说明已经到达左子树最下边，此时需要出栈，并打印该结点
    
100.                 {
     
101.                         pop(&S,&p);
     
102.                         printf("%c",p->data);
     
103.                         p=p->rchild;  //进入右子树
     
104.                 }
     
105.         }
     
106. }
     
107. 
     
108. 
     
109. 
     
110. 
     
111. int main()
     
112. {
     
113.         BiTree T;
     
114.         printf("先序创建一个二叉树：\n");
     
115.         CreatBitree(&T);
     
116.         printf("该二叉树的中序遍历结果为：");
     
117.         inorderbitree(T);
     
118.         printf("\n");
     
119.         return 0;
     
120. }
     
121. 
     

复制代码

上面是一个可执行的代码，我自己加了点注释，不知对否。接下来我的问题如下：

①inorderbitree函数为什么不能改为如下代码：

1. void inorderbitree(BiTree T)  //中序遍历，非递归    没有改变树的结构 没必要用指针
   
2. {
   
3.         BiTree p=T;
   
4.         Sqstack *S=NULL;
   
5.         initstack(S);//初始化栈，构造结点
   
6.         while(p||!emptystack(S))
   
7.         {
   
8.                 if(p)         //一直遍历到左子树的最下边 便遍历边入栈
   
9.                 {
   
10.                         push(S,p);
    
11.                         p=p->lchild;
    
12.                 }
    
13.                 else         //当p为空时，说明已经到达左子树最下边，此时需要出栈，并打印该结点
    
14.                 {
    
15.                         pop(S,&p);
    
16.                         printf("%c",p->data);
    
17.                         p=p->rchild;  //进入右子树
    
18.                 }
    
19.         }
    
20. }
    

复制代码

即把S定义为Sqstack类型的指针，这样的话在调用函数的时候可以直接写S而不是&S。但是不能成功运行，为何？


②CreatBitree函数中的scanf是如何做到直接输入一行字符便可执行，而不是需要输入一个字符按一次回车？（是不是和递归有关？本人对递归不是很了解。。）


本人小白，最近因为比较忙对学习一直朝三暮四，但会尽快恢复状态。如果我的问题有蠢到各位或者有哪些知识点没有学好的地方，恳请各位指正！
在这里先谢谢各位dalao！如有更好的学习建议请各位指出！

PS：严蔚敏的数据结构太晦涩难懂了。

人造人

PS：严蔚敏的数据结构的确太晦涩难懂了，不适合自学，推荐一个适合自学的《大话数据结构》
^_^

仓鼠爱跑圈

人造人 发表于 2018-5-20 02:11
PS：严蔚敏的数据结构的确太晦涩难懂了，不适合自学，推荐一个适合自学的《大话数据结构》
^_^

谢谢dalao，那我那个想法有错吗，如果没错的话该怎么用指针定义S呢。我是看到他报错说没有初始化，我才把他NULL。。

人造人

仓鼠爱跑圈 发表于 2018-5-20 08:11
谢谢dalao，那我那个想法有错吗，如果没错的话该怎么用指针定义S呢。我是看到他报错说没有初始化，我才把 ...

没有仔细看你的程序，这样应该可以，至少调试没有报错

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define A 100                        // 栈的空间初始分配大小
   
4. 
   
5. // 定义二叉链表
   
6. typedef struct BiNode
   
7. {
   
8.         char data;
   
9.         struct BiNode *lchild, *rchild;
   
10. }BiNode, *BiTree;
    
11. 
    
12. // 定义栈
    
13. typedef struct
    
14. {
    
15.         BiTree *base;
    
16.         BiTree *top;
    
17.         int stacksize;                // 分配的存储空间的大小
    
18. }Sqstack;
    
19. 
    
20. int emptystack(Sqstack* S)        // 判断栈是否为空，若为空则返回1
    
21. {
    
22.         if(S->base != S->top)
    
23.         {
    
24.                 return 0;
    
25.         }
    
26.         else
    
27.         {
    
28.                 return 1;
    
29.         }
    
30. }
    
31. 
    
32. void push(Sqstack *S, BiTree e)                // 将元素进栈  这里e不用指针->因为不用返回e，而是输入e
    
33. {
    
34.         if(S->top - S->base == S->stacksize)
    
35.         {
    
36.                 printf("此时栈满，不能插入啦。\n");
    
37.         }
    
38.         else
    
39.         {
    
40.                 *(S->top) = e;
    
41.                 (S->top)++;
    
42.         }
    
43. }
    
44. 
    
45. void pop(Sqstack *S, BiTree *e)                // 将元素出栈    这里e要用指针->因为出栈有返回栈顶
    
46. {
    
47.         if(S->base == S->top)
    
48.         {
    
49.                 printf("为空，不能弹出\n");
    
50.         }
    
51.         else
    
52.         {
    
53.                 S->top--;
    
54.                 *e = *(S->top);
    
55.         }
    
56. }
    
57. 
    
58. void initBitree(BiTree *T)                // 初始化树，即建造一棵空树   * 用来返回值
    
59. {
    
60.         *T = NULL;
    
61.         printf("空树构造成功。\n");
    
62. }
    
63. 
    
64. void CreatBitree(BiTree* T)                // 先序建立一个二叉树   *用来返回值   *T仍然是一个指针->因为BiTree本身是一个指针类型
    
65. {
    
66.         char c;
    
67.         scanf("%c", &c);
    
68.         if(c == '*')
    
69.         {
    
70.                 *T = NULL;
    
71.         }
    
72.         else
    
73.         {
    
74.                 *T = (BiTree)malloc(sizeof(BiNode));
    
75.                 (*T)->data = c;                                // 生成的根节点里输入数据
    
76.                 CreatBitree(&(*T)->lchild);                // 递归创建左子树
    
77.                 CreatBitree(&(*T)->rchild);                // 递归创建右子树
    
78.         }
    
79. }
    
80. 
    
81. void initstack(Sqstack *S);
    
82. void inorderbitree(BiTree T)                // 中序遍历，非递归    没有改变树的结构 没必要用指针
    
83. {
    
84.         BiTree p = T;
    
85.         Sqstack S;
    
86.         initstack(&S);                        // 初始化栈，构造结点
    
87.         while(p || !emptystack(&S))
    
88.         {
    
89.                 if(p)                        // 一直遍历到左子树的最下边 便遍历边入栈
    
90.                 {
    
91.                         push(&S, p);
    
92.                         p = p->lchild;
    
93.                 }
    
94.                 else                        // 当p为空时，说明已经到达左子树最下边，此时需要出栈，并打印该结点
    
95.                 {
    
96.                         pop(&S, &p);
    
97.                         printf("%c", p->data);
    
98.                         p = p->rchild;        // 进入右子树
    
99.                 }
    
100.         }
     
101. }
     
102. 
     
103. void initstack(Sqstack *S)        // 初始化栈
     
104. {
     
105.         S->base = (BiTree*)malloc(sizeof(A));
     
106.         S->top = S->base;
     
107.         S->stacksize = A;
     
108. }
     
109. 
     
110. void initstack_ptr1(Sqstack **S)        // 初始化栈
     
111. {
     
112.         (*S) = malloc(sizeof(Sqstack));
     
113. 
     
114.         (*S)->base = (BiTree*)malloc(sizeof(A));
     
115.         (*S)->top = (*S)->base;
     
116.         (*S)->stacksize = A;
     
117. }
     
118. 
     
119. Sqstack *initstack_ptr2(void)        // 初始化栈
     
120. {
     
121.         Sqstack *s = malloc(sizeof(Sqstack));
     
122. 
     
123.         s->base = (BiTree*)malloc(sizeof(A));
     
124.         s->top = s->base;
     
125.         s->stacksize = A;
     
126.         return s;
     
127. }
     
128. int main(void)
     
129. {
     
130.         Sqstack S;
     
131.         initstack(&S);
     
132. 
     
133.         Sqstack *S1;
     
134.         initstack_ptr1(&S1);
     
135.        
     
136.         Sqstack *S2 = initstack_ptr2();
     
137.        
     
138.         /*Sqstack *S1 = NULL;
     
139.         initstack(S1);*/
     
140. 
     
141.        
     
142.         return 0;
     
143. }
     

复制代码

刘亮

路过看看

qq171256018

很详细，不错哦

独吟月上

学习了

xy123963

学习学习

常德水鱼村

支持楼主！楼主加油！

钱闻韬

666

whdd

whdd

whdd

余生愿你常欢笑

学习

考拉熊

学习一下··

helloconan

占楼..