数据结构备考——第五章二叉树

#include
using namespace std;

//二叉树的链式存储结构    ok
typedef struct BNode{
	ElemType data;
	struct BNode *lchild,*rchild;
}BNode,*BTree;

//先序遍历的方式建立二叉链表   ok
char ch;
void CreateT(BTree &T){
	cin>>ch;
	if(ch=='#'){
		T=NULL;
	}
	else{
		T=new BNode;
		T->data=ch;
		CreateT(T->lchild);
		CreateT(T->rchild);
	}
}

//复制二叉树   ok
void Copy(BTree T,BTree &NewT){
	if(T==NULL){
		NewT=NULL;
		return;
	}
	else{
		NewT=new BTree;
		NewT->data=T->data;
		Copy(T->lchild,NewT->lchild);
		Copy(T->rchild,NewT->rchild);
	}
}
//二叉树中叶结点的个数   ok
int nodecount(BiTree T){
	if(T==NULL){
		return 0;
	}
	if(T->lchild==NULL&&T->rchild==NULL){
		return 1;
	}
	else return nodecount(T->lchild)+nodecount(T->rchild);
}

//二叉树中结点的个数
int nodecount(BiTree T){
	if(T==NULL){
		return 0;
	}
	else return 1+nodecount(T->lchild)+nodecount(T->rchild);
}

//判别两棵树是否相等   参数是BiNode * 类型 ok
bool issame(BiNode *T1,BiNode *T2){
	if(T1==NULL&&T2==NULL){
		return true;
	}
	if(T1==NULL||T2==NULL){
		return false;
	}
	if(T1->data!=T2->data){
		return false;
	}
	else{
		if(issame(T1->lchild,T2->lchild)&&issame(T1->rchild,T2->rchild)){
			return true;
		}
	}
}

//层次遍历二叉树，统计度为1的结点数目  改正了，首先要保证树不为空    参数是BiTree类型，不是BiNode *类型
//还需要再次修改****************
int nodecount(BiTree T){
	int num=0;
	if(T){
		BiTree p;
		SQueue Q;
		InitQ(Q);
		Queuein(Q,T);
		while(!EmptyQ(Q)){
			p=Queueout(Q);
			cout<data;
			if(p->lchild!=NULL) Queuein(Q,p->lchild);
			if(p->rchild!=NULL) Queuein(Q,p->rchild);
			if((p->lchild==NULL&&p->rchild!=NULL)||(p->lchild!=NULL&&p->rchild==NULL)){
				num++;
			}
			
		}
	}

	return num;
}

//统计度为1的结点数目  ok
int nodecount(BiTree T){
	if(T==NULL){
		return 0;
	}
	else if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL)){
		return 1+nodecount(T->lchild)+nodecount(T->rchild);
	}
	else return nodecount(T->lchild)+nodecount(T->rchild);
}


//求二叉树的深度  ok
int depth(BiTree T){
	if(T==NULL){
		return 0;
	}
	else{
		int m,n;
		m=depth(T->lchild);
		n=depth(T->rchild);
		if(m>n){
			return 1+m;
		}
		else return 1+n;
	}
}

//求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值  参数应该是BiNode *类型  ok
void echopath(BiNode *T){
	if(T){
		printf("%d ",T->data);
		if(depth(T->lchild)>depth(T->rchild)){
			echopath(T->lchild);
		}
		else echopath(T->rchild);
	}
}

//判断是否是正则二叉树   ok
bool judge(BiTree T){
	if(T==NULL){
		return true;
	}
	else if(T->lchild==NULL&&T->rchild==NULL){
		return true;
	}
	else if(T->lchild!=NULL&&T->rchild!=NULL){
		if(judge(T->lchild)&&judge(T->rchild)){
			return true;
		}
		else return false;
	}
	else return false;
}

int main(){
	
}