二叉树的创建、前序遍历后序遍历的递归和非递归实现

二叉树的创建：

#include "stdio.h"
typedef char ElemType;
#define MAXNUM 150

/* 二叉树结点定义 */
typedef struct BTNode
{
    ElemType data;         /* data field */
    struct BTNode *lchild;
    struct BTNode *rchild;    
} BTNode;

/* 辅助的二叉树索引数组 */
BTNode *p[MAXNUM+1];

/* 根据用户输入创建二叉树 */
/* 二叉树结点信息：数据域，以及在完全二叉树中的索引值 */
BTNode *Create_BiTree(void)
{
        BTNode* t = NULL;
        int i;
        int j;
        char ch;
    
        printf("\n enter i, ch :");
        scanf("%d,%c", &i, &ch);
        
        while (i != 0 && ch != '#' )
        {
            BTNode* s = (BTNode*)malloc(sizeof(BTNode));
            s->data = ch;
            s->lchild = s->rchild = NULL;
            
            p[i] = s;
            
            if ( i == 1 )
                t = s;
            else
            {
                j = i/2;
                
                if ( i%2 == 0 )
                    p[j]->lchild = s;
                else
                    p[j]->rchild = s;
            }
            printf("\n enter i, ch :");
            scanf("%d,%c", &i, &ch);
        }
        
        return t;
}

int main(void)
{
    BTNode* t;
    t = Create_BiTree();
/*    
    preorder(t);
    printf(" preorder\n");
    preorder_recursive(t);
    printf(" preorder_recursive\n");

    Inorder(t);
    printf(" Inorder\n");
    Inorder_recursive1(t);
    printf(" Inorder_recursive1\n");
    Inorder_recursive2(t);
    printf(" Inorder_recursive2\n");


    Postorder(t);
    printf(" Postorder\n");
    Postorder_recursive(t);
    printf(" Postorder_recursive\n");

    LevelOrder(t);
    printf(" LevelOrder\n");
*/    
    getchar();
    getchar();

    return 0;
}

 

二叉树的 前序遍历，递归、非递归的实现：

 

/* 前序遍历的递归实现 */
void preorder(BTNode *bt)
{
     if (bt)
   {
           printf("%c ",bt->data);
      preorder(bt->lchild);
      preorder(bt->rchild);
    }
}

/* 前序遍历的非递归实现 */

void preorder_recursive(BTNode *bt)
{
    BTNode* p;
    BTNode* s[MAXNUM+1]; /* 辅助的模拟栈 */
    int top;
    
    p=bt;
    top=-1;
  while(p||top != -1)
  {
         if(p)
       {
           printf("%c ",p->data);
      ++top;
      s[top]=p;
      
      p=p->lchild ;
     } /*p移向左孩子*/
     else /*栈非空*/
     {
           p=s[top];
           --top;
        p=p->rchild;
     }
   }
}


 

二叉树的 中序遍历，递归、非递归的实现：

 

/* 中序遍历的递归实现 */
void Inorder(BTNode *bt)
{
  if (bt)
  {
      Inorder(bt->lchild);
    printf("%c ",bt->data); /* 访问根结点 */
    Inorder(bt->rchild);
  }
} /* inorder */

/* 中序遍历的非递归实现 */
void Inorder_recursive1(BTNode *bt )
{
        BTNode* p,*s[MAXNUM+1];
        int top;
        p=bt;
        top=-1;
      while(p||top != -1)
      {
          if(p)
          {
               ++top;
         s[top]=p;
         p=p->lchild ;
      } /*p移向左孩子*/
      else /*栈非空*/
      {
           p=s[top];
           --top;
                printf("%c ",p->data);
        p=p->rchild;
      }
        }
}

/* 中序遍历的非递归实现 */
void Inorder_recursive2(BTNode *bt)
{
        BTNode* p,*s[MAXNUM+1];
        int top;
        p=bt;
        top=-1;

        while(p||top != -1)
        {
            if(p && p->lchild)
            {
                ++top;
                s[top] = p;
                p = p->lchild;
            }
            else
            {
                if (p)
                    printf("%c ", p->data);
                if (p && p->rchild )
                {
                    p = p->rchild;
                }
                else if ( top >= 0)
                {
                    p = s[top];
                    top--;
                    printf("%c ", p->data);
                    p = p->rchild;
                }
                else
                    break;
            }
        }
}


 

二叉树的 后序遍历，递归、非递归的实现：

 

/* 后序遍历的递归实现 */
void Postorder(BTNode *bt)
{
     if (bt)
     {
         Postorder(bt->lchild);
      Postorder(bt->rchild);
      printf("%c ",bt->data);
  }
}
/* 后序遍历的非递归实现 */
void Postorder_recursive(BTNode *pt)
{
    BTNode *s[MAXNUM+1];
    int top = -1;

    BTNode *p = pt;
    BTNode *pre = NULL;

    while ( p || top != -1 )
    {
        if (p )
        {
            ++top;
            s[top] = p;
            p = p->lchild;
            pre = p;
        }
        else
        {
            p = s[top];
        //    --top;



            if ( p->rchild == NULL || p->rchild == pre )
            {
                p = s[top];
                --top;
                printf("%c ", p->data);
                pre =p;
                p = NULL;
            }
            else
            {
                p = p->rchild;
                pre = p;
            }
        }
    }
}        

层次遍历：

 

 

/*层次遍历二叉树*/
void LevelOrder(BTNode *bt)
{
    BTNode* queue[100];
  int front=0,rear=0;
  
  if (bt==NULL)
      return;
  
  queue[rear]=bt;
  rear++;
    
    do
    {
        printf("%c ",queue[front]->data);
    
    /*访问队首结点的数据域*/
    if (queue[front]->lchild!=NULL)
    /*将队首结点的左孩子结点入队列*/
    {
        queue[rear]=queue[front]->lchild;
        rear++;
    }
    
    if (queue[front]->rchild!=NULL)
    /*将队首结点的右孩子结点入队列*/
      {
          queue[rear]=queue[front]->rchild;
          rear++;
      }
      front++;
  }while(front!=rear);
}