二叉排序树（又叫二叉查找树、二叉搜索树）的操作集及平衡二叉排序树

　　二叉排序树或者是一棵空树；或者是具有如下特征的二叉树：若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左右子树也都分别是二叉排序树；二叉排序树的定义，是一个递归定义的过程；对二叉排序树进行中序遍历，遍历结果恰好是一个有序的线性序列，这也是它被称为二叉排序树的由来；

　　二叉排序树的查找，若给定值等于根结点的关键字，则查找成功；如果给定值小于根结点的关键字，则继续在左子树上进行查找；若给定值大于根结点的关键字，则继续在右子树上进行查找；若二叉排序树为空则查找失败；查找成功的路径，从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点；查找不成功的路径，从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止；

　　二叉排序树插入结点的位置，就是查找失败的位置；插入操作在查找不成功时才进行，如果二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到；

　　二叉排序树，是在插入的基础上生成的，二叉排序树的生成过程就是结点序列的插入过程；二叉排序树的形态完全由一个输入序列决定，一个无序序列可以通过构造一棵二叉排序树而得到一个有序序列；

　　中序遍历二叉排序树可以得到关键字有序序列；在构造二叉排序树时，每次插入的新结点都是新的叶子结点，所以进行插入时不必移动其他结点；二叉排序树不但拥有类似于折半查找的特性，又采取了链表作为存储结构，因此是动态查找表的一种适宜表示；

　　二叉排序树的删除和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性；删除结点分三种情况，结点有左右二个孩子，有左孩子没有右孩子，有右孩子没有左孩子，左右孩子都没有；查找不到删除的结点删除不成功；被删除结点为叶子结点即没有左右孩子，修改其父结点的指针域就可以了，即该结点的指针赋值为NULL；被删除结点有左或右一个孩子的，修改其父结点的指针域，即该结点的指针由其子结点指针覆盖；被删除结点有左右两个孩子的，查找其右子树的最小值结点，右子树的最小值结点的值赋值给该结点，删除右子树的最小值结点，或者查找其左子树的最大值的结点，左子树的最大值结点的值赋值给该结点，删除左子树的最大值结点；

