inbitr2.c

来自「《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构」· C语言 代码 · 共 66 行

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node            /*二叉树结点定义*/
 {
  datatype data;
  struct node *lchild,*rchild;
  }bintnode;
typedef bintnode *bintree;
typedef struct stack         /*栈结构定义*/
     { bintree data[100];
       int tag[100];          /*为栈中每个元素设置的标记，用于后序遍历*/
       int top;              /*栈顶指针*/
     } seqstack;
/****************************************/
 void push(seqstack *s,bintree t)  /*进栈*/
  { s->data[++s->top]=t;
  }
/*****************************************/
 bintree pop(seqstack *s)  /*出栈*/
 { if (s->top!=-1)
      {s->top--;
      return(s->data[s->top+1]);}
      else
      return NULL;
 }
/******************************************/
void createbintree(bintree *t)       
{/*按照前序遍历的顺序建立一棵给定的二叉树*/ 
 char ch;
 if ((ch=getchar())==' ')
      *t=NULL;
      else {
	  *t=(bintnode *)malloc(sizeof(bintnode));
	  (*t)->data=ch;
	  createbintree(&(*t)->lchild);
	  createbintree(&(*t)->rchild);
      }
 }
/*****************************************/
void inorder1(bintree t)    /*非递归实现二叉树的中序遍历*/
 { seqstack s;
   s.top=-1;
   while((t!=NULL) || (s.top!=-1))
     {  while (t)
	     {  push(&s,t);
	        t=t->lchild;
	      }
	    if (s.top!=-1)
	     {  t=pop(&s);
	        printf("%c ",t->data);
	        t=t->rchild;
	     }
      }
 }


main()     /*主程序*/
  { bintree root;
    printf("\n");
    createbintree(&root);
    printf("\n");
    printf("\n中序遍历结果是: ");
    inorder1(root);
}