【二叉树基本操作总结1】

目录

构造函数

前、中、后序遍历

层序遍历

析构函数

求深度

求结点数

转化为一维数组

//二叉树链表存储
#include
#include
#include
const int N=1e5+10;
using namespace std;
struct BiNode{
	char data;
	BiNode *lchild,*rchild;
};
struct buildArray{
	BiNode* node;
	int index;
};
class BiTree{
	private:
		BiNode* root;
	public:
		BiTree(){root=create(root);}
		~BiTree(){release(root);}
		BiNode* getRoot(){return root;}
		BiNode* create(BiNode *bt);
		void preOrder(BiNode* bt);
		void inOrder(BiNode* bt);
		void postOrder(BiNode* bt);
		void levelOrder(BiNode* bt);
		void release(BiNode* bt);
		int getDepth(BiNode* bt);
		int getNum(BiNode* bt);
		int getArray(BiNode* bt,char *array,int i); 
		
}; 
BiNode* BiTree::create(BiNode *bt){
	char ch;
	cin>>ch;
	if(ch=='#') bt=NULL; 
	else{
		bt=new BiNode;
		bt->data=ch;
		bt->lchild=create(bt->lchild);
		bt->rchild=create(bt->rchild);
	}
	return bt;
}

void BiTree::preOrder(BiNode* bt){
	if(bt==NULL) return;
	else{
		cout<data<<" ";
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
	return;
}

void BiTree::inOrder(BiNode* bt){
	if(bt==NULL) return;
	else{
		inOrder(bt->lchild);
		cout<data<<" ";
		inOrder(bt->rchild);
	}
	return;
	
}

void BiTree::postOrder(BiNode* bt){
	if(bt==NULL) return;
	else{
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		cout<data<<" "; 
	}
	return;
}

void BiTree::levelOrder(BiNode* bt){
	if(bt==NULL) return;
	queue Q;
	Q.push(bt);
	BiNode* p;
	while(!Q.empty()){
		p=Q.front();
		Q.pop();
		cout<data<<" ";
		if(p->lchild!=NULL) Q.push(p->lchild);
		if(p->rchild!=NULL) Q.push(p->rchild);
	}
	return;
}
//后序遍历删除结点 
void BiTree::release(BiNode* bt){
	BiNode* p=bt;
	if(p->lchild==NULL&&p->rchild==NULL){
		cout<<"delete "<data<lchild!=NULL) release(bt->lchild);
		if(p->rchild!=NULL) release(bt->rchild);
		cout<<"delete "<data<lchild==NULL&&bt->rchild==NULL) return 1;
//	else{
//		int left=0,right=0;
//		if(bt->lchild!=NULL) left=getDepth(bt->lchild);
//		if(bt->rchild!=NULL) right=getDepth(bt->rchild);
//		return max(left,right)+1;
//	}
	if(bt==NULL) return 0;
	int left=getDepth(bt->lchild);
	int right=getDepth(bt->rchild);
	return max(left,right)+1;
} 

int BiTree::getNum(BiNode* bt){
	if(bt==NULL) return 0;
	int left=getNum(bt->lchild);
	int right=getNum(bt->rchild);
	return left+right+1;
}

//使用递归进行一维数组的创建
int BiTree::getArray(BiNode* bt,char *array,int i){
	BiNode* p=bt;
	if(p==NULL) return i/2;
	array[i]=p->data;
	int left=getArray(p->lchild,array,i*2);
	int right=getArray(p->rchild,array,i*2+1);
	return max(left,right);
}

//利用层序遍历进行一维数组的创建
void BiTree::getArray2(char *array,BiNode* bt){
	buildArray bA;
	bA.node=bt;
	bA.index=1;
	int i;
	queue Q;
	Q.push(bA);
	while(true){
		buildArray p=Q.front();
		Q.pop();
		array[p.index]=p.node->data;
		buildArray t;
		if(p.node->lchild!=NULL){
			t.index=p.index*2;
			t.node=p.node->lchild;
			Q.push(t);
		}
		if(p.node->rchild!=NULL){
			t.index=p.index*2+1;
			t.node=p.node->rchild;
			Q.push(t);
		}
		if(Q.empty()){
			i=p.index;
			break;
		}
	}
	array[i+1]='';	
} 



