03-树2 List Leaves (队列——链式存储)

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define null -1
  5 #define MaxTreeNode 10
  6 
  7 typedef int ElementType;
  8 typedef int Tree;
  9 typedef struct TreeNode *BinTree;
 10 struct TreeNode {
 11     ElementType Data;
 12     Tree left;
 13     Tree right;
 14     BinTree Left;
 15     BinTree Right;
 16 };
 17 
 18 struct Node {    // 队列中的节点 
 19     BinTree BT;
 20     struct Node *Next;
 21 };
 22 typedef struct Node *Position;
 23 
 24 struct QNode {
 25     Position Front, Rear;    // 队列的头、尾指针 
 26 };
 27 typedef struct QNode *Queue;
 28 
 29 typedef struct node *PtrToNode;
 30 struct node {
 31     int value;
 32     PtrToNode next;
 33 };
 34 typedef PtrToNode List;
 35 
 36 BinTree BulidTree(int N);
 37 Queue CreateQueue();
 38 int IsEmpty(Queue Q);
 39 void AddQ(Queue Q, BinTree BT);
 40 BinTree DeleteQ(Queue Q);
 41 List FindLeaf(BinTree BT);
 42 void Print(List L);
 43 
 44 int main()
 45 {
 46     int N;        // 节点数量
 47     scanf("%d\n", &N);
 48     
 49     BinTree RootNode;
 50     RootNode = BulidTree(N);
 51     
 52     List L;
 53     L = FindLeaf(RootNode);
 54 
 55     Print(L);
 56     
 57     return 0;
 58 }
 59 
 60 Queue CreateQueue()
 61 {
 62     Queue Q = (Queue)malloc(sizeof(struct QNode));
 63     Q->Front = Q->Rear = NULL;
 64     
 65     return Q;
 66 }
 67 
 68 int IsEmpty(Queue Q)
 69 {
 70     return ( Q->Front == NULL );
 71 }
 72 
 73 void AddQ(Queue Q, BinTree BT)
 74 {
 75     struct Node *TmpCell = (struct Node*)malloc(sizeof(struct Node)); 
 76     TmpCell->Next = NULL;
 77     TmpCell->BT = BT;
 78     
 79     if ( IsEmpty(Q) )    //     队列为空 
 80         Q->Front = Q->Rear = TmpCell;
 81     else {
 82         Q->Rear->Next = TmpCell;
 83         Q->Rear = TmpCell;
 84     }
 85 }
 86 
 87 BinTree DeleteQ(Queue Q)
 88 {
 89     if ( IsEmpty(Q) )    return NULL;
 90     
 91     struct Node *FrontCell;
 92     BinTree FrontElem;
 93     FrontCell = Q->Front;
 94     
 95     if ( Q->Front == Q->Rear )        //  若队列中只有一个元素 
 96         Q->Front = Q->Rear = NULL;    //  删除后置空 
 97     else                         
 98         Q->Front = Q->Front->Next;
 99     
100     FrontElem = FrontCell->BT;
101     free(FrontCell);
102     
103     return FrontElem;
104 }
105 
106 List FindLeaf(BinTree BT)
107 {
108     if ( !BT )        return NULL;
109     
110     List r, p, t;
111     p = (List)malloc(sizeof(struct node));    p->next = NULL;    
112     r = p;
113     
114     Queue Q;
115     Q = CreateQueue();    // 创建空队列
116     AddQ(Q, BT);
117     
118     BinTree T;
119     while ( !IsEmpty(Q) ) {
120         T = DeleteQ(Q);
121         if ( T->Left == NULL && T->Right == NULL ) {
122             t = (List)malloc(sizeof(struct node));    t->next = NULL;    
123             t->value = T->Data;
124             r->next = t; r = t;
125         } else {
126             if ( T->Left )    AddQ(Q, T->Left);
127             if ( T->Right )   AddQ(Q, T->Right);
128         }
129     }
130     t = p; p = p->next; free(t);
131     
132     return p;
133 }
134 
135 void Print(List L)
136 {
137     if ( !L )    return;
138     int flag = 1;　　　　 
139     
140     while ( L ) {
141         if ( flag )
142             flag = 0;
143         else
144             printf(" ");
145         printf("%d", L->value);
146         
147         L = L->next;
148     }
149 }
150 
151 BinTree BulidTree(int N)
152 {
153     BinTree T[N];
154     Tree Root;
155     int check[N];
156     char cl, cr;
157     int i, j;
158     if ( N ) {
159         for ( i = 0; i < N; i++ )    check[i] = 0;
160         for ( i = 0; i < N; i++ ) {
161             scanf("%c %c\n", &cl, &cr);
162             T[i] = (BinTree)malloc(sizeof(struct TreeNode));
163             T[i]->Data = i;
164             // left
165             if ( cl != '-' ) {
166                 T[i]->left = cl - '0';
167                 check[T[i]->left] = 1;
168             } else {
169                 T[i]->left = null;
170             }
171             // right
172             if ( cr != '-' ) {
173                 T[i]->right = cr - '0';
174                 check[T[i]->right] = 1;
175             } else {
176                 T[i]->right = null;
177             }
178         }
179         // 构建二叉树
180         Tree L, R;
181         for ( i = 0; i < N; i++ ) {
182             L = T[i]->left;
183             R = T[i]->right;
184             
185             if ( L != null )    T[i]->Left = T[L];
186             else                 T[i]->Left = NULL;
187             
188             if ( R != null )    T[i]->Right = T[R];
189             else                T[i]->Right = NULL;
190         }
191         // 找到根节点所在位置 
192         for ( i = 0; i < N; i++ )
193             if ( !check[i] )    break;
194         Root = i;
195         
196     } else {
197         return NULL;
198     }
199     
200     return T[Root];
201 }