二叉树的先序递归建立与遍历

二叉树的树结构很简单,用一个结构体就可以完成。

struct node    //二叉树的结点
{
	char data;    //存放当前二叉树结点的数据
	node *left,*right;     //指向下一个二叉树的左子树和右子树
}*p;   //指向树根的结点p

二叉树的先序建立用递归就可以了,下面给出代码

void create_bitree(node *&p)   //递归建立二叉树
{
	char c;
	cin>>c;
	if(c=='#')
	{
		p=NULL;   //如果当前输入为'#'证明当前为NULL指向
	}
	else
	{
		p=new node;   //为当前的p指向的结点开辟空间
		p->data=c;    //放置二叉树的数据
		create_bitree(p->left);    //递归建立左子树
		create_bitree(p->right);   //递归建立右子树
	}
}

遍历二叉树也很简单,直接递归即可

void preorder(node *&p)
{
	if(p!=NULL)
	{
		cout<<p->data;     //输出当前的结点的数据
		preorder(p->left);   //递归访问左子树
		preorder(p->right);   //递归访问右子树
	}
}

下面给出完整的代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
	char data;
	node *left,*right;
}*p;
void create_bitree(node *&p)
{
	char c;
	cin>>c;
	if(c=='#')
	{
		p=NULL;
	}
	else
	{
		p=new node;
		p->data=c;
		create_bitree(p->left);
		create_bitree(p->right);
	}
}
void preorder(node *&p)
{
	if(p!=NULL)
	{
		cout<<p->data;
		preorder(p->left);
		preorder(p->right);
	}
}
int main()
{
	create_bitree(p);
	preorder(p);
	return 0;
}

上面有完整细节

全部评论

相关推荐

头像 头像
03-18 20:55
浙江师范大学
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务