visit.cpp

这个程序采用先序建立二叉树

#include<stdio.h>//头文件
#include<malloc.h>//动态分配内存的头文件

typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;//二叉树中结点的结构

bool CreateBiTree(BiTree &T)//建立二叉树
{
	char ch;
	scanf("%c",&ch);//读入该结点的值
	if (ch=='0') T=NULL;//若输入0，表示该结点为空
	else {
	       T=(BiTNode *)malloc(sizeof(BiTNode));//分配内存
		   T->data=ch;//保存该结点的值
		   CreateBiTree(T->lchild);//创建该结点的左子树
		   CreateBiTree(T->rchild);//创建该结点的右子树
	}
	return 1;//返回真
}

void Preorder(BiTree &T)//递归，先序遍历
{
	 if (T!=NULL)//判断该结点是否为空
	 {
	  printf("%c",T->data);//打印该结点的数据
	  Preorder(T->lchild);//先序遍历左子树
	  Preorder(T->rchild);//先序遍历右子树
	 }
}

void Inorder(BiTree &T)//递归，中序遍历
{
	if (T!=NULL)//判断该结点是否为空
	{
	  Inorder(T->lchild);//中序遍历左子树
	  printf("%c",T->data);//打印该结点的数据
	  Inorder(T->rchild);//中序遍历右子树
	}
}

void Postorder(BiTree &T)//递归，后序遍历
{
	if (T!=NULL)//判断该结点是否为空
	{
		Postorder(T->lchild);//后序遍历左子树
        Postorder(T->rchild);//后序遍历右子树
		printf("%c",T->data);//打印该结点的数据
	}
}

void preorder1( BiTree  b)//非递归，先序遍历
  { BiTree stack[100],p;//stack[]用来保存访问过程中的结点的指针
     int top;  //top指向当前的栈顶
     if (b!=NULL)
       { top=1;               //根结点入栈
          stack[top]=b;
          while (top>0)       //栈不为空时循环
             {p=stack[top];   //退栈并访问该结点
               top--;
               printf("%c",p->data);//输出该结点的数据
               
              if (p->rchild!=NULL)     //若右孩子存在，则入栈
                  { top++;         
                     stack[top]=p->rchild;}
              if (p->lchild!=NULL)    //若左孩子存在，则入栈 
                   { top++;
                      stack[top]=p->lchild;
                   }
              }
         }
    }

void Inorder1(BiTree &T)//非递归，中序遍历
{
	BiTree stack[100],p;//stack[]用来保存访问过程中的结点的指针
	int top=0;//top指向当前的栈顶
	p=T;//p首先被赋值为根结点
    do
	{
		while (p!=NULL)//该结点不为空，则进栈
		{
			top++;  //栈顶上移
			stack[top]=p;//该结点进栈
			p=p->lchild;//并开始访问该结点的左孩子
		}
		if (top>0)//栈不为空
		{ 
			p=stack[top];//p为栈顶元素
			top--;//出栈一个元素
			printf("%c",p->data);//打印该结点的数据
			p=p->rchild;//访问右孩子
		}
	}while ((p!=NULL)||(top!=0));
}

void postorder1( BiTree  &T)//非递归，后序遍历
{
     BiTree stack[100],p;//stack[]用来保存访问过程中的结点的指针
     int tag[100], top=0; //tag[]表示stack[]相应的结点是否访问
     p=T;
     do
       { while (p!=NULL)                   //扫描左结点，不为空则进栈
            { top++;//栈顶上移
               stack[top]=p;//该结点的指针进栈
               tag[top]=0;//此结点没有被遍历，过被赋值为0
               p=p->lchild;//访问左子树
            }
          //p所指结点为无左子树的结点或其左子树已遍历过
	      if(top>0){
		     if(tag[top]==1)
			 {                                     // p的左右子树都访问过
				 printf("%c",stack[top]->data);top--;//栈顶下移，打印该结点的数据
			 }
		    else{p=stack[top];
		        if(top>0){p=p->rchild; tag[top]=1;}//访问结点
			}
		  }
	     //扫描右子树
         //表示当前结点的右子树已访问过
          } while (top!=0);
}
void main()
{   BiTree T=NULL;
    printf("按照先序建立二叉树,空结点输入0,非空结点输入结点数据\n");
	printf("请建立二叉树:");
    CreateBiTree(T);//调用创建二叉树的函数
	printf("使用递归方法实现先序输出:");
	Preorder(T);//递归先序遍历
	printf("\n");
	printf("使用非递归方法实现先序输出:");
	preorder1(T);//非递归先序遍历
	printf("\n");
  
	printf("使用递归方法实现中序输出:");
	Inorder(T); //递归中序遍历
	printf("\n");
	printf("使用非递归方法实现先序输出:");
	Inorder1(T);//非递归中序遍历
	printf("\n");

	printf("使用递归方法实现后序输出:");
	Postorder(T);//递归后序遍历
	printf("\n");
	printf("使用非递归方法实现后序输出:");
	postorder1(T);	////非递归后序遍历
	printf("\n");
}