1、#include <stdio.h>#include <stdlib.h>#define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30#ifndef elemType typedef char elemType;#endif/*/*                      以下是關于二叉樹操作的11個簡單算法&#

2、160;              */*/ struct BTreeNode elemType data; struct BTreeNode *left; struct BTreeNode *right;/* 1.初始化二叉樹 */void initBTree(struct BTreeNode* *bt) *bt = NULL; return;/* 2.建立二叉樹(根據a所指向的二叉樹廣義表字符串建立) */voi

3、d createBTree(struct BTreeNode* *bt, char *a) struct BTreeNode *p; struct BTreeNode *sSTACK_MAX_SIZE;/* 定義s數組為存儲根結點指針的棧使用 */ int top = -1; /* 定義top作為s棧的棧頂指針，初值為-1,表示空棧 */ int k; /* 用k作為處理結點的左子樹和右子樹，k = 1處理左子樹，k = 2處理右子樹 */ int i = 0; /* 用i掃描數組a中存儲的二叉樹廣義表字符串，初值

4、為0 */ *bt = NULL; /* 把樹根指針置為空，即從空樹開始建立二叉樹 */ /* 每循環一次處理一個字符，直到掃描到字符串結束符0為止 */ while(ai != '0')     switch(ai)         case ' ':    break;  /* 對空格不作任何處理 */   ca

5、se '(':    if(top = STACK_MAX_SIZE - 1)        printf("棧空間太小！n");     exit(1);        top+;    stop = p;    k = 1; &#

6、160;  break;         case ')':    if(top = -1)        printf("二叉樹廣義表字符串錯誤!n");     exit(1);        top-; &#

