C++实现二叉树链表存储结构先中后序遍历的递归算法和非递归算法和顺序存储完全二叉树

二叉树链表结点结构如下：

 

typedef char DataType;
struct BiNode
{
	DataType data;
	BiNode *lchild,*rchild;
};

创建二叉树的递归算法描述（ C++ ）如下：

 

BiNode *BiTree::Create(BiNode *bt)
{
	static int i=0;
	char ch;
	string str="AB#D##C##";
	ch=str[i++];
	if(ch=='#')bt=nullptr;//建立一棵空树 
	else {
		bt=new BiNode;bt->data=ch;//生成一个结点，数据域为ch
		bt->lchild=Create(bt->lchild);//递归建立左子树
		bt->rchild=Create(bt->rchild);//递归建立右子树
	}
	return bt;
}

void BiTree::Preorder(BiNode *bt)
{
	if(bt==nullptr)return;//递归调用的结束条件
	else{
		cout<<bt->data<<" ";//访问根节点bt的数据域
		Preorder(bt->lchild);//前序递归遍历bt的左子树
		Preorder(bt->rchild);//前序递归遍历bt的右子树
	}
}

void BiTree::Inorder(BiNode *bt)
{
	if(bt==nullptr)return;//递归调用的结束条件
	else{
		Inorder(bt->lchild);//中序递归遍历bt的左子树
		cout<<bt->data<<" ";//访问根节点的数据域
		Inorder(bt->rchild);//中序递归遍历bt的右子树
	}
}

二叉树的后序遍历递归算法描述（C++）如下：

void BiTree::Postorder(BiNode *bt)
{
	if(bt==nullptr)return;//递归调用的结束条件
	else{
		Postorder(bt->lchild);//后序递归遍历bt的左子树
		Postorder(bt->rchild);//后序递归遍历bt的右子树
		cout<<bt->data<<" ";//访问根节点bt的数据域
	}
}

二叉树的层序遍历递归算法描述（C++）如下：

void BiTree::Levelorder(BiNode *bt){
	BiNode *Q[100],*q=nullptr;
	int front=-1,rear=-1;//队列初始化 
	if(root == nullptr) return;//二叉树为空，算法结束
	Q[++rear]=root;//根指针入队
	while(front!=rear){//当队列非空时 
		q=Q[++front];//出队
		cout<<q->data<<" ";
		if(q->lchild!=nullptr) Q[++rear]=q->lchild;
		if(q->rchild!=nullptr) Q[++rear]=q->rchild; 
	} 
}

二叉树的销毁二叉树算法描述（C++）如下：

void BiTree::Release(BiNode *bt)
{
	if(bt!=nullptr){
		Release(bt->lchild);
		Release(bt->rchild);
		delete bt;
	}
}

C++实现二叉树完整代码 ：