int main(){
	BiTree BT;
	BiNode* r=BT.getRoot();
	cout<<"前序遍历"< 
以该二叉树为例，试试效果
 
 
 
 打印效果图如下
 
 
 
下面我们把各个函数单拎出来浅讲一下
 
构造函数 
BiTree(){root=create(root);}
 
BiNode* create(BiNode *bt);
 
这里在构造函数里面调用creat,因为需要使用递归调用函数且new 一个空间。这里切记root=create(root) 
 
是我容易错的
 
前、中、后序遍历 
以    preOrder(BiNode* bt)为例
 
遍历也是递归的写法，没啥好讲的。
 
 
层序遍历 
levelOrder(BiNode* bt)
 
层序遍历是这里使用了一个容器，STL里面的队列。
 
说明一下使用到的函数吧：
 
 
 
 
 
 
 因为之前自己写代码实现队列的时候，pop()是有返回值的。这里只可以通过front()访问，写的时候d了一下bug.
 
这里的思路就是，将根节点入队，在每次出队的时候就检查它是否有左右子树。如果有就入队（利用队列先进先出的特性）
 
 
析构函数 
~BiNode(release(root));
 
release(BiNode* bt)
 
这里需要逐步回收刚才new的空间，众周知，二叉树是通过根节点来访问子节点的，如果你把根节点delete了，左右子树就没有办法回收了，所以我们这里采用后序访问的方法来delete.
 
如果已经是叶节点了（没有左右子树）就直接de
 
如果是分支结点，就需要先de左右子树，然后再de自己。
 
 
求深度 
getDepth(BiNode* bt);
 
深度，众周知，就是一颗二叉树最大的深度。那么我们，先求出左边的深度和右边的深度，取最大的，再加上自己这一层的1，返回。然后递归调用。
 
 
求结点数 
getNum(BiNode* bt);
 
结点数与深度可谓是异曲同工之妙。
 
我们就把“先求出左边的深度和右边的深度，取最大的，再加上自己这一层的1”换成“求左边个数和右边个数，相加，再加上自己的1”，递归调用即可。
 
 
转化为一维数组 
 
getArray1(BiNode* bt,char *array,int i);
 
这里与前序类似，但多了一个将遍历的结果储存（且按二叉树的性质储存）这一步。
 
性质：
 
一点坐标是i    (下标从1开始)
 
则左子树 (的根节点)==i*2
 
右子树（的根节点）==i*2+1
 
采取的策略是，只存储含有实际值的数据.
 
在遍历数组的时候，如果没有数据，我们就手动打印‘^’
 
 
我在写的是后遇到的问题：
 
不知道数组开多大------>策略：往大了开1e5+10
 
怎么判断结尾------>好问题，仔细看看下面代码
 
if(p==NULL) return i/2;


max(left,right);
 
一个是访问到叶节点后的回溯
 
一个数取得数组得最大下标
 
 
void getArray2(char *array,BiNode* bt);
 
这里是用层序遍历的方法创建数组
 
总体思路将层序遍历的打印操作改为存入数组的操作。
 
基于此，
 
1.我们需要一个存储数组下标的index,以及index的变化关系（左：2*i,右：2*i+1）。
 
2.将下标与结点封装起来，就需要一个结构体buildArray。
 
注意：
 
就如同上面递归写法需要获取 最大下标一样，我们这里很容易直接获取最大下标，那就是在马上要跳出while()时，拿一个变量接一下。为了更加简单，我们就直接在最大下标的下一个位置存一个终止符。就可以直接在主函数cout输出了。唯一有点不对头的地方就是，需要将字符数组初始化为^，如果开的空间很大，而数据很小，就会有一点浪费时间。比如我这里就是N=1e5+10
 
 
over!