计算机二级公共基础知识章节知识点：1.6树与二叉树_第2页

二叉树的存储结构

　　二叉树的存储常采用链式存储结构。
　　存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。
　　存储结构如下：
　　
　　即二叉树的存储结构中每一个存储结点都有两个指针域，因此，二叉树的链式存储结构也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。
　　如图所示的二叉树：
　　
　　如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是：
　　
　　当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树.

二叉树的遍历

　　二叉树的遍历即是不重复地访问二叉树的所有结点。
　　在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。
　　1）前序遍历
　　前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。
　　操作的具体方式：
　　若二叉树为空，则结束返回。
　　否则：访问根结点?前序遍历左子树?前序遍历右子树
　　如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O
　　2）中序遍历
　　中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。
　　具体的操作方式：
　　若二叉树为空，则结束返回。
　　否则：中序遍历左子树?访问根结点 ?中序遍历右子树
　　这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。
　　如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O
　　3）后序遍历
　　后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。
　　具体的操作方式：
　　若二叉树为空，则结束返回。
　　否则：前序遍历左子树?前序遍历右子树?访问根结点
　　如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A