erchashu.cpp

自己编写了数据结构上的二叉树树所有实现算法

#include<iostream.h>
#include<stdlib.h>
#define Maxsize 100
typedef char ElemType;
struct BTreeNode
{
	ElemType data;  //接点的数据
    BTreeNode *lchild; //左孩子
    BTreeNode *rchild; //右孩子
};

//二杈树的初始化
void IniBTree(BTreeNode * &root)
{
	root=NULL;   //根接点赋值为空
}

//二杈树的创建
void creatBT(BTreeNode * &root)
{
    BTreeNode *q[Maxsize];  //申请一个指针数组，存放接点的地址
    BTreeNode *s;  //申请的新接点
	int froot=1,rear=0; //队首指针赋为1，队尾指针赋为0
	char ch;
	cout<<"请输入二杈树接点的元素（注意！先输入根接点，再输入左孩子，最后输入右孩子）。"<<endl;
	cout<<"虚接点用“，”表示，输入“#”表示结束创建。"<<endl;
	cin>>ch;  
	while(ch!='#')  //如果二杈树的创建没有结束
	{
		s=NULL;  //新接点暂时赋为空
		if(ch!=',')  //如果石二杈树上的元素机不是虚接点
		{
			s=new BTreeNode; 
			s->data=ch;
			s->lchild=NULL;
			s->rchild=NULL;
		}
		q[++rear]=s; //所有虚实接点进队
		if(rear==1)  //让根接点指向第一个元素
			root=s;
		else
		{
			if(s!=NULL&&q[froot]!=NULL)//如果不是虚接点，并且队首元素还有左右孩子
				if(rear%2==0) //如果是左孩子
					q[froot]->lchild=s;
				else
                    q[froot]->rchild=s;
				if(rear%2==1)//如果队首元素的左右孩子都进队
					froot++; //队首指针下移 
		}
		cin>>ch;//输入新元素
	}
}



//输出二杈树
void printbt(BTreeNode *root)
{
	if(root!=NULL)
	{
		cout<<root->data;
		if(root->lchild!=NULL||root->rchild!=NULL)
		{
			cout<<"(";
			printbt(root->lchild);
			if(root->rchild!=NULL)
				cout<<",";
			printbt(root->rchild);
			cout<<")";
			
		}
	}
}



//前序遍历
void proorder1(BTreeNode * root)
{
    BTreeNode *s[Maxsize];//定义一个栈
    BTreeNode  *p=root;
	int top=-1;
    cout<<"前序输出的结果为：";
	while(p!=NULL||top>-1)
	{
		while(p!=NULL)
		{
			cout<<p->data<<"  ";
			if(p->rchild!=NULL)   //让有右孩子的接点进栈
				s[++top]=p;
			p=p->lchild;
		}
		if(top>-1) //栈不为空，表明此接点有右孩子
		{
			p=s[top--];
			p=p->rchild;
		}
	}
	cout<<endl;
}


//中序遍历
void inorder1(BTreeNode *  root)
{
    BTreeNode *s[Maxsize];//定义一个栈
    BTreeNode  *p=root;
	int top=-1;
    cout<<"中序输出的结果为：";
	while(p!=NULL||top>-1)
	{
		while(p!=NULL)
		{
			s[++top]=p;
			p=p->lchild;
		}
		p=s[top--];
        cout<<p->data<<"  ";
		p=p->rchild;
	}
	cout<<endl;
}

//后序遍历
void postorder(BTreeNode * root)
{
	int top=-1,b=0,i=0;
    BTreeNode *s1[Maxsize];//定义一个栈存放接点的地址
	int s2[Maxsize];//定义一个栈测试接点第二次进栈
    BTreeNode *p=root;
    cout<<"后序输出的结果为：";
	while(top>-1||i==0)
	{
		i=1;
		while(p!=NULL)//左子树全部进栈
		{
			s1[++top]=p;
			s2[top]=0;
			p=p->lchild;
		}
		if(top>-1)
		{
			b=s2[top];
			p=s1[top--];
			if(b==0)//判断接点是否第二次进栈
			{
				s1[++top]=p;
				s2[top]=1;
				p=p->rchild;
			}
			else
			{
				cout<<p->data<<"  ";
				p=NULL;
			}
		}
	}
	cout<<endl;
}


//按层输出
void level(BTreeNode * root)
{
	BTreeNode *q[Maxsize];
	int front=0,rear=0;
    BTreeNode *p=root;
     cout<<"按层输出的结果为：";
	if(p!=NULL)
	{
		cout<<p->data<<"  ";
		q[rear++]=p;
	}
	while(rear>front)
	{
		p=q[front++];
        if(p->lchild!=NULL)
		{
			cout<<p->lchild->data<<"  ";
			q[rear++]=p->lchild;
		}
        if(p->rchild!=NULL)
		{
			cout<<p->rchild->data<<"  ";
			q[rear++]=p->rchild;
		}
	}
	cout<<endl;
}

//求二杈树的深度
int depthbt(BTreeNode * root)
{
	if(root==NULL)
		return 0;
	else
	{
		int dep1=depthbt(root->lchild);
        int dep2=depthbt(root->rchild);
		if(dep1>dep2)
			return dep1+1;
		else
			return dep2+1;
	}
}


 present(BTreeNode * root)
{
    BTreeNode *s1[Maxsize];//定义一个栈存放接点的地址
	int s2[Maxsize];//定义一个栈测试接点第二次进栈
    BTreeNode  *p=root;
	int top=-1,i=0,g=0,b=0;
    ElemType h;
    cout<<"请输入你要查找的接点：";
	cin>>h;
    if(h==root->data)
	{
		cout<<"此接点为根接点";
	    return;
	}
	while(top>-1||i==0)
	{
		i=1;//控制循环，使根接点进栈
		while(p!=NULL)//左子树全部进栈
		{	
			if((h==p->data))
			{
				g=1;//接点找到的标志
				break;//跳初内循环
			}	
			s1[++top]=p;
			s2[top]=0;
			p=p->lchild;
		}
		if(g==1)
			break;//跳初外循环
		if(top>-1)
		{
			b=s2[top];
			p=s1[top--];
			if(b==0)//判断接点是否第二次进栈
			{
				s1[++top]=p;
				s2[top]=1;
				p=p->rchild;
			}
		}
	}
    cout<<h<<"的祖先为：";
	for(int j=0;j<=top;j++)
	{
		cout<<s1[j]->data<<"  ";
	}
	cout<<endl;
}





//主函数
void main()
{
    BTreeNode *root;
    IniBTree(root);  //二杈树链表的初始化
    creatBT(root);  //二杈树链表的创建
	cout<<"所操作的二杈树为：";
    printbt(root);//输出二杈树
	cout<<endl;
    proorder1(root);//前序遍历
    inorder1(root);//中序遍历
    postorder(root);//后序遍历
    level(root);//按层遍历
	cout<<"二杈树的深度为："<<depthbt(root)<<endl;//求二杈树的深度
    present(root);
}