算法/C++ 二叉树的创建并用BFS遍历

 这是我们要创建的二叉树

			            E
			    B                G
			lA     rD       lF       rI
			     lC               lH

具体创建操作如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
struct Node{
	char value;
	int lchild,rchild;
}node[maxn];
int index=0;
int newNode(char val){
	node[index].value=val;
	node[index].lchild=-1;
	node[index].rchild=-1;
	return index++;
}
void insert(int &father,int child,int l_r){
	if(l_r==0)
		node[father].lchild=child;
	else
		node[father].rchild=child;
}
int buildtree(){
	int A=newNode('A');int B=newNode('B');int C=newNode('C');
	int D=newNode('D');int E=newNode('E');int F=newNode('F');
	int G=newNode('G');int H=newNode('H');int I=newNode('I');
	insert(E,B,0);insert(E,G,1);insert(B,A,0);insert(B,D,1);
	insert(G,F,0);insert(G,I,1);insert(D,C,0);insert(I,H,1);
	int root=E;
	return root;
}

遍历方式：

1，BFS（广度优先，逐层遍历）

int main(){
	int root=buildtree();
	queue<int> q;
	q.push(root);
	while(q.size()){
		int tmp=q.front();
		cout<<node[tmp].value<<" ";
		q.pop();
		if(node[tmp].lchild!=-1)
			q.push(node[tmp].lchild);
		if(node[tmp].rchild!=-1)
			q.push(node[tmp].rchild);
	}
	return 0;
}
//E B G A D F I C H

2，深度优先:

int visit_timer=0;
void visit_order(int father){//递归的顺序
	if(father!=-1){
		printf("visit[%c]=%d;\n",node[father].value,++visit_timer);
		visit_order(node[father].lchild);
		visit_order(node[father].rchild);
		printf("visit[%c]=%d;\n",node[father].value,++visit_timer);
	}
}
//visit[E]=1;
//visit[B]=2;
//visit[A]=3;
//visit[A]=4;
//visit[D]=5;
//visit[C]=6;
//visit[C]=7;
//visit[D]=8;
//visit[B]=9;
//visit[G]=10;
//visit[F]=11;
//visit[F]=12;
//visit[I]=13;
//visit[H]=14;
//visit[H]=15;
//visit[I]=16;
//visit[G]=17;
//visit[E]=18;
int deep[maxn]={0};//节点的深度
int deep_timer=0;
void deep_node(int father){
	if(father!=-1){
		deep[father]=++deep_timer;
		printf("deep[%c]=%d;\n",node[father].value,deep[father]);
		deep_node(node[father].lchild);
		deep_node(node[father].rchild);
		deep_timer--;
	}
}
//deep[E]=1;
//deep[B]=2;
//deep[A]=3;
//deep[D]=3;
//deep[C]=4;
//deep[G]=2;
//deep[F]=3;
//deep[I]=3;
//deep[H]=4;
int num[maxn]={0};//子节点的个数
int num_node(int father){
	if(father==-1) return 0;
	else{
		num[father]=num_node(node[father].lchild)+num_node(node[father].rchild)+1;
		printf("num[%c]=%d;\n",node[father].value,num[father]);
		return num[father];
	}
}
//num[A]=1;
//num[C]=1;
//num[D]=2;
//num[B]=4;
//num[F]=1;
//num[H]=1;
//num[I]=2;
//num[G]=4;
//num[E]=9;
void preorder(int father){//先（父）序序列 先父节点再左右子节点
	if(father!=-1){
		cout<<node[father].value<<' ';
		preorder(node[father].lchild);
		preorder(node[father].rchild);
	}
	return;
}
//E B A D C G F I H
void inorder(int father){//中序序列
	if(father!=-1){
		inorder(node[father].lchild);
		cout<<node[father].value<<' ';
		inorder(node[father].rchild);
	}
}
//A B C D E F G H I
void postorder(int father){//后（父）序序列 先左右子节点再父节点
	if(father!=-1){	
		postorder(node[father].lchild);
		postorder(node[father].rchild);
		cout<<node[father].value<<' ';
	}
	return;
//A C D B F H I G E
}
int main(){
	int root=buildtree();
	visit_order(root);
	deep_node(root);
	num_node(root);
	preorder(root);
    inorder(root);
    postorder(root);
	return 0;
}