#include<iostream>
using namespace std;
typedef char DataType;
struct BiNode
{
	DataType data;
	BiNode *lchild,*rchild;
};
class BiTree
{
	public:
		BiTree(){root=Create(root);}//构造函数，建立一颗二叉树
		~BiTree(){Release(root);}//析构函数，释放各个节点的存储空间
		void Preorder(){Preorder(root);}//前序遍历二叉树
		void Inorder(){Inorder(root);}//中序遍历二叉树
		void Postorder(){Postorder(root);}//后序遍历二叉树
		void Levelorder(){Levelorder(root);};//层序遍历二叉树
	private:
		BiNode *root;//指向根节点的头指针
		BiNode *Create(BiNode *bt);//构造函数调用
		void Release(BiNode *bt);//析构函数调用
		void Preorder(BiNode *bt);//前序遍历函数调用
		void Inorder(BiNode *bt);//中序遍历函数调用
		void Postorder(BiNode *bt);//后序遍历函数调用
		void Levelorder(BiNode *bt);//层序遍历函数调用
};
//前序遍历
void BiTree::Preorder(BiNode *bt)
{
	if(bt==nullptr)return;//递归调用的结束条件
	else{
		cout<<bt->data<<" ";//访问根节点bt的数据域
		Preorder(bt->lchild);//前序递归遍历bt的左子树
		Preorder(bt->rchild);//前序递归遍历bt的右子树
	}
}
//中序遍历
void BiTree::Inorder(BiNode *bt)
{
	if(bt==nullptr)return;//递归调用的结束条件
	else{
		Inorder(bt->lchild);//中序递归遍历bt的左子树
		cout<<bt->data<<" ";//访问根节点的数据域
		Inorder(bt->rchild);//中序递归遍历bt的右子树
	}
}
//后序遍历
void BiTree::Postorder(BiNode *bt)
{
	if(bt==nullptr)return;//递归调用的结束条件
	else{
		Postorder(bt->lchild);//后序递归遍历bt的左子树
		Postorder(bt->rchild);//后序递归遍历bt的右子树
		cout<<bt->data<<" ";//访问根节点bt的数据域
	}
}
//层序遍历
void BiTree::Levelorder(BiNode *bt){
	BiNode *Q[100],*q=nullptr;
	int front=-1,rear=-1;//队列初始化 
	if(root == nullptr) return;//二叉树为空，算法结束
	Q[++rear]=root;//根指针入队
	while(front!=rear){//当队列非空时 
		q=Q[++front];//出队
		cout<<q->data<<" ";
		if(q->lchild!=nullptr) Q[++rear]=q->lchild;
		if(q->rchild!=nullptr) Q[++rear]=q->rchild; 
	} 
}
//创建二叉树 
BiNode *BiTree::Create(BiNode *bt)
{
	static int i=0;
	char ch;
	string str="AB#D##C##";
	ch=str[i++];
	if(ch=='#')bt=nullptr;//建立一棵空树 
	else {
		bt=new BiNode;bt->data=ch;//生成一个结点，数据域为ch
		bt->lchild=Create(bt->lchild);//递归建立左子树
		bt->rchild=Create(bt->rchild);//递归建立右子树
	}
	return bt;
}
//销毁二叉树 
void BiTree::Release(BiNode *bt)
{
	if(bt!=nullptr){
		Release(bt->lchild);
		Release(bt->rchild);
		delete bt;
	}
}
int main()
{
	cout<<"创建一棵二叉树"<<endl;
	BiTree T{};//创建一颗二叉树
	cout<<"---层序遍历---"<<endl;//A B C D 
	T.Levelorder();
	cout<<endl;
	cout<<"---前序遍历---"<<endl;//A B D C
	T.Preorder();
	cout<<endl;
	cout<<"---中序遍历---"<<endl;//B D A C
	T.Inorder();
	cout<<endl;
	cout<<"---后序遍历---"<<endl;//D B C A
	T.Postorder();
	cout<<endl;
	return 0;
}
 

实验结果图：

中序遍历非递归算法思路：从当前结点开始遍历

• ① 若当前结点存在，就存入栈中，并访问左子树；
• ② 直到当前结点不存在，就出栈并访问输出栈顶，并通过栈顶结点访问右子树；
• ③ 不断重复①②，直到当前结点不存在且栈空。

中序遍历非递归算法：在二叉树的中序遍历中，访问结点的操作发生在该结点的左子树遍历完毕并准备遍历右子树时，所以，在遍历过程中遇到某结点时并不能立即访问它，而是将它压栈，等到它的左子树遍历完毕后，再从栈中弹出并访问之。中序遍历的非递归算法只需将前序遍历非递归算法中的输出操作移到出栈操作bt=S[top--]之后即可。

二叉树中序遍历的非递归算法用伪代码如下：

算法：Inorder

输入：二叉链表的根指针bt

输出：前序遍历序列

          1.栈S初始化

           2.循环直到bt为空且栈为空

               2.1.1当bt不为空的时循环

               2.1.2准备遍历bt的左子树

           2.2如果栈S不空，则

               2.2.1 将栈顶元素弹出至bt;

               2.2.2输出bt->data;

               2.2.3准备遍历bt的右子树;

简单起见，栈采用顺序存储结构并不假定不会发生溢出

void BiTree::Inorder(BiNode *bt)
{
	int top=-1;
	BiNode *s[20];
	while(bt!=nullptr || top!=-1) //两个条件都不成立才退出循环
	{
		while(bt!=nullptr) 
		{ 
			
			s[++top]=bt; //将根指针 bt 入栈
			bt=bt->lchild;
		}
		if(top!=-1) //栈非空
		{
			bt=s[top--];
			printf("%c ",bt->data);//出栈时，访问输出
			bt=bt->rchild;
		}
	}
	
}

