二叉树学习

#include<stdio.h>
#include<stdlib.h>


//二叉树结构 
typedef struct BiTNode{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//链表 
typedef struct LinkNode{
	BiTree data;//数据域 
	struct LinkNode* next;//指针域 
}LinkNode,*LinkStack;

//初始化栈 
void InitStack(LinkStack &S){
	S=(LinkStack)malloc(sizeof(LinkNode));
	S->next=NULL;
}
//判栈空
bool EmptyStack(LinkStack &S){
	if(S->next==NULL){
		return true;
	}
	return false;
}
//获取栈顶元素 
bool GetTop(LinkStack &S,BiTree &x){
	if(EmptyStack(S)){
		return false;
	}
	x=S->next->data;
	return true;
}
//入栈 
bool Push(LinkStack &S,BiTree &x){
	LinkStack newNode=(LinkStack)malloc(sizeof(LinkNode));
	newNode->data=x;
	newNode->next=S->next;
	S->next=newNode;
	return true;
}
//出栈
bool Pop(LinkStack &S,BiTree &x){
	if(EmptyStack(S)){
		return false;
	}
	LinkStack node=S->next;
	x=node->data;
	S->next=node->next;
	free(node);
	return true;
}

//访问结点函数
void visit(BiTree T){
	printf("%d->",T->data);//打印结点数据 
}
//非递归中序遍历 
void InOrder2(BiTree T){
	LinkStack S;
	InitStack(S);
	BiTree p=T;
	while(p||!EmptyStack(S)){//p不为null或栈不为空时循环
		if(p){
			Push(S,p);//存储当前结点
			p=p->lchild;//访问当前左子结点
		}else{
            //如果当前结点为空则回溯父结点
			Pop(S,p);
			visit(p);//访问父结点
			p=p->rchild;//获取父结点的右子结点
		}
	}
	printf("\n");
} 
//非递归先序遍历
 void PreOrder2(BiTree T){
 	LinkStack S;
	InitStack(S);
	BiTree p=T;
	while(p||!EmptyStack(S)){//p不为null或栈不为空时循环
		if(p){
			visit(p);//访问当前结点 
			Push(S,p);//将当前结点入栈 
			p=p->lchild;//继续向左获取结点 
		}else{
			Pop(S,p);//回溯上一个结点 
			p=p->rchild;//访问结点的右结点 
		}
	}
	printf("\n");
 } 
 //非递归后序遍历二叉树算法
void PostOrder(BiTree T){
	LinkStack S;
	InitStack(S);//初始化一个链表栈（分配空间）
	BiTree p=T;
	BiTree r=NULL;//记录最近访问过的结点
	while(p||!EmptyStack(S)){
		if(p){
			Push(S,p);
			p=p->lchild;
		}else{
			GetTop(S,p);
			if(p->rchild&&p->rchild!=r){
				p=p->rchild;
			}else{
				Pop(S,p);
				visit(p);
				r=p;
				p=NULL;
			}
		}
	} 
	printf("\n");
} 
int main(){
	BiTree t1=(BiTree)malloc(sizeof(BiTNode));
	BiTree t2=(BiTree)malloc(sizeof(BiTNode));
	BiTree t3=(BiTree)malloc(sizeof(BiTNode));
	BiTree t4=(BiTree)malloc(sizeof(BiTNode));
	BiTree t5=(BiTree)malloc(sizeof(BiTNode));
	
	t1->data=1;t1->lchild=t2;t1->rchild=t3;
	t2->data=2;t2->lchild=t4;t2->rchild=t5;
	t3->data=3;t3->lchild=NULL;t3->rchild=NULL;
	t4->data=4;t4->lchild=NULL;t4->rchild=NULL;
	t5->data=5;t5->lchild=NULL;t5->rchild=NULL;
	
	InOrder2(t1);//测试中序 
	PreOrder2(t1);//测试先序 
	PostOrder(t1);//测试后序 
} 

三、二叉树层序遍历（借助队列）

#include<stdio.h>
#include<stdlib.h>


//二叉树结构 
typedef struct BiTNode{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//链表 
typedef struct LinkNode{
	BiTree val;//数据域
	struct LinkNode *next;//指针域 
}LinkNode,*LinkedList;
//链式存储队列 
typedef struct LinkedQueue{
	LinkedList front,rear;
}LinkedQueue;

//初始化队列 
void Init_LinkedQueue(LinkedQueue &q){
	q.front=q.rear=(LinkedList)malloc(sizeof(LinkNode));//建立队头和队尾
	q.front->next=NULL; 
}
//判队空
bool is_Empty(LinkedQueue &q){
	if(q.front==q.rear){
		return true; 
	} 
	return false;
} 
//入队
void EnQueue(LinkedQueue &q,BiTree x){
	LinkedList newNode=(LinkedList)malloc(sizeof(LinkNode));//新结点
	newNode->val=x;
	newNode->next=NULL;
	//插入新结点 
	q.rear->next=newNode;
	q.rear=newNode;
	return;
} 
//出队
bool DeQueue(LinkedQueue &q,BiTree &x){
	if(is_Empty(q)){
		return false;
	}
	//获取被删结点 
	LinkedList p=q.front->next;
	x=p->val;
	//删除结点 
	q.front->next=p->next;
	if(q.rear==p){
		q.rear=q.front; 
	}
	free(p);
	return true;
}
//访问结点函数
void visit(BiTree T){
	printf("%d->",T->data);//打印结点数据 
}

//层序遍历
void LevelOrder(BiTree T){
	LinkedQueue q;//队列 
	Init_LinkedQueue(q);//初始化队列
	EnQueue(q,T);//头结点入队
	BiTree b;
	while(!is_Empty(q)){//如果队列中有结点则遍历 
		DeQueue(q,b);//获取出队结点
		visit(b);//访问结点
		if(b->lchild!=NULL)
			EnQueue(q,b->lchild);//左子结点存在则先访问 
		if(b->rchild!=NULL)
			EnQueue(q,b->rchild);//右子结点存在则后访问 
	}
	printf("\n");
} 
//层序遍历求二叉树的深度（非递归算法） 
int BtTree(BiTree T){
	if(T==NULL){
		return 0;
	}
	int level=0;
	BiTree last=T;//指向遍历下一层的最后一个元素
	 
	LinkedQueue q;//队列 
	Init_LinkedQueue(q);//初始化队列
	EnQueue(q,T);//头结点入队
	BiTree b;
	while(!is_Empty(q)){//如果队列中有结点则遍历 
		DeQueue(q,b);//获取出队结点
		if(b->lchild!=NULL)
			EnQueue(q,b->lchild);//左子结点存在则先访问 
		if(b->rchild!=NULL)
			EnQueue(q,b->rchild);//右子结点存在则后访问 
		if(last==b){//遍历到当前层最后一个元素
			++level;//层数++ 
			last=q.rear->val;//指向下一层最后一个元素			
		}
	}
	return level;
} 
int main(){
	BiTree t1=(BiTree)malloc(sizeof(BiTNode));
	BiTree t2=(BiTree)malloc(sizeof(BiTNode));
	BiTree t3=(BiTree)malloc(sizeof(BiTNode));
	BiTree t4=(BiTree)malloc(sizeof(BiTNode));
	BiTree t5=(BiTree)malloc(sizeof(BiTNode));
	
	t1->data=1;t1->lchild=t2;t1->rchild=t3;
	t2->data=2;t2->lchild=t4;t2->rchild=t5;
	t3->data=3;t3->lchild=NULL;t3->rchild=NULL;
	t4->data=4;t4->lchild=NULL;t4->rchild=NULL;
	t5->data=5;t5->lchild=NULL;t5->rchild=NULL;
	
	LevelOrder(t1);//测试层序 
	printf("二叉树的层数=%d\n",BtTree(t1));//测试统计层数 
}