二叉树的建立和递归遍历

代码如下：

#include<bits/stdc++.h>//¶þ²æÊ÷µÄ½¨Á¢ºÍµÝ¹é±éÀú 
using namespace std;
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void createBiTree(BiTree &t){//À¨ºÅÄÚµÄ BiTree &tµÈ¼ÛÓÚ BiTNode* &t
	char c;
	cin>>c;
	if(c == '#')//µ±Óöµ½ #ʱ£¬Áî¸ù½ÚµãΪNULL£¬½áÊøµô¸Ã·ÖÖ§µÄµÝ¹é 
		t = NULL;
	else{
		t = new BiTNode;
		t->data = c;
		createBiTree(t->lchild);
		createBiTree(t->rchild);
	}
}

void PreOrder(BiTree &t){
	if(t == NULL)
		return;
	cout<<t->data<<' ';
	PreOrder(t->lchild);
	PreOrder(t->rchild);
}

void InOrder(BiTree &t){
	if(t == NULL)
		return;
	InOrder(t->lchild);
	cout<<t->data<<' ';
	InOrder(t->rchild); 
}

void PostOrder(BiTree &t){
	if(t == NULL)
		return;
	PostOrder(t->lchild);
	PostOrder(t->rchild);
	cout<<t->data<<' ';
}

int main(){
	BiTree t;
	createBiTree(t);
	cout<<"¶þ²æÊ÷½¨Á¢Íê³É£¡"<<endl;
	cout<<"ÏÈÐò±éÀúÐòÁÐΪ£º"<<endl;
	PreOrder(t); 
	cout<<endl;
	cout<<"ÖÐÐò±éÀúÐòÁÐΪ£º"<<endl;
	InOrder(t);
	cout<<endl;
	cout<<"ºóÐò±éÀúÐòÁÐΪ£º"<<endl;
	PostOrder(t);
	cout<<endl;
	return 0;
}

测试结果 ：

假设我们要建立一个如下图所示的二叉树，#代表空节点，按照前序遍历顺序二叉树表示为：ab##c##

运行结果如下： 

完美运行！