二叉树（周五实验）

  1 #include <iostream>
  2 #include<fstream>
  3 using namespace std;
  4 
  5 typedef struct TreeNode
  6 {
  7     char data;
  8     int level;
  9     TreeNode* lchid;
 10     TreeNode* rchid;
 11 }TreeNode;
 12 
 13 char arr[20][2];//存放结点信息
 14 bool visited[20]={0};//标记是否访问
 15 int numlevel[20]={0};
 16 int sum=1;//文件总行数加一
 17 
 18 typedef struct StackNode
 19 {
 20     TreeNode* data;
 21     StackNode* next;
 22 }StackNode;
 23 
 24 typedef struct QueueNode
 25 {
 26     TreeNode* data;
 27     QueueNode* next;
 28     QueueNode* pre;
 29 }QueueNode;
 30 
 31 QueueNode* initQueue()
 32 {
 33     QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));
 34     Q->data = NULL;
 35     Q->next = Q;
 36     Q->pre = Q;
 37     return Q;
 38 }
 39 
 40 void enQueue(QueueNode* Q,TreeNode*T)
 41 {
 42     QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
 43     node->data = T;
 44     
 45     node->next = Q;
 46     node->pre = Q->pre;
 47     Q->pre->next = node;
 48     Q->pre = node;
 49 }
 50 
 51 bool isEmptyQ(QueueNode* Q)
 52 {
 53     if (Q->next == Q)
 54         return true;
 55     return false;
 56 }
 57 
 58 QueueNode* deQueue(QueueNode* Q)
 59 {
 60     if (isEmptyQ(Q) == true)
 61         return NULL;
 62     QueueNode* node = Q->next;
 63 
 64     Q->next->next->pre = Q;
 65     Q->next = Q->next->next;
 66     return node;
 67 }
 68 
 69 StackNode* initStack()
 70 {
 71     StackNode* S = (StackNode*)malloc(sizeof(StackNode));
 72     S->data = NULL;
 73     S->next = NULL;
 74     return S;
 75 }
 76 
 77 void Push(TreeNode* data, StackNode* S)
 78 {
 79     StackNode* node = (StackNode*)malloc(sizeof(StackNode));
 80     node->data = data;
 81     node->next = S->next;
 82     S->next = node;
 83 }
 84 
 85 int isEmptyS(StackNode* S)
 86 {
 87     if (S->next == NULL)
 88         return 1;
 89     return 0;
 90 }
 91 
 92 StackNode* Pop(StackNode* S)
 93 {
 94     if (isEmptyS(S))
 95         return NULL;
 96     StackNode* node = S->next;
 97     S->next = node->next;
 98     return node;
 99 }
100 
101 StackNode* GetPop(StackNode* S)
102 {
103     if (isEmptyS(S))
104         return NULL;
105     StackNode* node = S->next;
106     return node;
107 }
108 
109 int SearchChild(int place)
110 {
111     for (int i = 1; i < sum; i++)
112     {
113         //该节点未访问并且父亲等于搜索的结点
114         if (visited[i] == 0 && arr[i][2] == arr[place][1])
115             return i;
116     }
117     return -1;
118 }
119 
120 void CreateTreeNode(TreeNode** T,int place,int pos)
121 {
122     //没有该结点
123     if (place == -1)
124         (*T) = NULL;
125     else
126     {
127         visited[place] = 1;
128         //标记已经访问，防止多次访问
129 
130         char ch = arr[place][1];
131         (*T) = (TreeNode*)malloc(sizeof(TreeNode));
132         (*T)->data = ch;
133         (*T)->level = pos;
134 
135         pos++;
136 
137         //寻找左孩子
138         int nextplace1 = SearchChild(place);
139         CreateTreeNode(&(*T)->lchid, nextplace1,pos);
140         //寻找右孩子
141         int nextplace2 = SearchChild(place);
142         CreateTreeNode(&(*T)->rchid, nextplace2,pos);
143     }
144     
145 }
146 
147 //先序遍历(递归)
148 void preOrderFun(TreeNode* T)
149 {
150     if (T == NULL)
151         return;
152     else
153     {
154         //输出节点
155         cout << T->data << " ";
156         //左孩子
157         preOrderFun(T->lchid);
158         //右孩子
159         preOrderFun(T->rchid);
160     }
161 }
162 
163 //中序遍历非递归
164 void inOrder(TreeNode* T)
165 {
166     TreeNode* node = T;
167     StackNode* S = initStack();
168     while (node||!isEmptyS(S))
169     {
170         if (node)
171         {
172             Push(node, S);
173             node = node->lchid;
174         }
175         else
176         {
177             node = Pop(S)->data;
178             cout << node->data << " ";
179             node = node->rchid;
180         }
181     }
182 }
183 
184 void LevelNumber(TreeNode* T,QueueNode*Q)
185 {
186     enQueue(Q, T);
187     while (!isEmptyQ(Q))
188     {
189         QueueNode* node = deQueue(Q);
190         numlevel[node->data->level]++;
191         if (node->data->lchid)
192             enQueue( Q,node->data->lchid);
193         if (node->data->rchid)
194             enQueue(Q, node->data->rchid);
195     }
196 }
197 
198 int main()
199 {
200     fstream fp;
201     fp.open("text.txt", ios::in);
202     if (!fp)return 0;
203 
204     int place = 0;//找寻根节点
205     while (!fp.eof())
206     {
207         fp >> arr[sum][1] >> arr[sum][2];
208         if (arr[sum][1] == arr[sum][2]&&arr[sum][1]!='\0')
209             place = sum;
210         sum++;
211     }
212 
213     int pos = 1;//层次
214 
215     TreeNode* T;
216     CreateTreeNode(&T, place,pos);
217 
218     cout << "先序遍历:" << endl;
219     preOrderFun(T);
220     cout << endl;
221 
222     cout << "中序遍历:" << endl;
223     inOrder(T);
224     cout << endl;
225 
226     QueueNode* Q = initQueue();
227     LevelNumber(T,Q);
228     int i = 1;
229     while (numlevel[i] != 0)
230     {
231         cout << numlevel[i] << endl;
232         i++;
233     }
234 }