【漫跨】二叉树的三种遍历

写在前面

已经坚持了9周明显感觉到自己体力跟不上，所以得养成每晚跑步的好习惯才行呢。这个周五下午感觉头有点昏沉，遂偷懒，回来配置了下emacs，然后敲一敲二叉树....

正文

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct BTNode
{
    char ch;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode, *PTree;//定义树节点的结构体
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)//后续遍历
{
    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;
}

写在后面

和室友一起跑步去喽，后面先序非递归是自己加上去奥，嘿嘿。。。