寫在前面

已經(jīng)堅持了9周明顯感覺到自己體力跟不上，所以得養(yǎng)成每晚跑步的好習(xí)慣才行呢。這個周五下午感覺頭有點昏沉，遂偷懶，回來配置了下emacs，然后敲一敲二叉樹....

正文

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct BTNode
{
    char ch;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode, *PTree;//定義樹節(jié)點的結(jié)構(gòu)體
void createBTree(PTree *p)//建立二叉樹
{
    char ch;
    scanf("%c", &ch);
    getchar();//此時%c讀取的是單個字符，所以用那個getchar來接收一下
    if(ch == '#')
         *p = NULL;
    else
    {
        *p = (PTree)malloc(sizeof(BTNode));
        (*p) -> ch = ch;
        printf("請輸入%c的左子樹\n", ch);
        createBTree(&((*p) -> lchild));
        printf("請輸入%c的右子樹\n", ch);
        createBTree(&((*p) -> rchild));
    }

}
void preOrderTraverse(PTree p)//前序遍歷
{
    if(p == NULL)
        return ;
    printf("%c ", p -> ch);
    preOrderTraverse(p -> lchild);
    preOrderTraverse(p -> rchild);
}
void InOrderTraverse(PTree p)//中序遍歷
{
    if(p == NULL)
        return;
    InOrderTraverse(p -> lchild);
    printf("%c ", p -> ch);
    InOrderTraverse(p -> rchild);
}
void BackOrderTraverse(PTree p)//后續(xù)遍歷
{
    if(p == NULL)
        return ;
    BackOrderTraverse(p -> lchild);
    BackOrderTraverse(p -> rchild);
    printf("%c ", p -> ch);
}

void preOrderTraverseNorecursion(PTree p)
{
  if(p!=NULL)
    {
      PTree Stack[MaxSize];
      int top = -1;
      PTree q;
      Stack[++top] = p;
      while (top!=-1) {
    q = Stack[top--];
    printf("%c ",q->ch);
    if(q->rchild!=NULL)
      Stack[++top] = q->rchild;
    if(q->lchild !=NULL)
      Stack[++top] = q->lchild;
      }
    }
}



int main()
{
    PTree pt;
    createBTree(&pt);
    preOrderTraverse(pt);
    printf("\n");
    InOrderTraverse(pt);
    printf("\n");
    BackOrderTraverse(pt);
    printf("\n");

    printf("先序非遞歸：\n");
    preOrderTraverseNorecursion(pt);
    printf("\n");
    return 0;
}

寫在后面

和室友一起跑步去嘍，后面先序非遞歸是自己加上去奧，嘿嘿。。。