二叉树的抽象数据类型

1 typedef struct Node
2 {
3     char data;
4     struct Node* Lchild;
5     struct Node* Rchild;
6 }BTNode;

按层次非递归遍历

 1 void LevelOrder(BTNode* A)
 2 {
 3     CSeQueue* B = InitSeQueue();
 4     InSeQueue(B, A);
 5     while (!IsEmptyQueue(B))
 6     {
 7         OutSeQueue(B, &A);
 8         printf("%c", A->data);
 9         if (A->Lchild != NULL)
10         {
11             InSeQueue(B, A->Lchild);
12         }
13         if (A->Rchild != NULL)
14         {
15             InSeQueue(B, A->Rchild);
16         }
17     }
18 }

源代码

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #define MAXSIZE 100
  5 
  6 typedef struct Node
  7 {
  8     char data;
  9     struct Node* Lchild;
 10     struct Node* Rchild;
 11 }BTNode;
 12 
 13 typedef struct
 14 {
 15     BTNode* elem[MAXSIZE];
 16     int front;
 17     int rear;
 18 }CSeQueue;//Circle Sequence Queue
 19 
 20 CSeQueue* InitSeQueue();
 21 int IsEmptyQueue(CSeQueue* A);
 22 int InSeQueue(CSeQueue* A, BTNode* B);
 23 int OutSeQueue(CSeQueue* A, BTNode** B);
 24 
 25 BTNode* CreateBinaryTree();
 26 void LevelOrder(BTNode* A);
 27 
 28 int main(void)
 29 {
 30     printf("请输入该二叉树先序遍历序列(用^表示空子树,叶子结点要跟两个^)：\n");
 31     BTNode* A = CreateBinaryTree();
 32 
 33     printf("按层次非递归遍历：");
 34     LevelOrder(A);
 35 
 36     system("pause");
 37     return 0;
 38 }
 39 
 40 CSeQueue* InitSeQueue()
 41 {
 42     CSeQueue* A = (CSeQueue*)calloc(1, sizeof(CSeQueue));
 43     A->front = MAXSIZE - 1;
 44     A->rear = MAXSIZE - 1;
 45     return A;
 46 }
 47 
 48 int IsEmptyQueue(CSeQueue* A)
 49 {
 50     if (A->front == A->rear)
 51     {
 52         return 1;
 53     }
 54     else
 55     {
 56         return 0;
 57     }
 58 }
 59 
 60 int InSeQueue(CSeQueue* A, BTNode* B)
 61 {
 62     if ((A->rear + 1) % MAXSIZE == A->front)
 63     {
 64         return 1;
 65     }
 66     else
 67     {
 68         A->rear = (A->rear + 1) % MAXSIZE;
 69         A->elem[A->rear] = B;
 70         return 0;
 71     }
 72 }
 73 
 74 int OutSeQueue(CSeQueue* A, BTNode** B)
 75 {
 76     if (A->rear == A->front)
 77     {
 78         return 1;
 79     }
 80     else
 81     {
 82         A->front = (A->front + 1) % MAXSIZE;
 83         (* B) = A->elem[A->front];
 84         return 0;
 85     }
 86 }
 87 
 88 BTNode* CreateBinaryTree()
 89 {
 90     BTNode* A = NULL;
 91     char ch = '\0';
 92 
 93     ch = getchar();
 94     if (ch == '^')
 95     {
 96         return NULL;
 97     }
 98     else
 99     {
100         A = (BTNode*)calloc(1, sizeof(BTNode));
101         A->data = ch;
102         A->Lchild = CreateBinaryTree();
103         A->Rchild = CreateBinaryTree();
104         return A;
105     }
106 }
107 
108 void LevelOrder(BTNode* A)
109 {
110     CSeQueue* B = InitSeQueue();
111     InSeQueue(B, A);
112     while (!IsEmptyQueue(B))
113     {
114         OutSeQueue(B, &A);
115         printf("%c", A->data);
116         if (A->Lchild != NULL)
117         {
118             InSeQueue(B, A->Lchild);
119         }
120         if (A->Rchild != NULL)
121         {
122             InSeQueue(B, A->Rchild);
123         }
124     }
125 }

View Code