数据结构：使用C++实现二叉树的深度优先搜索和广度优先搜索

二叉树的搜索主要依靠队列进行搜索，用头尾进行：先进先出，后进后出的原则

实现代码如下：

#include<iostream>
#include<time.h>
using namespace std;

typedef struct Node{
	int key;
	struct Node *lchild, *rchild;
}Node;

Node *getnewNode(int key){
	Node *p = new Node;
	p->key=key;
	p->lchild=p->rchild=NULL;
	return p;
}

Node *insert(Node *root,int key){
	if(root==NULL)	return getnewNode(key);
	if(rand()%2)	root->lchild=insert(root->lchild,key);
	else			root->rchild=insert(root->rchild,key);
	return root;
}

void clear(Node *root)
{
	if(root==NULL)	return;
	clear(root->lchild);
	clear(root->rchild);
	free(root);
	return;
}

#define MAX_NODE 10
Node *queue[MAX_NODE+5];
int head,tail;

void bfs(Node *root){
	head=tail=0;
	queue[tail++]=root;
	while(head<tail){
			Node *node=queue[head];
			cout<<endl<<"node: "<<node->key<<endl;
	if(node->lchild){
			queue[tail++]=node->lchild;
			cout<<' '<<node->key<<"->"<<node->lchild->key<<"(left)"<<endl;
		}
	if(node->rchild){
			queue[tail++]=node->rchild;
			cout<<' '<<node->key<<"->"<<node->rchild->key<<"(right)"<<endl;
		}
		head++;	
	}
	cout<<endl;
	return;
}

int tot=0;
void dfs(Node *root)
{
	if(root==NULL) return;
	int start,end;
	tot+=1;
	start=tot;
	if(root->lchild)	dfs(root->lchild);
	if(root->rchild)	dfs(root->rchild);
	tot+=1;
	end=tot;
	cout<<root->key<<" : "<<"["<<start<<','<<end<<"]"<<endl;
	return;
}


int main()
{
	srand(time(0));
	Node *root=NULL;
	for(int i=0;i<MAX_NODE;i++)
	{
		root=insert(root,rand()%100);
	}
	bfs(root);
	dfs(root);
	return 0;
}