数据结构——二叉树的创建与遍历（链式存储结构）

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。以下是对链式存储结构的二叉树的创建与先序、中序、后序遍历操作：

定义二叉树节点

每个节点由三个部分组成：
数据部分
左孩子节点
右孩子节点

typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree; 

主函数

声明初始节点时，是BiTree bt，此时bt是节点指针，如果写的是BiTNode bt，则为节点元素。为了传地址操作方便，我们使用声明节点地址的形式。

int main(){BiTree bt;//指针 initial(&bt);cout<<"先序创建树（输入#停止生成节点）：\n"; createTree(&bt);cout<<"先序遍历：\n"; preOrder(bt);cout<<"\n中序遍历：\n"; inOrder(bt);cout<<"\n后序遍历：\n";postOrder(bt); return 0;} 

初始化

我们在主函数里以initial(&bt)的形式调用bt指针，即将指针地址传入初始化函数里。参数里写的是(BiTree bt)表示bt是指向根节点这个节点指针的指针。
此时bt指的是根节点指针，(BiTree)malloc(sizeof(BiTNode))为该节点分配空间。
初始时均无左右孩子，所以设为NULL。

Status initial(BiTree *bt){//指针的指针 *bt = (BiTree)malloc(sizeof(BiTNode));(*bt)->lchild = NULL;(*bt)->rchild = NULL;}

创建二叉树

依然是以指针的指针的形式将节点指针传入函数里
我们设置输入“#”为输入结束。
当输入的元素不是“#”时，为节点指针开辟空间后，将元素赋给该节点的data。
然后递推式创建左右孩子。

Status createTree(BiTree *bt){ElemType c;c = getchar();if(c=='#'){*bt = NULL;}else{*bt = (BiTree)malloc(sizeof(BiTNode));(*bt)->data = c;createTree(&(*bt)->lchild);createTree(&(*bt)->rchild);}}

值得注意的是：因为我们使用的是“指针的指针”，所以递推式将创建其左右孩子时，记得是将其左右孩子的地址传入createTree函数里
（即：&(*bt)->child的形式）

关于先序、中序和后序遍历

先序遍历最容易理解：从根节点开始输出，一直向左遍历输出，到尽头后再找到该节点兄弟右节点输出，然后再去到父亲节点的兄弟右节点输出……以此类推。
中序遍历：从左子树的最左边最底层的左孩子节点开始输出，然后输出其父亲节点，再输出其兄弟右节点，然后输出其父亲节点的父亲节点……以此类推。
后序遍历：从左子树的最左边最底层的左孩子节点开始输出，然后输出其兄弟右节点，然后输出其父亲节点，然后输出其父亲节点的熊迪右节点……以此类推。

示例1

我们来创建一个如下图的树：

示例2

示例3

简单粗暴地画法就是遵守这个规律：

先序、中序、后序遍历代码实现：

void preOrder(BiTree bt){//指针形参 if(bt!=NULL){cout<<bt->data<<" ";preOrder(bt->lchild);preOrder(bt->rchild);}}void inOrder(BiTree bt){//指针形参 if(bt!=NULL){inOrder(bt->lchild);cout<<bt->data<<" ";inOrder(bt->rchild);}}void postOrder(BiTree bt){//指针形参 if(bt!=NULL){postOrder(bt->lchild);postOrder(bt->rchild);cout<<bt->data<<" ";}}

源代码（编程风格参考严蔚敏版《数据结构》）

#include#include#includeusing namespace std;#define MAXSIZE 5#define ElemType char#define Status int//表示状态 #define OK 1#define ERROR 0#define STOP 0#define OVERFLOW 0typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree; Status initial(BiTree *bt){//指针的指针 *bt = (BiTree)malloc(sizeof(BiTNode));(*bt)->lchild = NULL;(*bt)->rchild = NULL;}Status createTree(BiTree *bt){ElemType c;c = getchar();if(c=='#'){*bt = NULL;}else{*bt = (BiTree)malloc(sizeof(BiTNode));(*bt)->data = c;createTree(&(*bt)->lchild);createTree(&(*bt)->rchild);}}void preOrder(BiTree bt){//指针形参 if(bt!=NULL){cout<<bt->data<<" ";preOrder(bt->lchild);preOrder(bt->rchild);}}void inOrder(BiTree bt){//指针形参 if(bt!=NULL){inOrder(bt->lchild);cout<<bt->data<<" ";inOrder(bt->rchild);}}void postOrder(BiTree bt){//指针形参 if(bt!=NULL){postOrder(bt->lchild);postOrder(bt->rchild);cout<<bt->data<<" ";}}int main(){BiTree bt;//指针 initial(&bt);cout<<"先序创建树（输入#停止生成节点）：\n"; createTree(&bt);cout<<"先序遍历：\n"; preOrder(bt);cout<<"\n中序遍历：\n"; inOrder(bt);cout<<"\n后序遍历：\n";postOrder(bt); return 0;} 

敬请批评指正！