后序遍历非递归算法思路：从当前结点开始遍历

• ①若当前节点存在，就存入栈中，并且置结点flag为1（表示第一次访问），然后访问其左子树；
• ② 直到当前结点不存在，需要回退。当栈顶结点flag为1时，则表明是从左子树回退，这时需置栈顶结点flag为2（第二次访问），然后通过栈顶结点访问其右子树（不出栈）；当栈顶结点flag为2时，则表明是从右子树回退，这时需出栈，并取出栈结点做访问输出。（输出完成需要置当前结点为空，以便继续回退）；
• ③ 不断重复①②，直到当前结点不存在且栈空。

void BiTree::Postorder(BiNode *bt)
{
	int top=-1;
	BiNode *s[20];
	int flagStack[20];
	while(bt!=nullptr || top!=-1) //两个条件都不成立才退出循环
	{
		if(bt!=nullptr) 
		{ 
			s[++top]=bt; //将根指针 bt 入栈
			flagStack[top]=1;
			bt=bt->lchild;
		}else{
			if(flagStack[top] == 1){//第二次访问，flag置2，取栈顶元素但不出栈
				bt=s[top];
				flagStack[top]=2;
				bt=bt->rchild; 
			}else{
				bt=s[top--];
				printf("%c ",bt->data);//出栈时，访问输出
				bt=nullptr;
			}
		}
	}
}

C++完整代码实现二叉树链表存储结构先中后序遍历非递归算法

#include<iostream>
using namespace std;
typedef char DataType;
struct BiNode
{
	DataType data;
	BiNode *lchild,*rchild;
};
class BiTree
{
	public:
		BiTree(){root=Create(root);}//构造函数，建立一颗二叉树
		~BiTree(){Release(root);}//析构函数，释放各个节点的存储空间
		void Preorder(){Preorder(root);}//前序遍历二叉树
		void Inorder(){Inorder(root);}//中序遍历二叉树
		void Postorder(){Postorder(root);}//后序遍历二叉树
		void Levelorder(){Levelorder(root);};//层序遍历二叉树
	private:
		BiNode *root;//指向根节点的头指针
		BiNode *Create(BiNode *bt);//构造函数调用
		void Release(BiNode *bt);//析构函数调用
		void Preorder(BiNode *bt);//前序遍历函数调用
		void Inorder(BiNode *bt);//中序遍历函数调用
		void Postorder(BiNode *bt);//后序遍历函数调用
		void Levelorder(BiNode *bt);//层序遍历函数调用
};
//前序遍历
void BiTree::Preorder(BiNode *bt)
{
	int top=-1;
	BiNode *s[20];
	while(bt!=nullptr || top!=-1) //两个条件都不成立才退出循环
	{
		while(bt!=nullptr) 
		{ 
			printf("%c ",bt->data);//入栈时，访问输出
			s[++top]=bt; //将根指针 bt 入栈
			bt=bt->lchild;
		}
		if(top!=-1) //栈非空
		{
			bt=s[top--];
			bt=bt->rchild;
		}
	}
}
//中序遍历
void BiTree::Inorder(BiNode *bt)
{
	int top=-1;
	BiNode *s[20];
	while(bt!=nullptr || top!=-1) //两个条件都不成立才退出循环
	{
		while(bt!=nullptr) 
		{ 
			
			s[++top]=bt; //将根指针 bt 入栈
			bt=bt->lchild;
		}
		if(top!=-1) //栈非空
		{ 
			bt=s[top--];
			printf("%c ",bt->data);//出栈时，访问输出
			bt=bt->rchild;
		}
	}
	
}
//后序遍历
void BiTree::Postorder(BiNode *bt)
{
	int top=-1;
	BiNode *s[20];
	int flagStack[20];
	while(bt!=nullptr || top!=-1) //两个条件都不成立才退出循环
	{
		if(bt!=nullptr) 
		{ 
			s[++top]=bt; //将根指针 bt 入栈
			flagStack[top]=1;
			bt=bt->lchild;
		}else{
			if(flagStack[top] == 1){//第二次访问，flag置2，取栈顶元素但不出栈
				bt=s[top];
				flagStack[top]=2;
				bt=bt->rchild; 
			}else{
				bt=s[top--];
				printf("%c ",bt->data);//出栈时，访问输出
				bt=nullptr;
			}
		}
	}
}
//层序遍历
void BiTree::Levelorder(BiNode *bt){
	BiNode *Q[100],*q=nullptr;
	int front=-1,rear=-1;//队列初始化 
	if(root == nullptr) return;//二叉树为空，算法结束
	Q[++rear]=root;//根指针入队
	while(front!=rear){//当队列非空时 
		q=Q[++front];//出队
		cout<<q->data<<" ";
		if(q->lchild!=nullptr) Q[++rear]=q->lchild;
		if(q->rchild!=nullptr) Q[++rear]=q->rchild; 
	} 
}
//创建二叉树 
BiNode *BiTree::Create(BiNode *bt)
{
	static int i=0;
	char ch;
	string str="AB#D##C##";
	ch=str[i++];
	if(ch=='#')bt=nullptr;//建立一棵空树 
	else {
		bt=new BiNode;bt->data=ch;//生成一个结点，数据域为ch
		bt->lchild=Create(bt->lchild);//递归建立左子树
		bt->rchild=Create(bt->rchild);//递归建立右子树
	}
	return bt;
}
//销毁二叉树 
void BiTree::Release(BiNode *bt)
{
	if(bt!=nullptr){
		Release(bt->lchild);
		Release(bt->rchild);
		delete bt;
	}
}
int main()
{
	cout<<"创建一棵二叉树"<<endl;
	BiTree T{};//创建一颗二叉树
	cout<<"---层序遍历---"<<endl;//A B C D 
	T.Levelorder();
	cout<<endl;
	cout<<"---前序遍历---"<<endl;//A B D C
	T.Preorder();
	cout<<endl;
	cout<<"---中序遍历---"<<endl;//B D A C
	T.Inorder();
	cout<<endl;
	cout<<"---后序遍历---"<<endl;//D B C A
	T.Postorder();
	cout<<endl;
	return 0;
}
 

