二叉树的遍历
既然想要明白二叉树的遍历，那我们是不是要首先明白什么是二叉树呀？【手动狗头】
1.认识我们的二叉树兄弟
至于中间这多了一条腿的家伙，我打保票他肯定不是二叉树！！！【手动狗头】
听到二叉，那肯定是一个结点只有两个分支呀
那对于我们的二叉树我们又是怎么来储存，找相似结构！找相似结构！找相似结构！（重要的话说三遍）
有些小伙伴看不出，好家伙，这样呢！
因为2，4结点后面不是没有，那么就是空，于是我们不上NULL（空）是不是出来了，这样每一个结点都可以看作是
那我们之前的图是不是这样子的啦！！！
我们用结构体来表示
我们设立一个值来储存他结点的数值，用两个指针来指向下一个结点
typedef struct Tree{ int data; // 存放数据域 struct Tree *lchild; // 遍历左子树指针 struct Tree *rchild; // 遍历右子树指针 }Tree,*BitTree;
2.二叉树兄弟的存放
我们扩展和链接一下我们前面的知识，说到结构体，指针，NULL，无限月读（不断存储），首先想到什么？我们的链表好兄弟呀！当然当你学完这篇之后，我们还可以想到我们的二叉树兄弟啦【手动狗头】
回忆一下我们的链表，嗯~
是不是沿着一条边，一直存放下去，直到遇到了特定条件,为空时停止。那么在这里我们一样的，他还是我们用链表来存储储存的，别忘了我们的大杀器
递归！！！
BitTree CreateLink() { int data; int temp; BitTree T; scanf("%d",&data); // 输入数据 if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建 return NULL; }else{ T = (BitTree)malloc(sizeof(Tree)); // T->data = data; // 把当前输入的数据存入当前节点指针的数据域中 printf("请输入%d的左子树: ",data); T->lchild = CreateLink(); // 开始递归创建左子树 printf("请输入%d的右子树: ",data); T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树 return T; // 返回根节点 } }
他的基本逻辑是这样！
我们创建一个根结点，为我们的根结点赋值
我们有了一个1结点
然后T->lchild = CreateLink()我们链接我们的左结点，并回到我们一开始的时候，给我们的左节点赋值，有点类似于new，但是我们也别忘记了还有个T->rchild = CreateLink();
这一步的图解
好的，我们然后问你2结点的左节点了，重复上面的步骤
我们得到了
然后我们就可以，开始结束我们4号结点的赋值，当在此跳转到原来程序，询问你4号结点的左子树为多少时，我们输出-1，那么他的左节点为空，又不会执行我们的else，我们就会开始执行我们的右结点，问你4号结点的右子树为多少，我们输入-1；这个时候，我们开始来还我们前面的债务啦
先是
我们给2的右结点赋值为5，然后再次，问你5的左右结点是多少，和上面的方案是一样的，我们再次输入-1，这时就会开始给你的第一块红的开始赋值了，这是我最后的赋值结果
做到这一步的你超级棒啦，我们马上就OK啦！！！
我们开始遍历吧！！！
遍历的先序，中序，后序，先 中 后 指的是根的位置
1.先序（根 左 右）
先序我们掌握最基本的就好啦，就像这样（中序，后序也是可以的）
我们先序的结果是： 1（根）2（左）3（右）
为什么这没说呢？我们看这个长一点的图
我们先看个左边的小的
先序是不是2 4 5！
我们先看个右边的小的
是不是 3 6 7！
好的我们来看大的！合起来！
先序是：1（根） 245（左） 367（右）
看看代码吧！
// 先序遍历 void ShowXianXu(BitTree T) // 先序遍历二叉树 { if(T==NULL) // 递归中遇到NULL，返回上一层节点 { return; } printf("%d ",T->data); ShowXianXu(T->lchild); // 递归遍历左子树 ShowXianXu(T->rchild); // 递归遍历右子树 }
我们用的也是递归思想，我们不断地去通过ShowXianXu(T->lchild)指向下一级，同时还会预先留下ShowXianXu(T->rchild)，来为我们实现左边的遍历，if用来判断是不是到达空结点 注意：T每一次的值都是不一样的喔！
你其实可以把这些看作：
根：printf("%d ",T->data);
左：ShowXianXu(T->lchild);
右：ShowXianXu(T->rchild);
2.中序 （左 根 右）
打好基本走遍天下都不怕！
中序是：2（左） 1（根） 3（右）
看看代码吧！
// 中序遍历 void ShowZhongXu(BitTree T) // 先序遍历二叉树 { if(T==NULL) // 递归中遇到NULL，返回上一层节点 { return; } ShowZhongXu(T->lchild); // 递归遍历左子树 printf("%d ",T->data); ShowZhongXu(T->rchild); // 递归遍历右子树 }
一样的一样的
你其实可以把这些看作：
左：ShowZhongXu(T->lchild);
根：printf("%d ",T->data);
右：ShowZhongXu(T->rchild);
3.后序 （左 右 根）
后序是：2（左） 3（右） 1（根）
代码：
// 后序遍历 void ShowHouXu(BitTree T) // 后序遍历二叉树 { if(T==NULL) // 递归中遇到NULL，返回上一层节点 { return; } ShowHouXu(T->lchild); // 递归遍历左子树 ShowHouXu(T->rchild); // 递归遍历右子树 printf("%d ",T->data); }
又是一样的一样的
你其实可以把这些看作：
左：ShowHouXu(T->lchild);
右：ShowHouXu(T->rchild);
根：printf("%d ",T->data);
over！！！
整体代码
#include<stdio.h> #include<stdlib.h> typedef struct Tree{ int data; // 存放数据域 struct Tree *lchild; // 遍历左子树指针 struct Tree *rchild; // 遍历右子树指针 }Tree,*BitTree; BitTree CreateLink() { int data; int temp; BitTree T; scanf("%d",&data); // 输入数据 if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建 return NULL; }else{ T = (BitTree)malloc(sizeof(Tree)); // T->data = data; // 把当前输入的数据存入当前节点指针的数据域中 printf("请输入%d的左子树: ",data); T->lchild = CreateLink(); // 开始递归创建左子树 printf("请输入%d的右子树: ",data); T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树 return T; // 返回根节点 } } // 先序遍历 void ShowXianXu(BitTree T) // 先序遍历二叉树 { if(T==NULL) // 递归中遇到NULL，返回上一层节点 { return; } printf("%d ",T->data); ShowXianXu(T->lchild); // 递归遍历左子树 ShowXianXu(T->rchild); // 递归遍历右子树 } // 中序遍历 void ShowZhongXu(BitTree T) // 先序遍历二叉树 { if(T==NULL) // 递归中遇到NULL，返回上一层节点 { return; } ShowZhongXu(T->lchild); // 递归遍历左子树 printf("%d ",T->data); ShowZhongXu(T->rchild); // 递归遍历右子树 } // 后序遍历 void ShowHouXu(BitTree T) // 后序遍历二叉树 { if(T==NULL) // 递归中遇到NULL，返回上一层节点 { return; } ShowHouXu(T->lchild); // 递归遍历左子树 ShowHouXu(T->rchild); // 递归遍历右子树 printf("%d ",T->data); } int main() { BitTree S; printf("请输入第一个节点的数据:\n"); S = CreateLink(); // 接受创建二叉树完成的根节点 printf("先序遍历结果: \n"); ShowXianXu(S); // 先序遍历二叉树 printf("\n中序遍历结果: \n"); ShowZhongXu(S); // 中序遍历二叉树 printf("\n后序遍历结果: \n"); ShowHouXu(S); // 后序遍历二叉树 return 0; }
