二叉树三种非递归遍历的区别
1 #include <iostream>
2
3 #define MAXN 100
4 using namespace stbd;
5
6
7 struct BTNode
8 {
9 char tag;
10 BTNode *left;
11 BTNode *right;
12 };
13
14 class BTree
15 {
16 private:
17 BTNode **root;
18 void BuildBTree(BTNode **root);
19
20 public:
21 /*递归版本*/
22 void PreVisit(BTNode *root);
23 void InVisit(BTNode *root);
24 void PostVisit(BTNode *root);
25
26 /*非递归版本*/
27 void NR_PreVisit(BTNode *root);
28 void NR_InVisit(BTNode *root);
29 void NR_PostVisit(BTNode *root);
30
31 BTree(BTNode **r);
32 BTree();
33 };
34
35 BTree::BTree()
36 {
37
38 }
39
40 BTree::BTree(BTNode **r)
41 {
42 root = r;
43 /*
44 *root = new BTNode; 45 (*root)->left = NULL;
46 (*root)->right = NULL; 47 */
48 BuildBTree(root);
49 }
50
51 /*先序方式插入结点*/
52 void BTree::BuildBTree(BTNode **root)
53 {
54 char c;
55
56 c = getchar();
57 if(c == '#')
58 *root=NULL;
59 else{
60 *root = new BTNode;
61 (*root)->tag = c;
62 BuildBTree(&(*root)->left);
63 BuildBTree(&(*root)->right);
64 }
65 }
66
67 void BTree::PreVisit(BTNode *root)
68 {
69 if(root!=NULL)
70 {
71 printf("%c ", root->tag );
72 PreVisit(root->left);
73 PreVisit(root->right);
74 }
75 }
76
77 void BTree::InVisit(BTNode *root)
78 {
79 if(root!=NULL)
80 {
81 InVisit(root->left);
82 printf("%c ", root->tag );
83 InVisit(root->right);
84 }
85 }
86
87 void BTree::PostVisit(BTNode *root)
88 {
89 if(root!=NULL)
90 {
91 PostVisit(root->left);
92 PostVisit(root->right);
93 printf("%c ", root->tag );
94 }
95 }
96
97 void BTree::NR_PreVisit(BTNode *root)
98 {
99 BTNode *s[MAXN];
100 int top=0;
101
102 while(top!=0 || root!=NULL)
103 {
104 while(root!=NULL)
105 {
106 s[top] = root;
107 printf("%c ", s[top++]->tag);
108 root = root->left;
109 }
110 if(top>0)
111 {
112 root = s[--top];
113 root = root->right;
114 }
115 }
116 }
117
118 void BTree::NR_InVisit(BTNode *root)
119 {
120 BTNode *s[MAXN];
121 int top=0;
122
123 while(top!=0 || root!=NULL)
124 {
125 while(root!=NULL)
126 {
127 s[top++]=root;
128 root = root->left;
129 }
130 if(top>0)
131 {
132 root = s[--top];
133 printf("%c ", root->tag);
134 root = root->right;
135 }
136 }
137 }
138
139 void BTree::NR_PostVisit(BTNode *root)
140 {
141 BTNode *s[MAXN], *tmp=NULL;
142 int top=0;
143
144 while(top!=0 || root!=NULL)
145 {
146 while(root!=NULL)
147 {
148 s[top++]=root;
149 root=root->left;
150 }
151 if(top>0)
152 {
153 root = s[--top];
154
155 /*右孩子不存在或者已经访问过，root出栈并访问*/
156 if( (root->right == NULL) || (root->right == tmp) )
157 {
158 printf("%c ", root->tag);
159 tmp = root; //保存root指针
160 root=NULL; //当前指针置空，防止再次入栈
161 &n
补充：web前端 , JavaScript ,