7、160;  break;   case ',':    k = 2;    break;   default:    p = malloc(sizeof(struct BTreeNode);    p->data = ai;    p->left = p->right = NULL;&

8、#160;   if(*bt = NULL)     *bt = p;    else        if( k = 1)            stop->left = p;        else  

9、          stop->right = p;                   i+;  /* 為掃描下一個字符修改i值 */  return;/* 3.檢查二叉樹是否為空，為空則返回1,否則返回0 */int emptyBTree(struct BTreeNode *bt)

10、0;if(bt = NULL)     return 1; else     return 0; /* 4.求二叉樹深度 */int BTreeDepth(struct BTreeNode *bt) if(bt = NULL)     return 0;  /* 對于空樹，返回0結束遞歸 */ else     int dep1 = BTreeDepth(bt->left

11、);  /* 計算左子樹的深度 */  int dep2 = BTreeDepth(bt->right);  /* 計算右子樹的深度 */  if(dep1 > dep2)      return dep1 + 1;  else      return dep2 + 1;   /* 5.從二叉樹中查找值為x的結點，若存在則返回元素存儲位置，否則返回空值 *

12、/elemType *findBTree(struct BTreeNode *bt, elemType x) if(bt = NULL)     return NULL; else     if(bt->data = x)         return &(bt->data);     else /* 分別向左右子樹遞歸查找 */ 

13、60;       elemType *p;   if(p = findBTree(bt->left, x)       return p;      if(p = findBTree(bt->right, x)       return p;      r

14、eturn NULL;      /* 6.輸出二叉樹(前序遍歷) */void printBTree(struct BTreeNode *bt) /* 樹為空時結束遞歸，否則執行如下操作 */ if(bt != NULL)     printf("%c", bt->data);  /* 輸出根結點的值 */   if(bt->left != NULL | bt->right != NULL)

15、60;  printf("(");   printBTree(bt->left);   if(bt->right != NULL)       printf(",");      printBTree(bt->right);   printf(")");   &

16、#160;   return;/* 7.清除二叉樹，使之變為一棵空樹 */void clearBTree(struct BTreeNode* *bt) if(*bt != NULL)     clearBTree(&(*bt)->left);  clearBTree(&(*bt)->right);  free(*bt);  *bt = NULL;  return;/* 8.前序遍歷 */void preOrder(st

17、ruct BTreeNode *bt) if(bt != NULL)     printf("%c ", bt->data);  /* 訪問根結點 */  preOrder(bt->left);    /* 前序遍歷左子樹 */  preOrder(bt->right);   /* 前序遍歷右子樹 */  return;/* 9.前序遍歷 */void inO

18、rder(struct BTreeNode *bt) if(bt != NULL)  inOrder(bt->left);    /* 中序遍歷左子樹 */     printf("%c ", bt->data);  /* 訪問根結點 */  inOrder(bt->right);    /* 中序遍歷右子樹 */  return;/* 10.后序遍

19、歷 */void postOrder(struct BTreeNode *bt) if(bt != NULL)  postOrder(bt->left);   /* 后序遍歷左子樹 */  postOrder(bt->right);   /* 后序遍歷右子樹 */  printf("%c ", bt->data);  /* 訪問根結點 */  return;/* 11.按層遍歷 */voi

20、d levelOrder(struct BTreeNode *bt) struct BTreeNode *p; struct BTreeNode *qQUEUE_MAX_SIZE; int front = 0, rear = 0; /* 將樹根指針進隊 */ if(bt != NULL)     rear = (rear + 1) % QUEUE_MAX_SIZE;  qrear = bt;  while(front != rear)  /* 隊

21、列非空 */     front = (front + 1) % QUEUE_MAX_SIZE; /* 使隊首指針指向隊首元素 */  p = qfront;  printf("%c ", p->data);  /* 若結點存在左孩子，則左孩子結點指針進隊 */  if(p->left != NULL)      rear = (rear + 1) % QUEUE_MAX_SIZE; 

22、  qrear = p->left;    /* 若結點存在右孩子，則右孩子結點指針進隊 */  if(p->right != NULL)      rear = (rear + 1) % QUEUE_MAX_SIZE;   qrear = p->right;    return;/*/*int main(int argc, char *argv) struct BTr

23、eeNode *bt; /* 指向二叉樹根結點的指針 */ char *b;    /* 用于存入二叉樹廣義表的字符串 */ elemType x, *px; initBTree(&bt); printf("輸入二叉樹廣義表的字符串：n"); /* scanf("%s", b); */ b = "a(b(c), d(e(f, g), h(, i)" createBTree(&bt, b); 

24、if(bt != NULL) printf(" %c ", bt->data); printf("以廣義表的形式輸出：n"); printBTree(bt);   /* 以廣義表的形式輸出二叉樹 */ printf("n"); printf("前序：");  /* 前序遍歷 */ preOrder(bt); printf("n"); printf("中

25、序：");  /* 中序遍歷 */ inOrder(bt); printf("n"); printf("后序：");  /* 后序遍歷 */ postOrder(bt); printf("n"); printf("按層：");  /* 按層遍歷 */ levelOrder(bt); printf("n"); /* 從二叉樹中查找一個元素結

26、點 */ printf("輸入一個待查找的字符：n"); scanf(" %c", &x);  /* 格式串中的空格跳過空白字符 */ px = findBTree(bt, x); if(px)     printf("查找成功：%cn", *px); else     printf("查找失敗！n");  printf("二叉樹

27、的深度為："); printf("%dn", BTreeDepth(bt); clearBTree(&bt); return 0;*/   #include <stdio.h>#define QUEUE_MAX_SIZE 20#define STACK_MAX_SIZE 10typedef int elemType;#include "BT.c"/*/*   

28、;                 以下是關于二叉搜索樹操作的4個簡單算法               */*/*  */* 遞歸算法 */elemType *findBSTree1(struct BTreeNode&#

29、160;*bst, elemType x)    /* 樹為空則返回NULL */    if (bst = NULL)        return NULL;    else        if (x = b

30、st->data)            return &(bst->data);        else            if (x < bst->data)   

31、60;/* 向左子樹查找并直接返回 */                return findBSTree1(bst->left, x);            else        /*&#

32、160;向右子樹查找并直接返回 */                return findBSTree1(bst->right, x);                      &#

33、160; /* 非遞歸算法 */elemType *findBSTree2(struct BTreeNode *bst, elemType x)    while (bst != NULL)        if (x = bst->data)       

34、0;    return &(bst->data);        else if (x < bst->data)            bst = bst->left;       &#

35、160;else            bst = bst->right;                return NULL;/*  */* 遞歸算法 */void insertBSTree1(struct BTreeN

36、ode* *bst, elemType x)    /* 新建一個根結點 */    if (*bst = NULL)        struct BTreeNode *p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode);

37、0;       p->data = x;        p->left = p->right = NULL;        *bst = p;        return; 

38、60;  else if (x < (*bst)->data)        /* 向左子樹完成插入運算 */        insertBSTree1(&(*bst)->left), x);    else      &#

39、160; /* 向右子樹完成插入運算 */        insertBSTree1(&(*bst)->right), x);    /* 非遞歸算法 */void insertBSTree2(struct BTreeNode* *bst, elemType x)    struct BTreeNode&

40、#160;*p;    struct BTreeNode *t = *bst, *parent = NULL;    /* 為待插入的元素查找插入位置 */    while (t != NULL)        parent = t;  

41、      if (x < t->data)            t = t->left;        else            t 

42、;= t->right;                /* 建立值為x，左右指針域為空的新結點 */    p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode);    p->data = 

