二叉树作业

设二叉树的顺序存储如下：
34 56 78 23 11 92 65 74 ∧ 85 36
（1）给出此树的图示；
（2）给出此树的二叉链表表示；
（3）给出树的二叉链表的构造算法，同时以括号表示法输出。
（4）在（3）的基础上，给出树的中序遍历的非递归算法和层次遍历算法并将遍历结果存储到一维数组t1和t2中。
（5）利用t1数组实现顺序查找算法。
（6）利用t2数组实现堆排序算法，并进行算法分析。

解答：
（1）

（2）

（3）

（4）

（5）

（6）

#include
typedef int ElemType;
unsigned int num=1,num1=0;
#define stackSize 100
typedef struct BiNode
{
    ElemType data;
    BiNode *lchild, *rchild;
}Bino;
typedef struct //顺序栈的储存结构
{
	Bino *rear;
	Bino *top;
	int stacksize;
}SqStack;
void Creat(BiNode *&root)//二叉树构建函数
{
	 
	 ElemType ch;
	 cin>>ch;
	if(ch==0)   
	  {root=NULL; }
      else {
        root=new BiNode; 
        root->data=ch;
        Creat(root->lchild); 
        Creat(root->rchild); 
	 } 
}
int InitStack(SqStack &S)//初始化顺序栈

{
	S.rear=new Bino[100];
	if(!S.rear) return 0;
	S.top=S.rear;
	S.stacksize=100;
	return 1;
}
int StackEmpty(SqStack &S)//判断栈是否为空
{
	if(S.rear==S.top)
		return 1;
	else 
		return 0;
}
int Push(SqStack &S,Bino *p)//入栈函数
{
	if(S.top-S.rear==S.stacksize)return 0;
	*S.top++=*p;
	return 1;
}
int Pop(SqStack &S,Bino *q)//出栈函数
{
	if(S.top==S.rear)return 1;
	*q=*--S.top;
	return 0;
}
void InorderTraver(Bino *T,ElemType t1[])//中序遍历函数
{
	SqStack S;
	InitStack(S);
	Bino *p,*q;
	p=T;
	q=new Bino;
	while(p||!StackEmpty(S))
	{
		if(p)
	{
		Push(S,p);
		p=p->lchild;
	}
		else 
	{
        Pop(S,q);
		t1[num]=q->data;
		num++;
        cout<data<<" ";
        p=q->rchild;
	}
	}
}
void PrinTree(BiNode *root)//二叉树括号法输出函数
{
	if(root==NULL) return;
	else
	{
		cout<data;            
		if(root->lchild != NULL || root->rchild != NULL )
	    {
	    	cout << "(";
	    	PrinTree(root->lchild);       
	    	if(root->rchild != NULL)
	        	cout << ",";
	    	PrinTree(root->rchild); 
	    	cout << ")";
		}
	}
} 
void Leveorder(BiNode *root,ElemType t2[])//层次遍历函数，t2数组为需要遍历的数组
{
   BiNode *Q[30],*p;
   int front,rear;  
   if(root == NULL) 
	  return;
   front=0;
   rear=0;
   Q[++rear]=root;
   while(front!=rear)
   {
     front++; 
	 p=Q[front];
	 t2[num1]=p->data;
	 num1++;
     cout<data<<" ";
     if(p->lchild!=NULL)
        {
		 rear++;Q[rear]=p->lchild;
		}
     if(p->rchild!=NULL)
         {rear++;Q[rear]=p->rchild;}
   }
}
void swap(ElemType *a,ElemType *b)//数组交换函数，a，b为需要交换的数组。
{
	ElemType temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
int find(ElemType t1[],ElemType k,int n)//顺序查找函数，t1为需要所查找的数组，k为需要查找的元素项，n为该数组长度。
{
	int i;
	t1[0]=k;
	for(i=n;i>=0;i--)
		if(t1[i]==k)
			break;
		return i;
}
void duibulid(ElemType arr[],int start,int end)//堆重建函数，arr为需要的重建的数组，start为需要重建的数组的起始位置，end为最终位置
{
    int dad=start;
    int son=dad*2+1;
    while (son<=end)
    {    
        if(son+1<=end&&arr[son]arr[son]) 
            return;
        else
        {
            swap(&arr[dad],&arr[son]);
            dad=son;
            son=dad*2+1;
        }
    }
}
 
void duipaixu(ElemType arr[],int len) //堆排序函数，将每次查找的堆顶点放到堆得末尾，len为数组的长度。
{
	int i;
    for(i=len/2-1;i>=0;i--)
        duibulid(arr,i,len-1);
    for (i=len-1;i>0;i--) 
    {
        swap(&arr[0],&arr[i]);
        duibulid(arr,0,i-1);
    }
}
void main()
{
	int n,i;
	ElemType k;
	ElemType t1[11],t2[10];
	BiNode *root;
	cout<<"先序输入，“0”为空节点："<>k;
	n=find(t1,k,len1);
	if(n==0)
		cout<<"没有这个数"< 
需要输入的数据：
 
 
 
34 56 23 74 0 0 0 11 85 0 0 36 0 0 78 92 0 0 65 0 0