二叉树的基本操作

二叉树的结构体定义

typedef struct BNode{
	int data;
	struct BNode *lchild,*rchild;
}BNode,BiTree;

二叉树的操作代码

//建立二叉树
BiTree createBiTree(){
	int data;
	scanf("%d",&data);
	if(data!=-1){
		t = (BNode*)malloc(sizeof(BNode));
		t->data = data;
		t->lchild = createBiTree();
		t->rchild = createBiTree();
		return t;
	}else{
		return NULL;
	}
} 

////三大递归遍历
//打印函数
void visit(BiTree T){
    printf("%d",T->data);
} 
//前序遍历
void NLRPrint(BiTree t){
	if(t){
	visit(t);
	NLRPrint(t->lchild);
	NLRPrint(t->rchild);
   }
}
//中序遍历
void LNRPrint(BiTree t){
	if(t){
	LNRPrint(t->lchild);
	visit(t);
	LNRPrint(t->rchild);
   }
}
//后续遍历
void LRNPrint(BiTree t){
	if(t){
	visit(t);
	LRNPrint(t->lchild);
	LRNPrint(t->rchild);
   }
}

////三大非递归遍历
//前序遍历
void NLRPrintN(BiTree t){
	BiTree stack[MAXSIZE],p = t;
	int top=-1;
	//stack[++top] = t;
	while(p || top!=-1){
		if(p){
			visit(p);
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top--];
			p = p->rchild;
		}
	}
} 

//中序遍历
void LNRPrintN(BiTree t){
	BiTree stack[MAXSIZE],p = t;
	int top=-1;
	while(p || top!=-1){
		if(p){
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top--];
			visit(p);
			p = p->rchild;
		}
	}
}

//后序遍历
void LRNPrintN(BiTree t){
	BiTree stack[MAXSIZE],p = t;
	int top = -1,tag[MAXSIZE] = {0};
	while(p || top!=-1){
		if(t){
			stack[++top] = p;
			p = p->lchild;
			tag[top] = 1;
		}else{
			if(tag[top]==1){
				tag[top] == 2;
				p = stack[top];
				p = p->rchild;
			}else{
				visit(p);
				top--;
				p = NULL;
			}
		}
	}
}

//层序遍历
void levelPrint(BiTree t){
	BiTree Queue[MAXSIZE],p=t;
	int rear = front = -1;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		visit(p);
		if(p->lchild){
			Queue[++rear] = p->lchild;
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
	}
}