JZTXT

二叉树

发布时间 2023-04-04 23:42:11作者: ouhq

 

 

 

 

 

#include<bits/stdc++.h>
using namespace std;
typedef struct TreeNode{
	char data;
 	struct TreeNode *LChild;
	struct TreeNode *RChild; 
}Tree,LPTree;

LPTree *creatNode(char data);
void insertNode(LPTree *parentNode,LPTree *LChild,LPTree *RChild);
void printfCurNode(LPTree *curNode){
	cout<<curNode->data<<"  ";
}

//递归法
void preOrder(LPTree *root); 
void midOrder(LPTree *root);
void lastOrder(LPTree *root); 
//非递归
void preOrderByStack(LPTree *root);
void midOrderByStack(LPTree *root);
void lastOrderByStack(LPTree *root);
 
int main()
{	//死板的创建过程，无实际作用 
 	LPTree *A=creatNode('A');
 	LPTree *B=creatNode('B');
 	LPTree *C=creatNode('C');
 	LPTree *D=creatNode('D');
 	LPTree *E=creatNode('E');
 	LPTree *F=creatNode('F');
 	LPTree *G=creatNode('G');
 	insertNode(A,B,C);
 	insertNode(B,D,NULL);
 	insertNode(D,NULL,G);
 	insertNode(C,E,F);
 	cout<<"前序遍历："<<endl;
 	preOrder(A);
 	cout<<endl;
 	cout<<"前序遍历(非递归)："<<endl;
 	preOrderByStack(A);
 	cout<<endl;
 	cout<<"中序遍历："<<endl;
 	midOrder(A);
 	cout<<endl;
 	cout<<"中序遍历(非递归)："<<endl;
 	midOrderByStack(A);
 	cout<<endl;
 	cout<<"后序遍历："<<endl;
 	lastOrder(A);
 	cout<<endl;
 	cout<<"后序遍历(非递归)："<<endl;
 	lastOrderByStack(A);
 	cout<<endl;
}

LPTree *creatNode(char data)
{
	LPTree *newNode=(LPTree*)calloc(1,sizeof(LPTree));
	if(newNode==NULL){
		cout<<"creat newNode fail";
		return NULL;
	}
	newNode->data=data;
	return newNode;
}

void insertNode(LPTree *parentNode,LPTree *LChild,LPTree *RChild)
{
	parentNode->LChild=LChild;
	parentNode->RChild=RChild;
}

//先序：根 左 右
void preOrder(LPTree *root) //递归 
{
	if(root!=NULL){
		printfCurNode(root);
		preOrder(root->LChild);
		preOrder(root->RChild);
	}
} 

void preOrderByStack(LPTree *root) //非递归 
{
	if(root==NULL) return;
	LPTree *stack[10];   //数组模拟  栈
	int stacktop=-1;  
	LPTree *pmove=root;
	while(stacktop!=-1||pmove!=NULL){
		// 根 左 右 
		while(pmove!=NULL){  //走到左边的尽头 
			//打印走过的路径，并且入栈
			cout<<pmove->data<<"  ";
			stack[++stacktop]=pmove;  //记录路径的地址
			pmove=pmove->LChild;  
		}
		if(stacktop!=-1){
			pmove=stack[stacktop];  //出栈前获取栈顶元素，即上一个路径，之后开始往右走 
			stacktop--;//伪  出栈
			pmove=pmove->RChild; 
		}
	} 
}
 
//中序：左 根 右 
void midOrder(LPTree *root)  //递归
{ 
	if(root!=NULL){
		midOrder(root->LChild);
		printfCurNode(root);
		midOrder(root->RChild);
	}
}

void midOrderByStack(LPTree *root)  //非递归
{ 
	if(root==NULL) return;
	LPTree *stack[10];
	int stacktop=-1;
	LPTree *pmove=root;
	while(stacktop!=-1||pmove!=NULL){
		while(pmove!=NULL){
			//走到左边的尽头，把路径入栈 
			stack[++stacktop]=pmove;
			pmove=pmove->LChild;
		}
		//伪  出栈
		if(stacktop!=-1){
			pmove=stack[stacktop--];
			cout<<pmove->data<<"  ";
			pmove=pmove->RChild;	
		} 
	}
}

//后序：左 右 根
void lastOrder(LPTree *root)  //递归
{ 
	if(root!=NULL){
		lastOrder(root->LChild);
		lastOrder(root->RChild);
		printfCurNode(root);
	}
} 

void lastOrderByStack(LPTree *root)
{
	if(root==NULL) return;
	LPTree *stack[10];
	int stacktop=-1;
	LPTree *pmove=root;
	LPTree *pLastVist=NULL;
	while(pmove!=NULL){
		//走到左边的尽头，把路径入栈 
		stack[++stacktop]=pmove;
		pmove=pmove->LChild;
	}
	while(stacktop!=-1){
		pmove=stack[stacktop--];  //回退到上一个
		 if(pmove->RChild==NULL||pmove->RChild==pLastVist){ //当前节点左右是否被访问过     //右边为空，或者被标记  //不用看左节点，因为上一个循环已经判断左节点为NULL了
		 	cout<<pmove->data<<"  "; //如果访问过就可以打印当前节点 
		 	pLastVist=pmove;  //改变标记的位置 
		 }
		 else {
		 	//右边没有被访问过   就访问右边 
		 	stack[++stacktop]=pmove;
		 	pmove=pmove->RChild;
		 	while(pmove!=NULL){
		 		stack[++stacktop]=pmove;
		 		pmove=pmove->LChild;
			 }
		 }
	}
}