　　一、排序树操作集

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef int ElementType;
  5 typedef struct TNode *Position;
  6 typedef Position BinTree;
  7 struct TNode{
  8     ElementType Data;
  9     BinTree Left;
 10     BinTree Right;
 11 };
 12 
 13 void PreorderTraversal( BinTree BT ); 
 14 void InorderTraversal( BinTree BT );  
 15 
 16 BinTree Insert( BinTree BST, ElementType X );
 17 BinTree Delete( BinTree BST, ElementType X );
 18 Position Find( BinTree BST, ElementType X );
 19 Position FindMin( BinTree BST );
 20 Position FindMax( BinTree BST );
 21 
 22 
 23 int main()
 24 {
 25     BinTree BST, MinP, MaxP, Tmp;
 26     ElementType X;
 27     int N, i;
 28 
 29     BST = NULL;
 30     scanf("%d", &N);
 31     for ( i=0; i<N; i++ ) {
 32         scanf("%d", &X);
 33         BST = Insert(BST, X);
 34     }
 35     printf("Preorder:"); PreorderTraversal(BST); printf("
");
 36     MinP = FindMin(BST);
 37     MaxP = FindMax(BST);
 38     scanf("%d", &N);
 39     for( i=0; i<N; i++ ) {
 40         scanf("%d", &X);
 41         Tmp = Find(BST, X);
 42         if (Tmp == NULL) printf("%d is not found
", X);
 43         else {
 44             printf("%d is found
", Tmp->Data);
 45             if (Tmp==MinP) printf("%d is the smallest key
", Tmp->Data);
 46             if (Tmp==MaxP) printf("%d is the largest key
", Tmp->Data);
 47         }
 48     }
 49     scanf("%d", &N);
 50     for( i=0; i<N; i++ ) {
 51         scanf("%d", &X);
 52         BST = Delete(BST, X);
 53     }
 54     printf("Inorder:"); InorderTraversal(BST); printf("
");
 55 
 56     return 0; 
 57 }
 58 
 59 // 插入 
 60 BinTree Insert( BinTree BST, ElementType X ){
 61     if(!BST){  // 如果为空，创建新结点 
 62         BST = (BinTree)malloc(sizeof(struct TNode));
 63         BST->Data = X;
 64         BST->Left = NULL;
 65         BST->Right = NULL;
 66     }else{
 67         if(X < BST->Data)
 68             BST->Left = Insert(BST->Left,X);
 69         else if(BST->Data < X)
 70             BST->Right = Insert(BST->Right,X);
 71     }
 72     return BST; 
 73 }
 74 
 75 // 删除
 76 BinTree Delete( BinTree BST, ElementType X ){
 77     BinTree tmp;
 78     if(!BST){
 79         printf("Not Found
");
 80         return BST;
 81     }else{
 82         if(X < BST->Data)
 83             BST->Left = Delete(BST->Left,X);
 84         else if(BST->Data < X)
 85             BST->Right = Delete(BST->Right,X);
 86         else{  // 找到要删除结点 
 87             if(BST->Left && BST->Right){  // 如果该结点有左右儿子 
 88                 tmp = FindMin(BST->Right);
 89                 BST->Data = tmp->Data;
 90                 BST->Right = Delete(BST->Right,tmp->Data);
 91             }else{
 92                 tmp = BST;
 93                 if(BST->Left && !BST->Right)
 94                     BST = BST->Left;
 95                 else if(!BST->Left && BST->Right)
 96                     BST = BST->Right;
 97                 else
 98                     BST = NULL;
 99                 free(tmp);
100             }
101         }
102     }
103     return BST;
104 } 
105 
106 // 寻找值最小结点 
107 Position FindMin( BinTree BST ){
108     if(BST)
109         while(BST->Left)
110             BST = BST->Left;
111     return BST;
112 }
113 
114 // 寻找值最大结点
115 Position FindMax( BinTree BST ){
116     if(BST)
117         while(BST->Right)
118             BST = BST->Right;
119     return BST;
120 } 
121 
122 // 查找
123 Position Find( BinTree BST, ElementType X ){
124     if(!BST){
125         return NULL;
126     }else if(X < BST->Data)
127         return Find(BST->Left,X);
128     else if(BST->Data < X)
129         return Find(BST->Right,X);
130     else
131         return BST;
132 } 
133 
134 // 先序遍历
135 void PreorderTraversal( BinTree BT ){
136     if(BT){
137         printf(" %d",BT->Data);
138         PreorderTraversal(BT->Left);
139         PreorderTraversal(BT->Right);
140     }
141 } 
142 // 中序遍历
143 void InorderTraversal( BinTree BT ){
144     if(BT){
145         
146         InorderTraversal(BT->Left);
147         printf(" %d",BT->Data);
148         InorderTraversal(BT->Right);
149     }
150 }
操作集

　　二、判断是否同一棵排序树

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 /* 树结点定义 */
  4 typedef struct TreeNode *Tree;
  5 struct TreeNode {
  6     int v;
  7     Tree Left, Right;
  8     int flag; /* 判别结点是否访问过的标记 */
  9 };
 10 
 11 /* 函数声明 
 12    1.创建一个树结点
 13    2.插入一个树结点
 14    3.创建一棵树
 15    4.检查树结点是否访问过
 16    5.判断是否同一棵树
 17    6.清除树中各结点的flag标记
 18    7.释放树的空间
 19 */
 20 Tree NewNode( int V );
 21 Tree Insert( Tree T, int V );
 22 Tree MakeTree( int N );
 23 int check ( Tree T, int V );
 24 int Judge( Tree T, int N );
 25 void ResetT ( Tree T );
 26 void FreeTree ( Tree T );
 27 
 28 /* 主程序 */
 29 int main()
 30 {
 31     int N, L, i;
 32     Tree T; /* 创建一个树的空结点 */
 33     scanf("%d", &N);
 34     while (N) 
 35     {
 36         scanf("%d", &L);
 37         T = MakeTree(N); /* 创建一棵N个结点的树 */
 38         for (i=0; i<L; i++) 
 39         {   /* 判断是否同一棵树 */
 40             if (Judge(T, N)) printf("Yes
");
 41             else printf("No
");
 42             ResetT(T); /*清除T中的标记flag*/
 43         }
 44         FreeTree(T); /* 释放上面的树空间 */
 45         scanf("%d", &N);
 46     }
 47     return 0; 
 48 }
 49 /* 创建一个树结点 */
 50 Tree NewNode( int V )
 51 { 
 52     Tree T = (Tree)malloc(sizeof(struct TreeNode));
 53     T->v = V;
 54     T->Left = T->Right = NULL;
 55     T->flag = 0;
 56     return T;
 57 }
 58 /* 插入一个树结点 */
 59 Tree Insert( Tree T, int V )
 60 {
 61     if ( !T ) T = NewNode(V);
 62     else 
 63     {
 64         if ( V > T->v )
 65             T->Right = Insert( T->Right, V );
 66         else
 67             T->Left = Insert( T->Left, V );
 68     }
 69     return T;
 70 }
 71 /* 创建一棵N个结点的树 */
 72 Tree MakeTree( int N )
 73 { 
 74     Tree T;
 75     int i, V;
 76     scanf("%d", &V);
 77     T = NewNode(V); /*  */
 78     for (i=1; i<N; i++) 
 79     {
 80         scanf("%d", &V);
 81         T = Insert(T, V); /*  */
 82     }
 83     return T;
 84 }
 85 /* 判断树的结点是否访问过 */
 86 int check ( Tree T, int V )
 87 {
 88     if ( T->flag ) 
 89     {
 90         if ( V<T->v ) return check(T->Left, V);
 91         else if ( V>T->v ) return check(T->Right, V);
 92         else return 0;
 93     }
 94     else 
 95     {
 96         if ( V==T->v ) 
 97         {
 98             T->flag = 1;
 99             return 1;
100         }
101         else return 0;
102     }
103 }
104 /* 判断是否同一棵树 */
105 int Judge( Tree T, int N )
106 {
107     int i, V, flag = 0;
108     /* flag,  0代表目前还一致, 1代表已经不一致*/
109     scanf("%d", &V);
110     if ( V!=T->v ) flag = 1;
111     else T->flag = 1;
112     for (i=1; i<N; i++) 
113     {
114         scanf("%d", &V);/* 读取结点的V */
115         if ( (!flag) && (!check(T, V)) ) flag = 1;
116     }
117     return !flag; /* 1代表已经不一致 */
118 }
119 /* 清除T中各结点的flag标记 */
120 void ResetT ( Tree T ) 
121 {
122     if (T->Left) ResetT(T->Left);
123     if (T->Right) ResetT(T->Right);
124     T->flag = 0;
125 }
126 /* 释放T的空间 */
127 void FreeTree ( Tree T ) 
128 {
129     if (T->Left) FreeTree(T->Left);
130     if (T->Right) FreeTree(T->Right);
131     free(T);
132 }
133 
134 /* 
135 测试用例
136 4 2
137 3 1 4 2
138 3 4 1 2
139 3 2 4 1
140 2 1
141 2 1
142 1 2 0 
143 */
判断是否同一棵排序树

　　三、排序树非递归操作

 1 Position IterFind( ElementType X, BinTree BST ) 
 2 {     
 3     while( BST ) 
 4     {         
 5         if( X > BST->Data )       
 6             BST = BST->Right; /*向右子树中移动，继续查找*/         
 7         else if( X < BST->Data )    
 8             BST = BST->Left;  /*向左子树中移动，继续查找*/         
 9         else /* X == BST->Data */             
10             return BST; /*查找成功，返回结点的找到结点的地址*/     
11     }     
12     return NULL; /*查找失败*/ 
13 }
查找
 1 BinTree Delete( BinTree BST, KeyType Key )
 2 {
 3     BinTree P,F,S,Q;
 4     P = BST;
 5     F = NULL; /* P的前驱结点指针 */
 6     
 7     while(P)
 8     {
 9         if(P->Data == Key) /* 找到了 */
10             break;
11         F = P; /* 保存P指针 */
12         if(P->Data > Key) 
13             P = P->Left; /* 左子树找 */
14         else
15             P = P->Right; /* 右子树找 */
16     }
17     
18     if(P == NULL)  /* 没找到返回 */
19         return BST;
20         
21     if(P->Left == NULL) /* 删除结点的左子树为空 */
22     {
23         if(F == NULL) /* 如果删除的是根结点 */
24             BST = P->Right;  /* P的右子树指针赋值给根结点指针 */
25         else if(F->Left == P) /* 如果删除结点是其父结点的左孩子 */
26             F->Left = P->Right;/* 删除结点的右孩子指针赋值给其父结点的左孩子 */
27         else
28             F->Right = P->Right; 
29         free(P); /* 删除结点 */
30     }
31     else
32     {
33         Q = P; /* P指针赋值给Q */
34         S = P->Left; /* P的左孩子指针赋值给S */
35         while(S->Right) /* 向右找右子树的最大值S->Data */
36         {
37             Q = S; /* Q为S的前驱结点 */
38             S = S->Right;
39         }
40         if(Q == P) /* 如果P左子树S的右子树为空 */
41             Q->Left = S->Left; 
42         else
43             Q->Right = S->Left;
44         P->Data = S->Data;
45         free(S);
46     }
47     return BST;
48 }
删除

　　四、平衡二叉树

　　平衡因子（Balance Factor，简称BF）: BF(T) = hL-hR，其中hL和hR分别为T的左、右子树的高度；平衡二叉树Balanced Binary Tree，AVL树 :  空树，或者任一结点左、右子树高度差的绝对值不超过1，即|BF(T) |≤ 1 ；给定结点数为 n 的AVL树的 最大高度为O(log2n) ；设 nh 是高度为h( h>= 0)的平衡二叉树的最小结点数，nh = nh-1 + nh-2 + 1 ，nh = Fh+2 - 1， (Fh+2，斐波那契序列)，1，2，4，7，12，20，...

  1 typedef struct AVLNode *Position;
  2 typedef Position AVLTree; /* AVL树类型 */
  3 struct AVLNode{
  4     ElementType Data; /* 结点数据 */
  5     AVLTree Left;     /* 指向左子树 */
  6     AVLTree Right;    /* 指向右子树 */
  7     int Height;       /* 树高 */
  8 };
  9  
 10 int Max ( int a, int b )
 11 {
 12     return a > b ? a : b;
 13 }
 14 
 15 AVLTree GetHeight(AVLTree A){
 16     if(!A) return -1;
 17     return A->Height;
 18 }
 19 
 20 AVLTree SingleLeftRotation ( AVLTree A )
 21 { /* 注意：A必须有一个左子结点B */
 22   /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */     
 23  
 24     AVLTree B = A->Left;
 25     A->Left = B->Right;
 26     B->Right = A;
 27     A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
 28     B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
 29   
 30     return B;
 31 }
 32  
 33 AVLTree DoubleLeftRightRotation ( AVLTree A )
 34 { /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
 35   /* 将A、B与C做两次单旋，返回新的根结点C */
 36      
 37     /* 将B与C做右单旋，C被返回 */
 38     A->Left = SingleRightRotation(A->Left);
 39     /* 将A与C做左单旋，C被返回 */
 40     return SingleLeftRotation(A);
 41 }
 42 
 43 AVLTree SingleRightRotation ( AVLTree A )
 44 { /* 注意：A必须有一个右子结点B */
 45   /* 将A与B做右单旋，更新A与B的高度，返回新的根结点B */     
 46  
 47     AVLTree B = A->Right;
 48     A->Right = B->Left;
 49     B->Left = A;
 50     A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
 51     B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
 52   
 53     return B;
 54 }
 55  
 56 AVLTree DoubleRightLeftRotation ( AVLTree A )
 57 { /* 注意：A必须有一个右子结点B，且B必须有一个左子结点C */
 58   /* 将A、B与C做两次单旋，返回新的根结点C */
 59      
 60     /* 将B与C做右单旋，C被返回 */
 61     A->Right = SingleLeftRotation(A->Right);
 62     /* 将A与C做右单旋，C被返回 */
 63     return SingleRightRotation(A);
 64 }
 65  
 66 AVLTree Insert( AVLTree T, ElementType X )
 67 { /* 将X插入AVL树T中，并且返回调整后的AVL树 */
 68     if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
 69         T = (AVLTree)malloc(sizeof(struct AVLNode));
 70         T->Data = X;
 71         T->Height = 0;
 72         T->Left = T->Right = NULL;
 73     } /* if (插入空树) 结束 */
 74  
 75     else if ( X < T->Data ) {
 76         /* 插入T的左子树 */
 77         T->Left = Insert( T->Left, X);
 78         /* 如果需要左旋 */
 79         if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
 80             if ( X < T->Left->Data ) 
 81                T = SingleLeftRotation(T);      /* 左单旋 */
 82             else 
 83                T = DoubleLeftRightRotation(T); /* 左-右双旋 */
 84     } /* else if (插入左子树) 结束 */
 85      
 86     else if ( X > T->Data ) {
 87         /* 插入T的右子树 */
 88         T->Right = Insert( T->Right, X );
 89         /* 如果需要右旋 */
 90         if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
 91             if ( X > T->Right->Data ) 
 92                T = SingleRightRotation(T);     /* 右单旋 */
 93             else 
 94                T = DoubleRightLeftRotation(T); /* 右-左双旋 */
 95     } /* else if (插入右子树) 结束 */
 96  
 97     /* else X == T->Data，无须插入 */
 98  
 99     /* 别忘了更新树高 */
100     T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
101      
102     return T;
103 }
插入，自平衡
  1 #include <stdio.h>
  2 #include <malloc.h>
  3 
  4 typedef int ElementType;
  5 typedef struct AVLNode *Position;
  6 typedef Position AVLTree; /* AVL树类型 */
  7 struct AVLNode{
  8     ElementType Data; /* 结点数据 */
  9     AVLTree Left;     /* 指向左子树 */
 10     AVLTree Right;    /* 指向右子树 */
 11     int Height;       /* 树高 */
 12 };
 13 
 14 /* AVL树左右单旋左右双旋右左双旋插入 */
 15 int GetHeight( AVLTree A ); /* 树高 */
 16 int Max ( int a, int b );   /* 结点数据大小 */
 17 AVLTree SingleLeftRotation ( AVLTree A );
 18 AVLTree SingleRightRotation ( AVLTree A ); 
 19 AVLTree DoubleLeftRightRotation ( AVLTree A );
 20 AVLTree DoubleRightLeftRotation ( AVLTree A );
 21 AVLTree Insert( AVLTree T, ElementType X );
 22  
 23 /* 主程序 */
 24 int main()
 25 {
 26     AVLTree AVLT = NULL;
 27     int N, i;
 28     ElementType X;
 29     scanf("%d", &N);
 30     for ( i=0; i<N; i++ ) {
 31         scanf("%d", &X);
 32         AVLT = Insert(AVLT, X);
 33     }
 34     printf("%d
", AVLT->Data);
 35     return 0; 
 36 }
 37 
 38 /* 树高 */
 39 int GetHeight(AVLTree A)
 40 {
 41     if(!A) return -1;
 42     return A->Height;
 43 }
 44 
 45 /* 树数据大小 */
 46 int Max ( int a, int b )
 47 {
 48     return a > b ? a : b;
 49 }
 50 
 51 /* 左单旋 */
 52 AVLTree SingleLeftRotation ( AVLTree A )
 53 { /* 注意：A必须有一个左子结点B */
 54   /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */     
 55  
 56     AVLTree B = A->Left;
 57     A->Left = B->Right;
 58     B->Right = A;
 59     A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
 60     B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
 61   
 62     return B;
 63 }
 64 
 65 /* 右单旋 */
 66 AVLTree SingleRightRotation ( AVLTree A )
 67 { /* 注意：A必须有一个右子结点B */
 68   /* 将A与B做右单旋，更新A与B的高度，返回新的根结点B */     
 69  
 70     AVLTree B = A->Right;
 71     A->Right = B->Left;
 72     B->Left = A;
 73     A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
 74     B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
 75   
 76     return B;
 77 }
 78 
 79 /* 左右双旋 */
 80 AVLTree DoubleLeftRightRotation ( AVLTree A )
 81 { /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
 82   /* 将A、B与C做两次单旋，返回新的根结点C */
 83      
 84     /* 将B与C做右单旋，C被返回 */
 85     A->Left = SingleRightRotation(A->Left);
 86     /* 将A与C做左单旋，C被返回 */
 87     return SingleLeftRotation(A);
 88 }
 89 
 90 /* 右左双旋 */
 91 AVLTree DoubleRightLeftRotation ( AVLTree A )
 92 { /* 注意：A必须有一个右子结点B，且B必须有一个左子结点C */
 93   /* 将A、B与C做两次单旋，返回新的根结点C */
 94      
 95     /* 将B与C做右单旋，C被返回 */
 96     A->Right = SingleLeftRotation(A->Right);
 97     /* 将A与C做右单旋，C被返回 */
 98     return SingleRightRotation(A);
 99 }
100 
101 /* 插入 */
102 AVLTree Insert( AVLTree T, ElementType X )
103 { /* 将X插入AVL树T中，并且返回调整后的AVL树 */
104     if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
105         T = (AVLTree)malloc(sizeof(struct AVLNode));
106         T->Data = X;
107         T->Height = 0;
108         T->Left = T->Right = NULL;
109     } /* if (插入空树) 结束 */
110  
111     else if ( X < T->Data ) {
112         /* 插入T的左子树 */
113         T->Left = Insert( T->Left, X);
114         /* 如果需要左旋 */
115         if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
116             if ( X < T->Left->Data ) 
117                T = SingleLeftRotation(T);      /* 左单旋 */
118             else 
119                T = DoubleLeftRightRotation(T); /* 左-右双旋 */
120     } /* else if (插入左子树) 结束 */
121      
122     else if ( X > T->Data ) {
123         /* 插入T的右子树 */
124         T->Right = Insert( T->Right, X );
125         /* 如果需要右旋 */
126         if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
127             if ( X > T->Right->Data ) 
128                T = SingleRightRotation(T);     /* 右单旋 */
129             else 
130                T = DoubleRightLeftRotation(T); /* 右-左双旋 */
131     } /* else if (插入右子树) 结束 */
132  
133     /* else X == T->Data，无须插入 */
134  
135     /* 别忘了更新树高 */
136     T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
137      
138     return T;
139 }
平衡树插入结点，返回根结点

 　   五、判断完全二叉树( 循环队列   层序遍历 树结构 队列结构 )

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <stdbool.h>
  4 
  5 /* 树结点 */
  6 typedef struct TreeNode *BinTree;
  7 typedef struct TreeNode TreeNode;
  8 struct TreeNode{
  9     int Data, ID;
 10     BinTree Left;
 11     BinTree Right;
 12 };
 13 
 14 /* 顺序循环队列*/
 15 #define MAXSIZE  21 //最大队列长度 N 
 16 typedef struct QNode *Queue; 
 17 struct QNode {
 18     BinTree* Data;    /* 存储元素的数组 */
 19     int Front, Rear;  /* 队列的头、尾指针 */
 20     int MaxSize;      /* 队列最大容量 */
 21 };
 22 
 23 BinTree Insert( BinTree BST, int X );     /* 插入 */
 24 void LevelorderTraversal ( BinTree BT );  /* 层次遍历 */
 25 Queue CreateQueue( );                /*  建队 */
 26 bool IsFull( Queue Q );              /* 队满 */
 27 bool IsEmpty( Queue Q );             /* 队空 */
 28 bool AddQ( Queue Q, BinTree X );     /* 入队 */
 29 BinTree DeleteQ( Queue Q );             /* 出队 */
 30 
 31 int main()
 32 {
 33     int N, i, X;   
 34     scanf("%d", &N);
 35     
 36     BinTree BST = NULL;
 37     for ( i=0; i<N; i++ ) {
 38         scanf("%d", &X);
 39         BST = Insert(BST, X);
 40     }
 41     LevelorderTraversal(BST);
 42     return 0;
 43 }
 44 
 45 BinTree Insert( BinTree BST, int X )
 46 {
 47     if(!BST)
 48     {  
 49         BST = (BinTree)malloc(sizeof(TreeNode));
 50         BST->Data = X;
 51         BST->Left = NULL;
 52         BST->Right = NULL;
 53     }
 54     else
 55     {
 56         if(X > BST->Data)
 57             BST->Left = Insert(BST->Left,X);
 58         else if(BST->Data > X)
 59             BST->Right = Insert(BST->Right,X);
 60     }
 61     return BST; 
 62 }
 63 
 64 void LevelorderTraversal ( BinTree BT )
 65 { 
 66     Queue Q; 
 67     BinTree T;
 68     
 69     bool flag = true, ans = true;
 70     int order = 0; /* 顺序 */
 71     
 72     if ( !BT ) return; /* 若是空树则直接返回 */
 73     
 74     Q = CreateQueue(); /* 创建空队列Q */ 
 75     
 76     
 77     AddQ( Q, BT ); /* 树根入队 */
 78     BT->ID = 1;
 79     
 80     while ( !IsEmpty(Q) ) 
 81     {
 82         T = DeleteQ( Q ); /* 出队 */
 83         order++;
 84         
 85         if(T->ID != order)
 86             ans = false; /* 顺序不同 */
 87         if(flag)  /* 输出格式 */
 88         {
 89             printf("%d", T->Data);
 90             flag = false;
 91         }
 92         else printf(" %d", T->Data);
 93               
 94         if ( T->Left ){
 95             T->Left->ID = 2 * T->ID;  /* 左儿子顺序 */
 96             AddQ( Q, T->Left );       /* 左儿子入队 */
 97         }   
 98         if ( T->Right ){
 99             T->Right->ID = 2 * T->ID + 1;/* 右儿子顺序 */
100             AddQ( Q, T->Right );         /* 右儿子入队 */
101         }  
102     }
103     
104     if(ans)  /* 顺序相同 */
105         printf("
YES");
106     else
107         printf("
NO"); 
108 }
109 
110  /* 建队列 */
111 Queue CreateQueue( )//返回队列指针
112 {
113     Queue Q = (Queue)malloc(sizeof(struct QNode));
114     Q->Data = (BinTree*)malloc(MAXSIZE * sizeof(BinTree));
115     Q->Front = Q->Rear = 0;
116     Q->MaxSize = MAXSIZE;
117     return Q;
118 }
119 
120 /* 队满 */
121 bool IsFull( Queue Q )
122 {
123     return ((Q->Rear+1)%Q->MaxSize == Q->Front);
124 }
125 
126 /* 队空 */
127 bool IsEmpty( Queue Q )
128 {
129     return (Q->Front == Q->Rear);
130 }
131 
132 /* 入队 */
133 bool AddQ( Queue Q, BinTree X )
134 {
135     if ( IsFull(Q) ) {
136         return false;
137     }
138     else {
139         Q->Rear = (Q->Rear+1)%Q->MaxSize;
140         Q->Data[Q->Rear] = X;
141         return true;
142     }
143 }
144 
145 /* 出队 */
146 BinTree DeleteQ( Queue Q )
147 {    
148     if ( IsEmpty(Q) )
149         return NULL;
150     Q->Front =(Q->Front+1)%Q->MaxSize;
151     return  Q->Data[Q->Front];   
152 }
顺序循环队列层序遍历
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/GoldenEllipsis/p/11424412.html