二叉链表.cpp

建立二叉树的链式存储结构

/*建立二叉树的链式存储结构，在此基础上完成下列算法：
1）	从键盘上输入二叉树的各个结点，建立二叉链表
2）	输出该二叉树；
3）	非递归的层次遍历序；
4）	非递归的先序遍历、中序遍历、后序遍历；
*/

#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#define Maxlength 10
typedef char TelemType;
typedef struct BiTNode{
      TelemType data;//存放二叉树中结点值
      struct BiTNode *lchild,*rchild;    /*左右孩子指针*/
   }BiTNode,*BiTree;
//从键盘上输入二叉树的各个结点，建立基于先序遍历的二叉链表。
BiTNode *createbittree()
{
	
	BiTNode *t;
	char ch;
	cin>>ch;                            //输入二叉树的各个结点
	if(ch=='#')return 0;                //如果输入的结点值为‘#’，则该结点为空
	else 
	{
		t=new BiTNode;              //申请一个新的二叉树的结点空间   
		t->data=ch;                 //输入的信息为根结点的值
		t->lchild=createbittree();  //递归建立二叉树的左子树
		t->rchild=createbittree();  //递归建立二叉树的右子树
		return t;                   //返回建立的二叉树
	} 
}
//按先序遍历输出该二叉树
void output( BiTNode   * t ) 
{
   
    if ( t != NULL )               //如果二叉树为非空
	{   
        cout << t->data<<" ";      //输出根结点信息
        output( t->lchild );       //递归访问二叉树的左子树
        output(t->rchild );        //递归访问二叉树的右子树
    }
}
//非递归的层次遍历序
void depthorder(BiTNode *t)
{
	BiTNode *Q[Maxlength];
	int front=0,rear=0;                     //把队列的队首和队尾指针的值值为零，队列为空
     BiTNode *p;
	 if(t!=NULL)
	 {
		 rear=(rear+1)%Maxlength;       //后移队尾指针
		 Q[rear]=t;                     //将树根结点指针进栈
	 }
	 while(front!=rear)                     //如果队列非空，则执行循环
	 {
		 front=(front+1)%Maxlength;     //后移队首指针
		 p=Q[front];                    //删除队首结点
		 cout<<p->data<<"  ";           //输出队首结点的值
		 if(p->lchild!=NULL)            //如果结点存在左孩子，则左孩子结点指针进队
		 {
		      rear=(rear+1)%Maxlength;  //后移队尾指针
		      Q[rear]=p->lchild;        //将左孩子结点指针进栈
		 }
		 if(p->rchild!=NULL)            //如果结点存在右孩子，则右孩子结点指针进队
		 {
		      rear=(rear+1)%Maxlength;  //后移队尾指针
		      Q[rear]=p->rchild;        //将右孩子结点指针进栈
		 }
	 }
}
//非递归的先序遍历
void preorder(BiTNode *t)
{

	BiTNode *s[100];                        //定义一个指针类型的堆栈                
	int top=0;                              //把栈顶单元的值附为零
	while(t!=0||top!=0)                     //栈顶单元不为零或二叉树不为空，则执行循环
	{
		while(t!=0)                     //二叉树不为空                 
		{
			cout<<t->data<<"  ";    //输出二叉树的结点
			s[++top]=t;             //把二叉树的结点入栈
			t=t->lchild;
		}
		if(top!=0)                      //如果栈不为空                
		{
			t=s[top--];             //栈顶单元的信息出栈
			t=t->rchild;
		}
	}
}
//非递归的中序遍历
void inorder(BiTNode *t)
{

	BiTNode *s[100];                        //定义一个指针类型的堆栈 
	int top=0;                              //把栈顶单元的值附为零
	while(t!=0||top!=0)                     //栈顶单元不为零或二叉树不为空，则执行循环
	{
		while(t!=0)                     //二叉树不为空
		{
			
			s[++top]=t;             //把二叉树的结点入栈 
			t=t->lchild;
		}
		if(top!=0)                      //如果栈不为空
		{
			t=s[top--];             //栈顶单元的信息出栈    
			cout<<t->data<<"  ";    //输出结点信息
			t=t->rchild;
		}
	}
}
//非递归的后序遍历
void postorder(BiTNode *t)
{

	typedef struct{
                        BiTNode *t;      
                        int tag; //定义一个标志位  
                      }stack;
	stack s[100];
	int top=0;
    while(t!=0||top!=0)      //当栈顶指针不为零或二叉树不为空时循环
	{
		while(t!=0)       //二叉树不为空时循环
		{
			
			s[++top].t=t;
			s[top].tag=0; 
			t=t->lchild;
		}
		while(top&&s[top].tag==1) //当栈顶指针不为零且标志位为s[top].tag==1输出栈顶元素
			cout<<s[top--].t->data<<"  ";                                                                                      
		if(top!=0)//当栈顶指针不为零
		{
			s[top].tag=1;  //标志位值为一
			t=s[top].t->rchild; //
		}
	}
}
void print1()
{
cout<<"                   * * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<"                   * * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<"                   * * * * *二叉树的非递归遍历算法 * * * * *"<<endl;
cout<<"                   * * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<"                   * * * * * * * * * * * * * * * * * * * * *"<<endl;
}
void print2()
{
cout<<"*******************************************"<<endl;
cout<<"*   *   *   *    该程序要实现的主要功能:    *    *    *    *"<<endl;
cout<<"*   *   *   *    *    *    *    *     *     *    *    *    *"<<endl;
cout<<"*   *   1------输出该二叉树---------------output(t1)  *    *"<<endl;
cout<<"*   *   2------非递归的层次遍历-------depthorder(t1)  *    *"<<endl;
cout<<"*   *   3------非递归的先序遍历---------preorder(t1)  *    *"<<endl;
cout<<"*   *   4------非递归的中序遍历----------inorder(t1)  *    *"<<endl;
cout<<"*   *   5------非递归的后序遍历--------postorder(t1)  *    *"<<endl;
cout<<"*   *   *   *    *    *    *    *     *     *    *    *    *"<<endl;
}
void main()
{
print1();
BiTNode *t1;int k;
cout<<"建立基于先序遍历的二叉链表:"<<endl;
t1=createbittree();
print2();
for(int i=1;i<=5;i++)
{
cout<<"选择的功能是:";
cout<<"which one?(1---5)"<<endl;
cin>>k;
switch(k)
{
case 1:
output(t1);break;
case 2:
depthorder(t1);break;
case 3:
preorder(t1);;break;
case 4:
inorder(t1);break;
case 5:
postorder(t1);break;
}
cout<<endl;
 cout<<"*******************************************"<<endl;
}
}