二叉树.cpp

二叉树算法！ ＶＣ＋＋６．０下开发～！

// 二叉树.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 5
#define NULL 0

// 用二叉树的顺序存取结构，用非递归中序遍历算法遍历二叉树；
int main(int argc, char* argv[])
{
	typedef struct{
		int *base;
		int *top;
		int stacksize;
	}SqStack;     //定义堆栈；
	SqStack s;
	s.stacksize=STACK_INIT_SIZE;
	s.base=new int[s.stacksize];
	s.top=s.base;
	int *Array;    //建立一个数组，用顺序存储结构存储二叉树；
	Array=new int[7];
	for(int i=1; i<7; i++)  //输入数据；
	scanf(" %d ", &Array[i]);
	Array[0]=6;        //数组第一个元素用来存放二叉树结点个数；
	int j=1, t=0; //j表示每个结点左子树的最后一个结点，t表示二叉树根结点的访问次数；
	while(t<=1)   //二叉树根结点的访问次数最多为一次，所以t<=1;
	{  
		for(i=j; i<7; i*=2)//走到每个结点左子树的最后一个结点,把所经过的结点压入堆栈；
		{
			*s.top=i;
			s.top++;
		}
		s.top--;  //空指针退栈；
		if(t<=1)
		{
			j=*s.top;
			printf(" %d ", Array[j]); //访问父结点的左子树；
			s.top--;
			j=*s.top;
			printf(" %d ", Array[j]); //访问父结点；
			j=j*2+1;
			if(s.top==s.base)
			t+=1;  //访问一次二叉树的根结点,t加1；
		}
	}
     return 0;
}