实验结果贴图：

3）顺序存储完全二叉树

完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为 i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相

同，则这棵二叉树称为完全二叉树。如图所示，即为一棵完全二叉树。其先序遍 历为：A B D H I E J C F G，中序遍历为：H D I B J E A F C G，

后序遍历为：H I D J E B F G C A。

 

①构建顺序存储二叉树

//完全二叉树的顺序存储结构
#include <iostream>
#include <string.h>
#define MaxSize 100
using namespace std;
typedef char DataType;
class Tree{
	public:
		Tree(string str);//构造函数
		void createTree();//创建二叉树 
		void seqPreorder(int i);//先序遍历二叉树 
		void seqInorder(int i);//中序遍历二叉树 
		void seqPostorder(int i);//后序遍历二叉树 
	private: 
		DataType node[MaxSize];//结点中的数据元素
		int num=0;//二叉树结点个数 
		string str;
};

Tree::Tree(string str){
	this->str = str;
} 

void Tree::createTree(){
	for(int i = 1;i < str.length()+1 ;i++){
		node[i]=str[i-1];
		num++;
	}
	node[0] = (char)num;
}

②顺序存储的完全二叉树递归先序遍历算法描述（C++）如下：

void Tree::seqPreorder(int i){
	if(i==0)//递归调用的结束条件
		return;
	else{
		cout<<"  "<<(char)node[i];//输出根结点
		if(2*i<=(char)node[0])
			seqPreorder(2*i);//先序遍历i的左子树
		else
			seqPreorder(0);
		if(2*i+1<=(char)node[0])
			seqPreorder(2*i+1);//先序遍历i的右子树
		else
			seqPreorder(0); 
	} 
} 

③顺序存储的完全二叉树递归中序遍历算法描述（C++）如下：

