二叉树学习（1）

二叉树学习（一）

如图所示的二叉树：

先序遍历为：ABDHIEJKCFLMGNO

中序遍历为：HDIBJEKALFMCNGO

后序遍历为：HIDJKEBLMFNOGCA

层次遍历为：ABCDEFGHIJKLMNO

然后，建立二叉树。先序遍历、中序遍历、后序遍历、层次遍历。

<pre name="code" class="cpp">#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
struct node
{
	char data;
	node *lchild,*rchild;
};
node *insert()//建立二叉树
{
	char ch;
	scanf("%c",&ch);
	node *current;
	if(ch=='#')
		current=NULL;
	else
	{
		current=new node;
		current->data=ch;
		current->lchild=insert();
		current->rchild=insert();
	}
	return current;
}
void pre(node *root)//先序遍历
{
	if (root)
	{
		printf("%c ",root->data);
		pre(root->lchild);
		pre(root->rchild);
	}
}
void in(node *root)//中序遍历
{

	if (root)
	{
		in(root->lchild);
		printf("%c ",root->data);
		in(root->rchild);
	}
}
void post(node *root)//后序遍历
{
	if (root)
	{
		post(root->lchild);
		post(root->rchild);
		printf("%c ",root->data);
	}
}
void bfs(node *root)//层次遍历1
{
	queue<node*>v;
	v.push(root);
	while (!v.empty())
	{
		root=v.front();
		v.pop();
		printf("%c ",root->data);
		if (root->lchild!=NULL)
			v.push(root->lchild);
		if (root->rchild)
			v.push(root->rchild);
	}
}
// void bfs(node *root)//层次遍历2
// {
// 	if (root==NULL)
// 	{
// 		return ;
// 	}
// 	queue<node*>v;
// 	while (true)
// 	{
// 		if (root->lchild!=NULL)
// 			v.push(root->lchild);
// 		if (root->rchild!=NULL)
// 			v.push(root->rchild);
// 		printf("%c ",root->data);
// 		if (v.empty())
// 			break;
// 		root=v.front();
// 		v.pop();
// 	}
// }
int main()
{
	node *root=insert();
	printf("pre::\n");
	pre(root);
	printf("\nin::\n");
	in(root);
	printf("\npost::\n");
	post(root);
	printf("\nbfs\n");
	bfs(root);
	printf("\n");
	return 0;
}

Input：ABDH##I##EJ##K##CFL##M##GN##O##