43、;x;    p->left = p->right = NULL;    /* 將新結點鏈接到指針為空的位置 */    if (parent = NULL)        *bst = p;       &

44、#160;/* 作為根結點插入 */    else if (x < parent->data)        /* 鏈接到左指針域 */       parent->left = p;    else    &

45、#160;   parent->right = p;        return;/*  */void createBSTree(struct BTreeNode* *bst, elemType a, int n)    int i;    *bst = NULL

46、;    for (i = 0; i < n; i+)        insertBSTree1(bst, ai);        return;/* 4.刪除值為x的結點，成功返回1,失敗返回0 */int deleteBSTree(struct BTreeNode*&#

47、160;*bst, elemType x)    struct BTreeNode *temp = *bst;    if (*bst = NULL)        return 0;        if (x < (*bs

48、t)->data)        return deleteBSTree(&(*bst)->left), x);        /* 向左子樹遞歸 */        if (x > (*bst)->data)    

49、    return deleteBSTree(&(*bst)->right), x);    /* 向右子樹遞歸 */        /* 待刪除的元素等于樹根結點值且左子樹為空，將右子樹作為整個樹并返回1 */    if (*bst)->left = NULL)  

50、;      *bst = (*bst)->right;        free(temp);        return 1;        /* 待刪除的元素等于樹根結點值且右子樹為空，將左子樹作為整個樹并返回1 */  

51、;  if (*bst)->right = NULL)        *bst = (*bst)->left;        free(temp);        return 1;    else  

52、60;     /* 中序前驅結點為空時，把左孩子結點值賦給樹根結點，然后從左子樹中刪除根結點 */        if (*bst)->left->right = NULL)            (*bst)->data = (*bst)->left-

53、>data;            return deleteBSTree(&(*bst)->left), (*bst)->data);        else    /* 定位到中序前驅結點，把該結點值賦給樹根結點，然后從以中序前驅結點為根的     

54、              樹上刪除根結點*/            struct BTreeNode *p1 = *bst, *p2 = p1->left;         

55、;   while (p2->right != NULL)                p1 = p2;                p2 = p2->right;

56、                        (*bst)->data = p2->data;            return deleteBSTree(&(p1->right)

57、, p2->data);            /*/int main(int argc, char *argv)    int x, *px;    elemType a10 = 30, 50, 20, 40, 25, 70, 54

58、, 23, 80, 92;    struct BTreeNode *bst = NULL;    createBSTree(&bst, a, 10);    printf("建立的二叉搜索樹的廣義表形式為： ");    printBTree(bst);    printf(" ");    printf("中序遍歷： ");    inOrder(bst);    printf(" ");    printf("輸入待查找元素的值：");    scanf(" %d", &x);    i