void Tree::seqInorder(int i){
	if(i==0)//递归调用的结束条件
		return;
	else{
		if(2*i<=(char)node[0])
			seqInorder(2*i);//中序遍历i的左子树
		else
			seqInorder(0);
		cout<<"  "<<(char)node[i];//输出根结点
		if(2*i+1<=(char)node[0])
			seqInorder(2*i+1);//中序遍历i的右子树
		else
			seqInorder(0); 
	} 
}

④顺序存储的完全二叉树递归后序遍历算法描述（C++）如下：

void Tree::seqPostorder(int i){
	if(i==0)//递归调用的结束条件
		return;
	else{
		if(2*i<=(char)node[0])
			seqPostorder(2*i);//后序遍历i的左子树
		else
			seqPostorder(0);
		if(2*i+1<=(char)node[0])
			seqPostorder(2*i+1);//后序遍历i的右子树
		else
			seqPostorder(0); 
		cout<<"  "<<(char)node[i];//输出根结点
	} 
} 

C++实现顺序存储完全二叉树完整代码：

//完全二叉树的顺序存储结构
#include <iostream>
#include <string.h>
#define MaxSize 100
using namespace std;
typedef char DataType;
class Tree{
	public:
		Tree(string str);//构造函数
		void createTree();//创建二叉树 
		void seqPreorder(int i);//先序遍历二叉树 
		void seqInorder(int i);//中序遍历二叉树 
		void seqPostorder(int i);//后序遍历二叉树 
	private: 
		DataType node[MaxSize];//结点中的数据元素
		int num=0;//二叉树结点个数 
		string str;
};

Tree::Tree(string str){
	this->str = str;
} 

void Tree::createTree(){
	for(int i = 1;i < str.length()+1 ;i++){
		node[i]=str[i-1];
		num++;
	}
	node[0] = (char)num;
}

//顺序存储的完全二叉树递归先序遍历算法描述（C++）如下：
void Tree::seqPreorder(int i){
	if(i==0)//递归调用的结束条件
		return;
	else{
		cout<<"  "<<(char)node[i];//输出根结点
		if(2*i<=(char)node[0])
			seqPreorder(2*i);//先序遍历i的左子树
		else
			seqPreorder(0);
		if(2*i+1<=(char)node[0])
			seqPreorder(2*i+1);//先序遍历i的右子树
		else
			seqPreorder(0); 
	} 
} 

//顺序存储的完全二叉树递归中序遍历算法描述（C++）如下：
void Tree::seqInorder(int i){
	if(i==0)//递归调用的结束条件
		return;
	else{
		if(2*i<=(char)node[0])
			seqInorder(2*i);//中序遍历i的左子树
		else
			seqInorder(0);
		cout<<"  "<<(char)node[i];//输出根结点
		if(2*i+1<=(char)node[0])
			seqInorder(2*i+1);//中序遍历i的右子树
		else
			seqInorder(0); 
	} 
} 

//顺序存储的完全二叉树递归后序遍历算法描述（C++）如下：
void Tree::seqPostorder(int i){
	if(i==0)//递归调用的结束条件
		return;
	else{
		if(2*i<=(char)node[0])
			seqPostorder(2*i);//后序遍历i的左子树
		else
			seqPostorder(0);
		if(2*i+1<=(char)node[0])
			seqPostorder(2*i+1);//后序遍历i的右子树
		else
			seqPostorder(0); 
		cout<<"  "<<(char)node[i];//输出根结点
	} 
} 

int main(){
	string str = "ABCDEFGHIJ";
	Tree T{str};//定义对象变量bus
	cout<<"按层序编号的顺序存储所有结点:"<<str<<endl;
	T.createTree();
	cout<<"顺序存储的完全二叉树递归前序递归遍历:"<<endl; 
	T.seqPreorder(1);
	cout<<endl; 
	cout<<"顺序存储的完全二叉树递归中序递归遍历:"<<endl; 
	T.seqInorder(1);
	cout<<endl; 
	cout<<"顺序存储的完全二叉树递归后序递归遍历:"<<endl; 
	T.seqPostorder(1);
	cout<<endl; 
	return 0;
}

实验结果贴图：

我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞+收藏+加关注喔~

如果文章有不正确的地方，欢迎交流指正，我将虚心请教~o(>ω<)o

我会定期更新文章，继续为您提供优质文章~o(>ω<)o