二叉树遍历（图解）

二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系。—–>一般只用于完全二叉树
链式存储—–>二叉链表
定义： lchild | data | rchild（两个指针域，一个数据域）typedef struct Node { ElemType data; struct Node *lchild, *rchild;}BiTnode,* BiTree;注意点：
1）已知 前序遍历序列 和 中序遍历序列，可以唯一确定一颗二叉树
2）已知 中序遍历序列和 后序遍历序列，可以唯一确定一颗二叉树
而已知前序和后序是不能确定一颗二叉树的二叉树的遍历：是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。1、前序遍历：根-左-右
代码：

void PreOrder（BiTree T） /*先序遍历: 根-左-右*/{if（T ！= NULL）{Visit（T）; /*访问根节点*/PreOrder（T->lchild）;/*访问左子节点*/PreOrder（T->rchild）;/*访问右子节点*/}}

2、中序遍历：左-根-右
代码：

void InOrder（BiTree T）/*中序遍历：左-根-右*/{if（T ！= NULL）{InOrder（T->lchild）;//左Visit（T）;//根InOrder（T->rchild）;//右}}

3、后序遍历：左-右-根
代码：

void PostOrder（BiTree T）/*后序遍历：左-右-根*/{if（T ！= NULL）{PostOrder（T->lchild）;//左PostOrder（T->rchild）;//右Visit（T）;//根}}

4、层序遍历：从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直到节点访问完毕
代码：该程序用到了队列的思想，可以参考下图理解
（该图为展示的是 图的广度优先遍历示意图，应用的就是层序遍历的思想）

/*层序遍历 思路：按从左至右的顺序来逐层访问每个节点，层序遍历的过程需要队列*/void LevelOrder（BiTree T）{BiTree p = T;queue<BiTree> queue; /*队列*/queue.push（p）; /*根节点入队*/while（！queue.empty（））/*队列不空循环 */{p = queue.front（）; /*对头元素出队*///printf（"%c ",p->data）; /*访问p指向的结点*/cout << p->data << " ";queue.pop（）; /*退出队列*/if（p->lchild ！= NULL）{ /*左子树不空，将左子树入队*/queue.push（p->lchild）;}if（p->rchild ！= NULL）{ /*右子树不空，将右子树入队*/queue.push（p->rchild）;}}}

二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm 本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-07/119765.htm