二叉树遍历（递归和非递归、线索化、释放） – 小飞侠

二叉树遍历（递归和非递归、线索化、释放）

Post author:xfxia
Post published:2023年7月23日
Post category:其他

二叉树遍历

自用模板

二叉链表

typedef struct node{
	char data;
	node *lchild,*rchild;
}*Tree;

二叉树创建

void build(Tree &T)
{
	char data;
	scanf("%c",&data);
	if(data!='#')
	{
		T=(Tree)malloc(sizeof(node));//分配空间 
		T->data=data;
		build(T->lchild);
		build(T->rchild);
	}
	else{
		T=NULL;
	}
}

递归版本

void preorder(Tree T)
{
	if(T != NULL)
	{
			printf("%c ",T->data);
		preorder(T->lchild);
		preorder(T->rchild);
	 } 
}

void inorder(Tree T)
{
	if(T!=NULL)
	{
		inorder(T->lchild);
			printf("%c ",T->data);
		inorder(T->rchild);	
	}
}

void postorder(Tree T)
{
	if(T != NULL)
	{
		postorder(T->lchild);
		postorder(T->rchild);
			printf("%c ",T->data);
	}
}

非递归版本

void preorder(Tree T)
{
	if(T != NULL)
	{
			printf("%c ",T->data);
		preorder(T->lchild);
		preorder(T->rchild);
	 } 
}

void inorder(Tree T)
{
	if(T!=NULL)
	{
		inorder(T->lchild);
			printf("%c ",T->data);
		inorder(T->rchild);	
	}
}

void postorder(Tree T)
{
	if(T != NULL)
	{
		postorder(T->lchild);
		postorder(T->rchild);
			printf("%c ",T->data);
	}
}

void preorder2(Tree T)
{
	stack<Tree>s;
	Tree p=T;
	while(p || !s.empty())
	{
		if(p)
		{
			printf("%c ",p->data);
			s.push(p);
			p=p->lchild;
		}
		else
		{
			p=s.top();
			s.pop();
			p=p->rchild;
		}
	}
 } 

void inorder2(Tree T)
{
	stack<Tree>s;
	Tree p = T;
	while(p || !s.empty())
	{
		if(p != NULL)
		{
			s.push(p);
			p=p->lchild;
		}
		else
		{
			p=s.top();
			s.pop();
			printf("%c ",p->data);
			p=p->rchild;
		}
	}
	
}
void postorder2(Tree T) 
{
	stack<Tree>s;
	int top=0;
	Tree p=T, Last;
	while(p||!s.empty())
	{
		while(p)  
	{
		s.push(p);
		 p=p->lchild;
	}
	if(!s.empty())  
	{
		p=s.top();
		s.pop();
		if(p->rchild==NULL || p->rchild==Last)
		{
		printf("%c ",p->data); 
		Last=p; p=NULL;  
		 }
		else  
			{
			s.push(p);  
			p=p->rchild;  
		   } 
	} 
	}
}

层次遍历

void levelorder(Tree T)
{
		queue<Tree>q;
		Tree p = T;
		if(p)
		{
			q.push(p);
			while(!q.empty())
			{
			    p=q.front();
			    q.pop();
				printf("%c ",p->data);
				if(p->lchild)
				q.push(p->lchild);
				if(p->rchild)
				q.push(p->rchild);
			}
		}
}

线索化以及遍历

void threading(Tree  T)
{
	if(T)
	{
	threading(T->lchild);
	if(!T->lchild)
	{
		T->ltag=1;
		T->lchild=pre;
	}
	if(!pre->rchild)
	{
		pre->rtag = 1;
		pre->rchild = T;
	}
	pre = T;
	threading(T->rchild);
	}
}

void inorderthread(Tree & Th, Tree T)
{
	Th=(Tree)malloc(sizeof (node));
	if(!Th)
	{
		printf("分配失败！");
		return ; 
	}
	Th->ltag=0,Th->rtag=1;
	Th->rchild=Th;
	if(T)
	{
		Th->lchild = T;
		pre = Th;
		threading(T);
		pre->rchild=Th,pre->rtag=1;
		Th->rchild=pre;
	}
	else
	Th->lchild=Th;
	
} 

void threadvisit(Tree Th)
{

	Tree T;
	T=Th->lchild;
	
	while(T != Th)
	{
		while(T->ltag == 0) T=T->lchild;
		printf("%c ",T->data);
		while(T->rtag == 1 && T->rchild != Th)
		{
			T=T->rchild;
			printf("%c ",T->data);
		}
		
		T=T->rchild;
	}
}

释放空间

void FreeTree(Tree Th)
{
	Tree T;
	T=Th->lchild;
	
	while(T != Th)
	{
		while(T->ltag == 0) T=T->lchild;
		while(T->rtag == 1 && T->rchild != Th)
		{
			pre = T;
			T=T->rchild;
			printf("数值%c的节点即将释放\n",pre->data);
			free(pre);
			pre = NULL;
			printf("释放成功...\n") ;
		}
		
			pre = T;
			T=T->rchild;
			printf("数值%c的节点即将释放\n",pre->data);
			free(pre);
			pre = NULL;
			printf("释放成功...\n") ;
	}
	printf("头结点即将释放\n");
	free(Th);
	Th = NULL;
	printf("头结点释放成功...\n"); 
}

完整代码

#include<iostream>
#include<stack>
#include<algorithm>
#include<queue>
using namespace std;

