二叉树的概念及结构
每个结点最多有两颗子树，即二叉树不存在度大于2的结点。
任何一颗二叉树可以看成三个部分：①根节点②左子树③右子树
遍历的三种方法
以下面的二叉树为例介绍遍历的方法。
先序遍历（前序）
先序遍历的方法是：“根左右”依次遍历，即先访问根结点，再访问左子树，再访问右子树。
以上面的二叉树为例，肯定要先访问根结点A，然后访问左子树，但A的左子树是以B为根结点的一颗子树，如下图。
那么在这颗子树里我们又要根据“根左右”进行遍历，先访问根结点B，然后左子树D，但在这我想让你思考D还有没有子树？看样子是没有，不过严格意义我们可以写上NULL（空），然后就是B的右子树，结点E。
到此为止A的左子树已经访问完了，可以写A B D NULL NULL E NULL NULL，有时候题目不要求我们写空的话，可以直接写ABDE（接下来为了方便大家看我就不写NULL了）。
然后再访问A的右子树C。
先序遍历完成，顺序为：ABDEC
中序遍历
中序遍历的方法是：“左根右”依次遍历，即先访问左子树，再访问根结点，再访问右子树。
以上面二叉树为例，先看A有无左子树，有！是根结点为B的子树！ 再看B有无左子树，有！是结点D。
D还有左子树吗？没有，是NULL（空，我们这里暂且不算）那就先访问D，然后D作为B的左子树，接下来就该访问根结点B。
接着访问B的右子树E，E有左子树吗？没有。现在我们看到A的所有左子树已经遍历完了，接着就是访问根结点A。
到此为止的顺序为：DBEA
然后再访问A的右结点C。
所以中序遍历的顺序为：DBEAC
可以自己试着把空（NULL）也给算上写出中序遍历：
NULL D NULL B NULL E NULL A NULL C NULL
后序遍历
后序遍历的方法是：“左右根”依次遍历，即先访问左子树，再访问右子树，再访问根结点。
以上面二叉树为例，先看A有无左子树，有！是根结点为B的子树！ 再看B有无左子树，有！是结点D。D无子树了，再看B是否有右子树，有！是结点E。
好的那就先访问D和E，然后再访问B，接着就是A的右子树。然后A的右子树只有一个C，最后再访问A，访问完毕。
后序遍历的顺序为：DEBCA
遍历例题
写出下面二叉树的三种遍历结果
严格上可以写NULL，读者可以自己加以理解，大多数情况会忽略NULL。
前序遍历：A BNULL D FNULL NULL NULLC E NULL NULL NULL
中序遍历：B F D A E C
后序遍历：F D B E C A
三种遍历方法的代码实现
结构体的定义
typedefcharBTDataType; typedefstructBinaryTreeNode{ structBinaryTreeNode*left; //左孩子structBinaryTreeNode*right; //右孩子BTDataTypedata; }BTNode;
解释：
①typedef char BTDataType; 是将char字符类型重新命名为BTDataType，目的是为了方便代码的可维护性，比如我后面发现char不是我想要的类型了，但我已经打了好几个char了，就不方便更改了。而用此方法，只需要把typedef char BTDataType里的char改成int就行。
②下面是结构体的定义
前序遍历代码实现
voidPrevOrder(BTNode*root) //前序遍历{ if (root==NULL) //空树return; printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right); }
这里就是先打印根结点，毕竟这是前序遍历，然后就访问左子树，即root->left。
如果遍历的时候想严格打印NULL那么就这样写.
voidPrevOrder(BTNode*root) //前序遍历{ if (root==NULL) //空树 { printf("NULL "); return; } printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right); }
中序遍历代码实现
voidInOrder(BTNode*root) //中序遍历{ if (root==NULL) //空树return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right); }
后序遍历代码实现
voidPostOrder(BTNode*root) //后序遍历{ if (root==NULL) //空树return; PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); }
所有函数和main函数
typedefcharBTDataType; typedefstructBinaryTreeNode{ structBinaryTreeNode*left; //左孩子structBinaryTreeNode*right; //右孩子BTDataTypedata; }BTNode; voidPrevOrder(BTNode*root) //前序遍历{ if (root==NULL) //空树return; printf("%c ", root->data); PrevOrder(root->left); PrevOrder(root->right); } voidInOrder(BTNode*root) //中序遍历{ if (root==NULL) //空树return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } voidPostOrder(BTNode*root) //后序遍历{ if (root==NULL) //空树return; PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); } intmain() { BTNode*A= (BTNode*)malloc(sizeof(BTNode)); A->data='A'; A->left=NULL; A->right=NULL; BTNode*B= (BTNode*)malloc(sizeof(BTNode)); B->data='B'; B->left=NULL; B->right=NULL; BTNode*C= (BTNode*)malloc(sizeof(BTNode)); C->data='C'; C->left=NULL; C->right=NULL; BTNode*D= (BTNode*)malloc(sizeof(BTNode)); D->data='D'; D->left=NULL; D->right=NULL; BTNode*E= (BTNode*)malloc(sizeof(BTNode)); E->data='E'; E->left=NULL; E->right=NULL; A->left=B; A->right=C; B->left=D; B->right=E; PrevOrder(A); printf("\n"); InOrder(A); printf("\n"); PostOrder(A); printf("\n"); printf(""); return0; }
这里还是以最上面的二叉树为例。
主函数里我使用了动态内存开辟，使用一次就开一次，不要浪费内存。
