二叉树的相干操作代码(继续补全中)

二叉树的相关操作代码(继续补全中)
#ifndef BITREEOPERATION_H
#define BITREEOPERATION_H
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
typedef char ElemType;

typedef struct BiNode{
	ElemType data;
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

//先序建立二叉树
int PreOrderCreateBiTree(BiTree& Root){
	char ch;
	scanf("%c",&ch);
	if(ch==' ')
		Root=NULL;
	else{
		Root=(BiTree)malloc(sizeof(BiNode));
		Root->data=ch;//生成根节点
		PreOrderCreateBiTree(Root->lchild);//构造左子树
		PreOrderCreateBiTree(Root->rchild);//构造右子树
	}
	return 0;
}

//先序的递归遍历
void PreOrderTraverse(BiTree Root){
	if(Root!=NULL){
		printf("%c",Root->data);//访问根节点
		PreOrderTraverse(Root->lchild);//先序遍历左子树
		PreOrderTraverse(Root->rchild);//先序遍历右子树
	}
}

//中序的递归遍历
void InOrderTraverse(BiTree Root){
	if(Root!=NULL){
		PreOrderTraverse(Root->lchild);//中序遍历左子树
		printf("%c",Root->data);//访问根节点
		PreOrderTraverse(Root->rchild);//中序遍历右子树
	}
}

//后序的递归遍历
void PostOrderTraverse(BiTree Root){
	if(Root!=NULL){
		PreOrderTraverse(Root->lchild);//后序遍历左子树
		PreOrderTraverse(Root->rchild);//后序遍历右子树
		printf("%c",Root->data);//访问根节点
	}
}

//先序的非递归遍历，使用到栈结构
void PreOrderNonRecur(BiTree Root){
	std::stack<BiTree> cstack;
	BiTree p=Root;
	while(p||!cstack.empty()){
		if(p){//根指针进栈，访问根节点，遍历左子树
			cstack.push(p);
			printf("%c",p->data);
			p=p->lchild; 
		}else{//根指针退栈，遍历右子树
			p=cstack.top();
			cstack.pop();
			p=p->rchild;
		}
	}

}

//中序的非递归遍历
void InOrderNonRecur(BiTree Root){
	if(Root!=NULL){
		std::stack<BiTree> cstack;
		BiTree p=Root;
		while(p||!cstack.empty()){
			if(p){//根指针进栈，遍历左子树
				cstack.push(p);			
				p=p->lchild;
			}else{//根指针退栈，访问根节点，遍历右子树
				p=cstack.top();
				cstack.pop();
				printf("%c",p->data);			
				p=p->rchild;
			}
		}
	}

}
//后序的非递归遍历比较麻烦些，暂时不讨论

//层序遍历,使用到队列结构
void levelOrderTraverse(BiTree Root){
	if(Root!=NULL){
		std::queue<BiTree> cqueue;
		BiTree p=Root;
		cqueue.push(p);
		while(!cqueue.empty()){
			p=cqueue.front();
			cqueue.pop();//根节点出队列
			printf("%c",p->data);
			if(p->lchild!=NULL)
				cqueue.push(p->lchild);
			if(p->rchild!=NULL)
				cqueue.push(p->rchild);
		}
	}
}

//递归求树的高度
int getBiTreeHeight(BiTree Root){
	if(Root==NULL)
		return 0; //空树返回0
	else{
		int lheight=getBiTreeHeight(Root->lchild);//递归求左子树高度
		int rheight=getBiTreeHeight(Root->rchild);//递归求右子树高度
		return lheight>rheight? lheight+1:rheight+1;//树的高度为左右子树的最大者
	}
}

//求特定节点的父节点
BiTree PreOrderTraverse(BiTree Root,char target,BiTree parent){
	if(Root!=NULL){
		if(Root->data==target)
			return parent;
		BiTree lparent=PreOrderTraverse(Root->lchild,target,Root);//先序遍历左子树
		if(lparent)
			return lparent;
		BiTree rparent=PreOrderTraverse(Root->rchild,target,Root);//先序遍历右子树
		if(rparent)
			return rparent;
	}
	return NULL;//若返回Null，则代表该子树不存在目标字符
}
#endif
二叉树的相干操作代码(继续补全中)

相关推荐