typedef struct node
{
	int ltag,rtag;
	char data;
	struct node * lchild,*rchild;
}*Tree;


Tree pre;

void build(Tree &T)
{
	char data;
	scanf("%c",&data);
	if(data == '#')
		T=NULL;
	else
	{
		T=(Tree)malloc(sizeof (struct node));
		if(!T)
		{
			printf("分配失败！");
			return ; 	
		} 
		T->data = data;
		T->ltag=0;
		build(T->lchild);
		build(T->rchild);
	}
}

void preorder(Tree T)
{
	if(T != NULL)
	{
		 printf("%c ",T->data);
		 preorder(T->lchild);
		 preorder(T->rchild);		
	}
}

void preorder2(Tree T)
{
	Tree p = T;
	stack<Tree>s;
	while(p || !s.empty())
	{
		if(p)
		{
			printf("%c ",p->data);
			s.push(p);
			p = p->lchild;
		}
		else
		{
			p=s.top();
			s.pop();
			p=p->rchild;
		}
	}
}

void inorder(Tree T)
{
	if(T != NULL)
	{
		inorder(T->lchild);
		printf("%c ",T->data);
		inorder(T->rchild);
	}
 } 

void inorder2(Tree T)
{
	stack<Tree>s;
	Tree q = T;
	while(q || !s.empty())
	{
		if(q)
		{
			s.push(q);
			q = q->lchild;
		}
		else
		{
			q=s.top();
			printf("%c ",q->data);
			s.pop();
			q=q->rchild;
		}
	}
}

void postorder(Tree T)
{
	if(T != NULL)
	{
		postorder(T->lchild);
		postorder(T->rchild);
		printf("%c ",T->data);
	}
}


void postorder2(Tree T)
{
	stack<Tree>s;
	Tree q=T;
	Tree pre;
	while(q||!s.empty())
	{
		while(q)
		{
			s.push(q);
			q=q->lchild;
		}
		if(!s.empty())
		{
			q=s.top();
			s.pop();
		if(q->rchild == NULL || q->rchild == pre)
		{
			printf("%c ",q->data);
			pre=q;
			q=NULL;
		}
		else
		{
			s.push(q);
			q=q->rchild;
		}
		}	
	}
} 

void threading(Tree  T)
{
	if(T)
	{
	threading(T->lchild);
	if(!T->lchild)
	{
		T->ltag=1;
		T->lchild=pre;
	}
	if(!pre->rchild)
	{
		pre->rtag = 1;
		pre->rchild = T;
	}
	pre = T;
	threading(T->rchild);
	}
}

void inorderthread(Tree & Th, Tree T)
{
	Th=(Tree)malloc(sizeof (node));
	if(!Th)
	{
		printf("分配失败！");
		return ; 
	}
	Th->ltag=0,Th->rtag=1;
	Th->rchild=Th;
	if(T)
	{
		Th->lchild = T;
		pre = Th;
		threading(T);
		pre->rchild=Th,pre->rtag=1;
		Th->rchild=pre;
	}
	else
	Th->lchild=Th;
	
} 

void threadvisit(Tree Th)
{

	Tree T;
	T=Th->lchild;
	
	while(T != Th)
	{
		while(T->ltag == 0) T=T->lchild;
		printf("%c ",T->data);
		while(T->rtag == 1 && T->rchild != Th)
		{
			T=T->rchild;
			printf("%c ",T->data);
		}
		
		T=T->rchild;
	}
} 
void levelorder(Tree T)
{
		queue<Tree>q;
		Tree p = T;
		if(p)
		{
			q.push(p);
			while(!q.empty())
			{
			    p=q.front();
			    q.pop();
				printf("%c ",p->data);
				if(p->lchild)
				q.push(p->lchild);
				if(p->rchild)
				q.push(p->rchild);
			}
		}
} 

void FreeTree(Tree Th)
{
	Tree T;
	T=Th->lchild;
	
	while(T != Th)
	{
		while(T->ltag == 0) T=T->lchild;
		while(T->rtag == 1 && T->rchild != Th)
		{
			pre = T;
			T=T->rchild;
			printf("数值%c的节点即将释放\n",pre->data);
			free(pre);
			pre = NULL;
			printf("释放成功...\n") ;
		}
		
			pre = T;
			T=T->rchild;
			printf("数值%c的节点即将释放\n",pre->data);
			free(pre);
			pre = NULL;
			printf("释放成功...\n") ;
	}
	printf("头结点即将释放\n");
	free(Th);
	Th = NULL;
	printf("头结点释放成功...\n"); 
} 

int main()
{
	Tree T,Th;
	build(T);
	printf("递归的前序遍历：");
	preorder(T);
	printf("\n"); 
	
	printf("递归的中序遍历：");
	inorder(T);
	printf("\n");
	
	printf("递归的后序遍历：");
	postorder(T);
	printf("\n"); 
	
	printf("非递归的前序遍历：");
	preorder2(T);
	printf("\n");
	
	printf("非递归的中序遍历：");
	inorder2(T);
	printf("\n");
	
	printf("非递归的后序遍历： ");
	postorder2(T);
	printf("\n");
	
	printf("层次遍历： ");
	levelorder(T);
	printf("\n");
	printf("中序线索化后的二叉树：");
	inorderthread(Th, T); 
	threadvisit(Th);
	printf("\n");
	
	FreeTree(Th);
	
	return 0;
}

结果示例

在这里插入图片描述

版权声明：本文为m0_51305283原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/m0_51305283/article/details/121254541