二叉树详解

二叉树：他的子节点的个数小于等于2

用结构体表示一个树：

struct treenode{
	int val;//根节点编号
	struct treenode* l;//左子树
	struct treenode* r;//右子树
};

为了方便表示，优化版：

typedef struct treenode{
	int val;//根节点编号
	struct treenode* l;
	struct treenode* r;
}tree,*lptree;//其实就是命名了一下结构体。。。

然后我们来种一个只有根节点的树

lptree creat(int t){
	lptree newtree=(lptree)malloc(sizeof newtree);
	newtree->val =t;
	newtree->l =NULL;
	newtree->r =NULL;
	return newtree;
}

 接下来就是插入 *** 作啦

void in(lptree p,lptree lc,lptree rc){//p是父节点，lc是左子树，rc是右子树
	p->l =lc;
	p->r =rc;
}

 然后我们演示一下代码实现建立下图的树：

#include
#include
#include
#include
using namespace std;

typedef struct tree{
	int val;
	struct tree* l;
	struct tree* r;
}tree,*lptree;
	
lptree creat(int t){
	lptree newtree=(lptree)malloc(sizeof newtree);
	newtree->val =t;
	newtree->l =NULL;
	newtree->r =NULL;
	return newtree;
}
void xianxu(lptree root){
	if(root==NULL)return ;
	printf("%d ",root->val );
	xianxu(root->l );
	xianxu(root->r );
}
void zhongxu(lptree root){
	if(root==NULL)return ;
	zhongxu(root->l );
	printf("%d ",root->val );
	zhongxu(root->r );
}
void houxu(lptree root){
	if(root==NULL)return ;
	houxu(root->l );
	houxu(root->r );
	printf("%d ",root->val );
}
void in(lptree p,lptree lc,lptree rc){
	p->l =lc;
	p->r =rc;
}
int main(){
	lptree t1=creat(1);
	lptree t2=creat(2);
	lptree t3=creat(3);
	lptree t4=creat(4);
	lptree t5=creat(5);
	lptree t6=creat(6);
	lptree t7=creat(7);
	return 0;
}

 最简单的建树，只是为了熟悉一下用法，无实际用途

完全二叉树：

下标从1开始，为了保证他的子节点除以2等于父节点，如果父节点为n，左子节点等于2*n，右子节点等于2*n+1

二叉树的先序，中序，后序遍历：

先序遍历：先头节点再左节点再右节点

中序遍历：左头右

后序遍历：左右头

比如下图中的一个树：

我们按先序遍历的话就是：1 2 4 5 3 6 7

按中序遍历的话就是：4 2 5 1 6 3 7

按后序遍历的话就是：4 5 2 6 7 3 1

代码实现（先用递归）是：

先序：

void xianxu(lptree t){
	if(t==NULL)return ;
	printf("%d",t->val );
	xianxu(t->l );
	xianxu(t->r );
}

中序：

void zhongxu(lptree t){
	if(t==NULL)return ;
	zhongxu(t->l );
	printf("%d",t->val );
	zhongxu(t->r );
}

后序:

void houxu(lptree t){
	if(t==NULL)return ;
	houxu(t->l );
	houxu(t->r );
	printf("%d",t->val );
}

聪明的小朋友很快就能看出来先中后其实是输出头节点的顺序在第一个第二个第三个啦~

 然后我们要看看刚才那个图我们先序中序和后序遍历的顺序是什么，我们可以这么写：

#include
#include
#include
#include
using namespace std;

typedef struct tree{
	int val;
	struct tree* l;
	struct tree* r;
}tree,*lptree;
	
lptree creat(int t){
	lptree newtree=(lptree)malloc(sizeof newtree);
	newtree->val =t;
	newtree->l =NULL;
	newtree->r =NULL;
	return newtree;
}
void xianxu(lptree root){
	if(root==NULL)return ;
	printf("%d ",root->val );
	xianxu(root->l );
	xianxu(root->r );
}
void zhongxu(lptree root){
	if(root==NULL)return ;
	zhongxu(root->l );
	printf("%d ",root->val );
	zhongxu(root->r );
}
void houxu(lptree root){
	if(root==NULL)return ;
	houxu(root->l );
	houxu(root->r );
	printf("%d ",root->val );
}
void in(lptree p,lptree lc,lptree rc){
	p->l =lc;
	p->r =rc;
}
int main(){
	lptree t1=creat(1);
	lptree t2=creat(2);
	lptree t3=creat(3);
	lptree t4=creat(4);
	lptree t5=creat(5);
	lptree t6=creat(6);
	lptree t7=creat(7);
	in(t1,t2,t3);
	in(t2,t4,t5);
	in(t3,t6,t7);
	printf("first:");
	xianxu(t1);
	printf("\nsecond:");
	zhongxu(t1);
	printf("\nthird:");
	houxu(t1);
	return 0;
}

最后出来的结果是：

跟我们刚刚分析的一样哈，没有骗人！

任何递归函数都可以写成非递归，所以我们可以把这三个递归函数写成非递归函数，用压栈的方法。

先序：因为顺序是头左右，所以我们先把头放进去，d出就打印，然后看他的右子树是不是空，如果不空的话就把右孩子加到栈里面，再看左孩子空不空，如果不空再把左孩子放进去。这样我们打印的顺序就是头左右啦~

代码实现：

stack q;//首先定义一个栈
	q.push(t1);//把根节点放进去
	while(q.size() ){//当栈不空的时候
		lptree tt;
		tt=q.top() ;//取队头
		printf("%d ",tt->val  );//打印队头
		q.pop() ;//d出即打印
		if(tt->r !=NULL){//如果右子树不空
			q.push(tt->r ); //压入栈中
		}
		if(tt->l!=NULL){//如果左子树不空
			q.push(tt->l ); //压
		}
	} 

后序是左右头，我们倒过来看就是头右左，跟先序的区别就是左右换了一下，所以我们可以按照先序的做法，但是把左右换了一下，就是构造出头右左，先把头放进去，然后先压左后压右，这样出来的顺序就是头右左，但是我们想要的是他的逆序左右头，所以我们可以再建立一个栈，当他d出原本的栈时候我们就把他存到那个新建的栈里，最后把栈输出就可以啦。

stack q,d;
	q.push(t1);
	while(q.size() ){
		lptree tt=q.top() ;
		d.push(tt);
		q.pop() ;
		if(tt->l !=NULL){
			q.push(tt->l ); 
		} 
		if(tt->r !=NULL){
			q.push(tt->r ); 
		}
	} 
	while(d.size() ){
		lptree t=d.top() ;
		printf("%d ",t->val );
		d.pop() ;
	}

中序遍历的话：我们先建立一个栈，判断如果头节点不空或者栈不空我们就进行循环，如果头节点不空我们就把他放进去，把头节点更新为他的左子树，（一直存他的左子树）如果头结点空了我们就取栈顶元素d出打印之后把头结点更新为栈顶元素的右节点。

stack o;
	lptree head=t1;
	while(o.size() ||head!=NULL){
		if(head!=NULL){
			o.push(head);
			head=head->l ; 
		}else{
			lptree t=o.top() ;
			head=t;
			o.pop() ;
			printf("%d ",t->val  );
			head=head->r ;
		}
	}