newtree.cpp

用图的邻接矩阵存取

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1024
typedef int   DataType; 
typedef struct BiNode{
	DataType data;
	 struct BiNode *lchild;
     struct BiNode *rchild;
}BiNode,*BiTree;

typedef struct{
	BiTree data[MAXSIZE];
	int top;
}stack;


void InitStack(stack &S){
//初始化栈
  S.top=0;
}//SqstackInit()


void Push(stack &S,BiTree p){
// 把元素x压入栈，使其成为新的栈顶元素 
	if(S.top> MAXSIZE )
		printf("栈已满!");
	S.data[S.top++]=p;  
}//SqstackPush


int StackEmpty(stack S){
	//判断栈是否为空,若是空返回1;
	if(S.top==0)
	return 1;
	return 0;
}//SqstackEmpty


BiTree GetTop(stack S)
{	
	if(S.top)
		return S.data[S.top-1];
	else 
		return NULL;
}
		

BiTree Pop(stack &S)
 {		//把栈顶元素弹出
	if(S.top!=0)
		return S.data[--S.top];
	else 
		return  NULL;
}//SqstackPop


 void CreatBitree(BiTree &T){
	//按先序输入结点，建立链表表示的二叉树T
	//输入0时结束
	DataType ch;
	printf("输入结点值：");
	scanf("%d",&ch);
	if(ch){
		T=(BiTree)malloc(sizeof(BiNode));
		T->data=ch;
	CreatBitree(T->lchild);
	CreatBitree(T->rchild);
	}//while	
	else T=NULL;
}//CreatBiTree




void PreOrderTraverse(BiTree T)
{//利用二叉树的链表结构实现二叉树的非递归先序遍历

	stack s; BiTree p;
	InitStack(s);
	p=T;
	while(p||!StackEmpty(s))
	{
		while(p)
		{
		printf("%d\n",p->data);
		Push(s,p);
		p=p->lchild;
		}
	p=Pop(s);
	p=p->rchild;
	}

}//PreOrderTraverse

void InOrderTraverse(BiTree T)
{                                          //中序遍历二叉树的非递归算法
	stack s;
	InitStack(s);                              //初始化辅助栈
    BiTree p=T;
	while(p||!StackEmpty(s))
	{                                      //p指向为空并且辅助栈为空的时候循环停止
		if(p)
		{                                  //p指向不是空时
		Push(s,p);                     //p进栈
            p=p->lchild;                   //p指向左子树
		}//if
		else
		{                                  //p指向为空的时候
		p=Pop(s);                      //出栈
			printf("%d",p->data);           //输出p
			p=p->rchild;                   //p指向栈顶元素的右子树
		}//else
	}//while
}


	
void PostOrderTraverse(BiTree T)
{//利用二叉树的链表结构实现二叉树的非递归后序遍历
            		
	stack s; BiTree p=T,pre=NULL;
	InitStack(s);
	while(p||!StackEmpty(s))
	 {
		while(p)
		{
			Push(s,p);
			p=p->lchild;
		}
		p=GetTop(s);
		if(p->rchild==NULL||p->rchild==pre)
		{
			printf("%d",p->data);
			pre=Pop(s);		//pre指向刚刚访问的结点
			p=NULL;
		}
		else
			p=p->rchild;
	 }//while
}//PostOrderTraverse




void main()
{
	BiTree T;
	printf("依次按先序遍历顺序输入各点值：（结点不存在用0代替）\n");
	CreatBitree(T);
	PreOrderTraverse(T);
}