test.cpp

数据结构中相关ADT的C++实现,注解清晰,让你快速掌握

//二叉树
#include<iostream.h>
#include<stdlib.h>
const int stack_init_size=100;
const int  stackincrement=10;
typedef struct bitnode
{
	char data; 
	bitnode * lchild,* rchild;
}* bitree;
typedef struct
{//栈结构
bitree * base;
bitree * top;
	int stacksize;
}sqstack;
void initstack(sqstack & s)
{//构造一个空栈
	s.base=new bitree  [stack_init_size];
	if(!s.base)return;
	s.top=s.base;
    s.stacksize=stack_init_size;
}
int stackempty(sqstack s)
{
if(s.top==s.base)return 0;
else return 1;
}
void gettop(sqstack s,bitree & e)
{//读取栈顶元素
	if(s.top==s.base)return;
	e=*(s.top-1);
	return ;
}
void push(sqstack & s,bitree e)
{//压栈
	if((s.top-s.base)>=s.stacksize)
	{
		bitree * increase=new bitree[s.stacksize+stackincrement];
		for(int i=0;i<s.stacksize;i++)
		{
		increase[i]=s.base[i];
		}
		s.base=increase;
	
	s.top=s.base+s.stacksize;
	s.stacksize+=stackincrement;
	}
 *s.top++=e;
}
void pop(sqstack & s,bitree & e)
{//弹栈
	if(s.top==s.base)return;
	e=*--s.top;

}
void precreatbitree(bitree & T)
{
//按先序次序输入二叉树中结点的值（一个字符），
	//0字符表示空树，构造二叉链表表示的二叉树T。
	char ch;
	cin>>ch;
	if(ch=='0'){T=NULL;}
	else
	{
		T=new bitnode;//注意不要忘了这一步
		T->data=ch;
		precreatbitree(T->lchild);
		precreatbitree(T->rchild);
	}
}
void preordertraverse(bitree T)
{
//采用二叉链表存储结构,先序遍历二叉树T的递归算法
if(T!=NULL)
	{
		cout<<T->data;
		preordertraverse(T->lchild);
		preordertraverse(T->rchild);
		}
else return;

}
void preordertraverse2(bitree t)
{
//采用二叉链表存储结构,先序遍历二叉树t的非递归算法
/*(1)根结点入栈
(2)若栈非空,弹栈,若弹出元素为空指针,从新执行这一步,若弹出的元素不是空指针,输出其内容,将其右指针入栈再将其左指针入栈;
否则,结束
*/
	bitree p;
	sqstack s;
	initstack(s);
	push(s,t);
	while(stackempty(s))
	{
		pop(s,p);
		if(p!=NULL)
		{
			cout<<p->data;
      push(s,p->rchild);
      push(s,p->lchild);
		}
	}
}
void inordertraverse2(bitree t)
{
//采用二叉链表存储结构,中序遍历二叉树t的非递归算法
/*(1)根结点入栈
(2)向左一直将栈顶元素的左指针入栈,直到栈顶元素为空指针时,弹栈
(3)若栈非空,访问栈顶元素,弹栈;否则,结束
(4)将弹出的元素的右指针入栈,继续回到第(2)步
*/
bitree p;
sqstack s;
initstack(s);
push(s,t);
gettop(s,p);
while(stackempty(s))
{
while(p!=NULL)
{push(s,p->lchild);
gettop(s,p);
}
pop(s,p);
if(stackempty(s))
{
	pop(s,p);
	cout<<p->data;
	push(s,p->rchild);
}
gettop(s,p);
}
}
void inordertraverse(bitree t)
{
//采用二叉链表存储结构,中序遍历二叉树t的递归算法
	if(t!=NULL)
	{
		inordertraverse(t->lchild);
		cout<<t->data ;
		inordertraverse(t->rchild);
	}
	else return;
}
void postordertraverse(bitree t)
{
	//采用二叉链表存储结构,后序遍历二叉树t的递归算法

if(t!=NULL)
	{
		inordertraverse(t->lchild);
		inordertraverse(t->rchild);
cout<<t->data ;
	}
	else return;
}
void postordertraverse2(bitree t)
{
//采用二叉链表存储结构,后序遍历二叉树t的非递归算法
/*(1)判断根结点是否为空指针,是结束,否依次压入根结点和根结点的右左指针
(2)判断栈是否为空,是结束,否则取栈元素,看其是否为空,此时有三种做法:
A.该元素不为空,压入其右左指针
B.该元素为空指针,且是连续第二个空指针,弹栈两次,访问最后弹出的元素,再弹栈到P,压入一个空指针,再把P压入,回到(2)
C.若为第一个空指针,弹栈,回到(2)
其用一个记录弹压次数
*/
	int i=0;
	bitree p;
	bitree q=NULL;
	sqstack s;
	initstack(s);
	if(t!=NULL)
	{
		push(s,t);
		push(s,t->rchild);
		push(s,t->lchild);
		while(stackempty(s))
		{
			gettop(s,p);
			if(p!=NULL&&i==0)
			{
push(s,p->rchild);
push(s,p->lchild);
			}
			else if(p!=NULL&&i==1)
			{
if(stackempty(s))//出口
				{
				pop(s,p);
				push(s,q);
				push(s,p);
				i=0;
				}
				else return;
			}
			else if(i==2)
			{
				pop(s,p);
				cout<<p->data;
				if(stackempty(s))//出口
				{
				pop(s,p);
				push(s,q);
				push(s,p);
				i=0;
				}
				else return;
			}
			else
			{pop(s,p);
			i=i+1;
			}
		}
	}
}

int max(int a,int b)
{
	if(a>=b)return a;
	else return b;
}
int bitreedepth(bitree t)
{
	//求左子树和右子树的深度,比较大小,大的加1为树的深度
	//求左右子树的深度时,又时一次递归
	//递归的出口为:当树为空树,即树根结点为空时,该子树深度为0
//算法时间长度为O(n),n为结点个数
	if(t==NULL)return 0;
	else
return max(bitreedepth(t->lchild),bitreedepth(t->rchild))+1;
}
void main()
{
	bitree t;
	cout<<"按先序次序输入二叉树中结点的值（一个字符）,0字符表示空树:"<<endl;
	precreatbitree(t);
cout<<"两种方法先序遍历树:"<<endl;
preordertraverse2(t);
	cout<<endl;
preordertraverse(t);
cout<<endl;
	cout<<"两种方法中序遍历树:"<<endl;
	inordertraverse2(t);
	cout<<endl;
	inordertraverse(t);
cout<<endl;
cout<<"两种方法后序遍历树:"<<endl;
	postordertraverse2(t);
	cout<<endl;
	postordertraverse(t);
cout<<endl<<"树的深度:"<<endl;
	cout<<bitreedepth(t)<<endl;
}