本文共 2409 字，大约阅读时间需要 8 分钟。

这两天停更了博客，在停下来学习树。不得不说相比较于链表、栈和队列等，树有更复杂的结构和特性。当然基本思想也离不开前面学的基本结构。比较困难的点就在于如何优雅的实现二叉树的建立和遍历–递归思想。对于刚接触递归的我来说，还是需要多想多练。

本例结合“大话数据结构”中的例题，构建二叉树和用三种方法，实现对树的遍历。我们想创建一个前序为“AB#D##C##”的二叉树，将树中的每个空指针引出一个虚节点，用#表示，该树为扩展二叉树。

代码示例输出：

Enter characters in the preorder traversal:AB#D##C##With PreOrderTraverse:A at 1 level.B at 2 level.D at 3 level.C at 2 level.With InOrderTraverse:B at 2 level.D at 3 level.A at 1 level.C at 2 level.With PostOrderTraverse:D at 3 level.B at 2 level.C at 2 level.A at 1 level.

基本函数功能介绍：

void CreateTreePre(Tree &T);   //创建二叉树void PreOrderTraverse(Tree T, int level);   //前序遍历树void InOrderTraverse(Tree T, int level);   //中序遍历树void PostOrderTraverse(Tree T, int level);   //后续遍历树void operate(ElemType ch, int level);   //遍历过程中执行的操作

需要注意的问题：

在创建树的过程中，注意函数原型为：void CreateTreePre(Tree &T);   //创建二叉树其中形参为引用类型，刚开始时没有用引用，导致虽然在构建二叉树时没有报错，但是在树的遍历的时候，无论如何也读不到值。在对其地址进行输出分析之后，发现问题就在于不是引用，提醒自己以后此类问题勿犯。

完整程序：

#include
   
    #include
    
     using namespace std;typedef char ElemType;struct Node{
   	ElemType data;	Node * lchild;	Node * rchild;};typedef Node* Tree;void CreateTreePre(Tree &T);void PreOrderTraverse(Tree T, int level);void InOrderTraverse(Tree T, int level);void PostOrderTraverse(Tree T, int level);void operate(ElemType ch, int level);void main(){
   	Tree test1 = nullptr;	cout << "Enter characters in the preorder traversal: \n";	CreateTreePre(test1);	int level = 1;	cout << "With PreOrderTraverse: \n";	PreOrderTraverse(test1, level);	cout << "With InOrderTraverse: \n";	InOrderTraverse(test1, level);	cout << "With PostOrderTraverse: \n";	PostOrderTraverse(test1, level);}void CreateTreePre(Tree &T){
   	ElemType ch;	cin >> ch;	if (ch == '#')		T = nullptr;	else	{
   		T = new Node;		T->data = ch;		CreateTreePre(T->lchild);		CreateTreePre(T->rchild);	}}void operate(ElemType ch, int level){
   	cout << ch << " at " << level << " level.\n";}void PreOrderTraverse(Tree T, int level){
   	if (T == nullptr)		return;	operate(T->data, level);	PreOrderTraverse(T->lchild, level + 1);	PreOrderTraverse(T->rchild, level + 1);}void InOrderTraverse(Tree T, int level){
   	if (T == nullptr)		return;	InOrderTraverse(T->lchild, level + 1);	operate(T->data, level);	InOrderTraverse(T->rchild, level + 1);}void PostOrderTraverse(Tree T, int level){
   	if (T == nullptr)		return;	PostOrderTraverse(T->lchild, level + 1);	PostOrderTraverse(T->rchild, level + 1);	operate(T->data, level);}
    
   

转载地址：http://kpyci.baihongyu.com/