问题描述： 以一定的方式输入数据（本文是以先序遍历的方式输入），程序根据数据进行解析，创建二叉树，然后对二叉树进行操作，主要操作包括以下几种：
求二叉树的高度先序遍历二叉树中序遍历二叉树后序遍历二叉树层序遍历二叉树先序遍历： 根节点->左子树->右子树 中序遍历： 左子树->根节点->右子树 先序遍历： 左子树->右子树->根节点 层序遍历： 第一层（根节点）->第二层->第三次->….
PS： 1. 大家可以清楚的看到，先序，中序和后序是相对于根节点而言的 2. 非递归版本可以查看我的另外一篇文章： http://blog.csdn.net/yi_ming_he/article/details/71272568
以下面的例子进行说明：
如图所示，根据上面的遍历顺序，我们可以得到以下遍历结果： 先序遍历： a b d h e c f g 中序遍历： h d b e a f c g 后序遍历： h d e b f g c a 层序遍历： a b c d e f g h
参考代码：
#include <stdio.h> #include <malloc.h> #include <queue> typedef struct BiTNode { char data; struct BiTNode* lchild; struct BiTNode* rchild; }BiTNode, *Bitree; void CreateBiTree(Bitree& T) { char ch; scanf_s("%c", &ch); //按照先序输入输入二叉树中的节点值，其中#表示空树 if (ch == '#') T = NULL; else { T = (Bitree)malloc(sizeof(BiTNode)); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } void PreOrderTraverseByRecursion(Bitree T) { if (!T) return; printf("%c ", T->data); PreOrderTraverseByRecursion(T->lchild); PreOrderTraverseByRecursion(T->rchild); } void InOrderTraverseByRecursion(Bitree T) { if (!T) return; InOrderTraverseByRecursion(T->lchild); printf("%c ", T->data); InOrderTraverseByRecursion(T->rchild); } void PostOrderTraverseByRecursion(Bitree T) { if (!T) return; PostOrderTraverseByRecursion(T->lchild); PostOrderTraverseByRecursion(T->rchild); printf("%c ", T->data); } int GetBiTreeHeight(Bitree T) { if (!T) return 0; int nLeftHeight = GetBiTreeHeight(T->lchild); int nRightHeight = GetBiTreeHeight(T->rchild); return (nLeftHeight > nRightHeight ? nLeftHeight : nRightHeight) + 1; } void TraverseTreeByLevel(Bitree T, int nLevel) { if (!T || nLevel < 1) return; if (1 == nLevel) { printf("%c ", T->data); return; } TraverseTreeByLevel(T->lchild, nLevel - 1); TraverseTreeByLevel(T->rchild, nLevel - 1); } void LevelOrderTraverseByRecursion(Bitree T) { int nHeight = GetBiTreeHeight(T); for (int i = 1; i <= nHeight; i++) TraverseTreeByLevel(T, i); } int main() { Bitree T; CreateBiTree(T); printf("树的高度是: %d\n", GetBiTreeHeight(T)); printf("先序遍历(递归)：\n"); PreOrderTraverseByRecursion(T); printf("\n"); printf("中序遍历(递归)：\n"); InOrderTraverseByRecursion(T); printf("\n"); printf("后序遍历(递归)：\n"); PostOrderTraverseByRecursion(T); printf("\n"); printf("层序遍历(递归)：\n"); LevelOrderTraverseByRecursion(T); printf("\n"); return 0; }运行结果：
