Demo entry 6343520

111

   

Submitted by 11 on Jan 10, 2017 at 08:26
Language: C++. Code size: 5.6 kB.

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int STACK_INIT_SIZE=1000;
typedef struct BiNode{
	int data;
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
/*****************以下为队列***********************/
typedef struct QNode{
	BiTree data;
	struct QNode* next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &q){
	q.front=q.rear=(QueuePtr)malloc(sizeof(QNode));
	q.front->next=NULL;
}
bool QueueEmpty(LinkQueue &q){
	if(q.front->next==NULL)	return true;
	else	return false;
}
BiTree GetHead(LinkQueue &q){
	return q.front->next->data;
}
void EnQueue(LinkQueue &q,BiTree e){
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	p->data=e;	p->next=NULL;
	q.rear->next=p;
	q.rear=p;
}
void DeQueue(LinkQueue &q){
	QueuePtr p=q.front->next;
	q.front->next=p->next;
	if(q.rear==p)	q.rear=q.front;
	free(p);
}
void DestroyQueue(LinkQueue &q){
	while(q.front){
		q.rear=q.front->next;
		free(q.front);
		q.front=q.rear;
	}
}
/*******************以下为栈****************************/
typedef struct{
    BiTree *top;
	BiTree *base;
	int stacksize;
}SqStack;
void InitStack(SqStack &S){
	S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));     
    S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
}
bool StackEmpty(SqStack S){
    if(S.top==S.base)
    	return true;
    else
    	return false;
}
void Push(SqStack &S,BiTree T){
	*S.top++=T;
}
void Pop(SqStack &S){
	S.top--;
}
BiNode* Top(SqStack S){
	BiNode *p;
	return p=*(S.top-1);
}
/*******************以下为树*******************************/
void create(BiTree &T){
	int tmp;
	scanf("%d",&tmp);
	if(tmp==-1)	T=NULL;
	else{
		T=(BiNode*)malloc(sizeof(BiNode));
		T->data=tmp;
		create(T->lchild);
		create(T->rchild);
	}
	return;
}
void pre_order(BiTree T){
	if(T!=NULL){
		printf("%d ",T->data);
		pre_order(T->lchild);
		pre_order(T->rchild);
	}
	return;
}
void in_order(BiTree T){
	if(T!=NULL){
		in_order(T->lchild);
		printf("%d ",T->data);
		in_order(T->rchild);
	}
	return;
}
void post_order(BiTree T){
	if(T!=NULL){
		post_order(T->lchild);
		post_order(T->rchild);
		printf("%d ",T->data);
	}
	return;
}
void pre_order_fdg(BiTree T){
    SqStack S;
    BiTree p=T;
	InitStack(S);
	while(p!=NULL || !StackEmpty(S)){
		while(p!=NULL){
			printf("%d ",p->data);
			Push(S,p);
			p=p->lchild;
		}
		if(!StackEmpty(S)){
			p=Top(S);
			Pop(S);
			p=p->rchild;
		}
	}
}
void in_order_fdg(BiTree T){
	SqStack S;
    BiTree p=T;
	InitStack(S);
	while(p!=NULL || !StackEmpty(S)){
		if(p){
			Push(S,p);
			p=p->lchild;
		}
		else{
			p=Top(S);	Pop(S);
			printf("%d ",p->data);
			p=p->rchild;
		}
	}
}
void post_order_fdg(BiTree T){
	SqStack S;
    BiTree cur,pre;
	InitStack(S);
	Push(S,T);
	while(!StackEmpty(S)){
		cur=Top(S);
		if((cur->lchild==NULL && cur->rchild==NULL) || (pre!=NULL && (pre==cur->lchild || pre==cur->rchild))){
			printf("%d ",cur->data);
			Pop(S);
			pre=cur;
		}
		else{
			if(cur->rchild!=NULL)
				Push(S,cur->rchild);
			if(cur->lchild!=NULL)
				Push(S,cur->lchild);
		} 
	}
}
int depth(BiTree T){
	if(T==NULL)	return 0;
	int ldeep=depth(T->lchild),rdeep=depth(T->rchild);
	return ldeep>rdeep?ldeep+1:rdeep+1;
}
void level_order_fdg(BiTree T){
	LinkQueue q;
	InitQueue(q);
	if(T!=NULL)
		EnQueue(q,T);
	while(!QueueEmpty(q)){
		BiTree tmp=GetHead(q);	DeQueue(q);
		printf("%d ",tmp->data);
		if(tmp->lchild)
			EnQueue(q,tmp->lchild);
		if(tmp->rchild)
			EnQueue(q,tmp->rchild);
	}
	DestroyQueue(q);
	return;
}
void printnode(BiTree T,int level){
	if(T==NULL || level<1)	return;
	if(level==1){
		printf("%d ",T->data);
		return;
	}
	printnode(T->lchild,level-1);
	printnode(T->rchild,level-1);
}
void level_order(BiTree T){
	if(T==NULL)	return;
	int dep=depth(T);
	for(int i=1;i<=dep;i++){
		printnode(T,i);
	}
}
int leafnode(BiTree T){
	if(T==NULL)
		return 0;
	else if(T->lchild==NULL && T->rchild==NULL)
		return 1;
	else
		return leafnode(T->lchild)+leafnode(T->rchild);
}
void change(BiTree &T){
	if(T!=NULL){
		BiNode *p=T->lchild,*q=T->rchild;
		T->lchild=q;
		T->rchild=p;
		change(T->lchild);
		change(T->rchild);
	}
}
bool is_completetree(BiTree T){
	LinkQueue q;
	InitQueue(q);
	if(T!=NULL)
		EnQueue(q,T);
	int flag=0;
	while(!QueueEmpty(q)){
		BiTree tmp=GetHead(q);	DeQueue(q);
		if(tmp->lchild)
			EnQueue(q,tmp->lchild);
		if(tmp->rchild)
			EnQueue(q,tmp->rchild);
		if(tmp->rchild && !tmp->lchild)	return false;
		if(tmp->lchild && !tmp->rchild){
			if(flag==0)
				flag=1;
			else
				return false;
		}
	}
	DestroyQueue(q);
	return true;
}
int main(){
	BiTree T;
	freopen("Btree.txt","r",stdin);
	create(T);
	if(is_completetree(T))
		printf("是完全二叉树。\n");
	else
		printf("不是完全二叉树。\n");
	printf("树的高度:%d\n",depth(T));
	printf("叶子节点个数:%d\n",leafnode(T));
	printf("递归先序遍历:");	pre_order(T);	puts("");
	printf("非递归先序遍历:");	pre_order_fdg(T);	puts("");
	
	printf("递归中序遍历:");	in_order(T);	puts("");
	printf("递归后序遍历:");	post_order(T);	puts("");
	printf("递归层次遍历:");	level_order(T);	puts("");

	printf("非递归层次遍历:");	level_order_fdg(T);	puts("");
	change(T);
	printf("交换左右子树之后:\n");
	printf("非递归先序遍历:");	pre_order_fdg(T);	puts("");
	printf("非递归中序遍历:");	in_order_fdg(T);	puts("");
	printf("非递归后序遍历:");	post_order_fdg(T);	puts("");
	level_order(T);
	return 0;
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).