树的操作.cpp

树的各种基本操作都包括了

#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 100
typedef struct bitnode
{int data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;

typedef struct 
{bitree *base;
int front;
int rear;
}sqqueue;

initqueue(sqqueue &q)
{q.base=(bitree*)malloc(MAXQSIZE*sizeof(bitree));

if(!q.base) exit(0);
q.front=q.rear=0;
}

enqueue(sqqueue &q,bitree e)
{if((q.rear+1)%MAXQSIZE==q.front)
{printf("队已经满了\n");

return NULL;
}
q.base[q.rear]=e;

q.rear=(q.rear+1)%MAXQSIZE;
}

dequeue(sqqueue &q, bitree &e)
{if(q.front==q.rear) return NULL;
e=q.base[q.front];

q.front=(q.front+1)%MAXQSIZE;
}

int empty(sqqueue &q)
{int n;
	if(q.front==q.rear)  n=0;
else n=1;
return n;
}


bitree create()
{int ch;
bitree t;
scanf("%d",&ch);
if(ch==32767)
t=NULL;

else
{if(!(t=(bitnode*)malloc(sizeof(bitnode))))
exit(0);
t->data=ch;
//printf("%d\n",t->data);
t->lchild=create();
t->rchild=create();
}
return t;
}

void preorder(bitree root)
{
	if(root)
{printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}

void inorder(bitree root)

{
	if(root)
{inorder(root->lchild);
printf("%d ",root->data);
inorder(root->rchild);
}
}

void postorder(bitree root)

{
	if(root)
{postorder(root->lchild);
postorder(root->rchild);
printf("%d ",root->data);

}
}

void layerorder (bitree t)
{sqqueue q;
bitree x;
	initqueue(q);

enqueue(q,t);
while(empty(q))
{dequeue(q,x);
printf("%d ",x->data);
if(x->lchild) enqueue(q,x->lchild);
if(x->rchild) enqueue(q,x->rchild);
}
}


int depth(bitree root)
{int n1,n2;
int n;
	if(!root) return NULL;
else
{n1=depth(root->lchild);
n2=depth(root->rchild);
if(n1<=n2)
n=n2+1;
else n=n1+1;
return n;
}
}

int  total(bitree root)
{int s;
if(root==NULL) return 0;
else 
{s=total(root->lchild)+total(root->rchild)+1;

return s;
}
}

bitree  parent(bitree root,int x,bitree p)
{bitree t,m;
if(!root) return NULL;

 if(root->data==x)
{ t=root;

if(p==t)
printf("%d没有父节点,它为根\n",x);
else
 printf("%d 的父节点为:%d\n",x,p->data);
return t;
}
else 
{p=root;
		
t=parent(root->lchild,x,p);
	
if(!t)
{p=root;
t=parent(root->rchild,x,p);
}
return t;	}
}



void main()
{int n;
char m;
bitree t,p,r;
int tot;
int dep;
int d;
while(1)
{ 
	printf("输入选择项Y__建立二差树;N——不再建立\n");
	scanf("%c",&m);
if(m=='Y')
{

printf("建立一个二叉树\n"); 
t=create();
while(1)
{printf("对该二叉树进行操作1--先序访问;2--中序访问;3--后序访问\n4--求深度;5--节点总数;6--求父节点;7__按层次遍历0--退出有关该操二叉树的操作\n");
scanf("%d",&n);
char c=getchar();
if(n==0)break;
switch(n)
{case 1: preorder(t);
printf("\n");
break;
case 2:  inorder(t);
	printf("\n");
	break;
case 3:  postorder(t);
printf("\n");
break;
case 4:  dep=depth(t);
	printf("该树的深度为%d\n",dep);
	break;
case 5: tot=total(t);
	printf("该二叉树的节点总数为%d\n",tot);
	break;
case 6: printf("输要找的数\n");
	scanf("%d",&d);

	p=t;
   r=parent(t,d,p);
   if(r==NULL)
	   printf("二叉树中没有该节点\n");
	break;

case 7: layerorder(t);
	break;
}
}

}


else break;
}
}