binarytree.cpp

二叉树操作汇总

#include "stdio.h"
#include "stdlib.h"
typedef struct node{
	char ch;
	struct node * lchild,*rchild;
}node,*tree;
int num;
void create(tree &t) //递归建立二叉树
{
	char ch;
	scanf("%c",&ch);
	if(ch=='#') t=NULL;
	else {
      t=(tree)malloc(sizeof(node));
	  t->ch=ch;
	  create(t->lchild);
	  create(t->rchild);
	}
}
void pretraverse(tree t)//前序遍历递归
{
	if(t==NULL);
	else{
		printf("%c",t->ch);
		pretraverse(t->lchild);
		pretraverse(t->rchild);
	}
}
void midtraverse(tree t)//中序遍历递归
{
	if(t==NULL);
	else{
		midtraverse(t->lchild);
		printf("%c",t->ch);
		midtraverse(t->rchild);
	}
}
void lasttraverse(tree t)//后序遍历递归
{
	if(t==NULL);
	else{

		midtraverse(t->lchild);
		midtraverse(t->rchild);
		printf("%c",t->ch);
	}
}
void pre_no(tree t)//前序遍历非递归
{
	struct node *a[20];
	int i=0;
	while(i>=0)
	{
	while(t)
	{
		printf("%c",t->ch);
		if(t->rchild) a[i++]=t->rchild;
		t=t->lchild;
	}
	t=a[--i];
	}
}

void mid_no(tree t)//中序遍历非递归
{
	struct node *a[20];
	int i=0;
	while(t) {a[i++]=t;t=t->lchild;}
	while(i>=1)
	{
		t=a[--i];
		if(t)
		{
           printf("%c",t->ch);
		   t=t->rchild;
           while(t) {a[i++]=t;t=t->lchild;}
		}
	}
}
void cenci(tree t)//层次遍历
{
	struct node *a[20];
	int i=0,j=0;
    a[j++]=t;
	while((j-i)>0)
	{
		t=a[i++];
		printf("%c",t->ch);
		if(t->lchild) a[j++]=t->lchild;
		if(t->rchild) a[j++]=t->rchild;
	}

}
int isfull(tree t)//判定是否完全二叉树
{
	struct node *a[20];
	int i=0,j=0;
	int flag=1;
	if(!t) a[j++]=t;
	while((j-i)>0)
	{
		t=a[i++];
		if(t->lchild) a[j++]=t->lchild;
		if(t->rchild) a[j++]=t->rchild;
		if(t->lchild==NULL&&t->rchild) flag=0;
		if(t->rchild==NULL&&a[i++]->lchild) flag=0;
	}
	return flag;
}
int getdepth(tree t)//二叉树的深度
{
	int m,n;
	if(t==NULL) return 0;
	else{
		m=getdepth(t->lchild);
		n=getdepth(t->rchild);
		return (m>n?m:n)+1;
	}
}
void del(tree t)
{
	if(t==NULL);
	else
	{
		del(t->lchild);
		del(t->rchild);
		//free(t);
	}
}

void search(tree t,char c)//查找二叉树值为c的节点，并返回个数
{
	if(t==NULL);
	else{
		if(t->ch==c) {printf("成功查找到：%c\n",c);del(t);num++;}
	search(t->lchild,c);
	search(t->rchild,c);
	}

}

int main()
{
	tree t;
	char c='a';
	create(t);
	printf("前序遍历的结果是：\n");
    	pre_no(t);
	//	pretraverse(t);
	printf("\n");
	printf("中序遍历的结果是：\n");
//	midtraverse(t);
	mid_no(t);
	printf("\n");
	printf("后序遍历的结果是：\n");
	lasttraverse(t);
	printf("\n");
	printf("二叉树的深度是：\n%d",getdepth(t));
	printf("\n");
	//search(t,c);
	//printf("二叉树中含有%c的个数%d\n",c,num);
    //printf("删除后的前序序列为：\n");
	//pre_no(t);
	printf("层次遍历的结果是：\n");
	cenci(t);
	printf("\n");
	printf("是完全二叉树1，不是 0 %d\n",isfull(t));

    return 1;

}