数据结构-二叉树的遍历

数据结构-----二叉树的遍历

数据结构学完有好长时间了。渐渐忘记了很多，在此机会以做笔记的形式将其复习一般，同时熟悉敲点代码熟悉VIM。

一，基本概念

1，二叉树是节点的有限集合，该集合或者为空（而树不允许为空）或者是由一个根和两棵互不相交的、称为该根的左子树和右子树组成。

2，几种特殊的二叉树

满二叉树：高度为h的二叉树敲好有2h -1个结点时称为满二叉树

完全二叉树：一个二叉树中，只有最下面两层结点的度（一个结点拥有的子树）小于2，并且最下一层的叶结点集中靠在左侧的若干位置上

扩充二叉树：也称2-树，扩充二叉树除叶子结点外，其余结点都必须有两个孩子。

如下图所示，显示集中特殊的二叉树。

二，二叉树的存储

1）完全二叉树可以采用顺序存储。

2）一般二叉树采用链式存储

lchilddatarchildlchild和rchild分别为指向左右孩子的指针，data为数据域。

三，二叉树的遍历

统称分为深度遍历和广度遍历，深度遍历即：先序、中序、后续。而广度即按层次遍历

先序：若二叉树为空，则空操作，否则先访问根节点，再遍历先序左子树，最后先序右子树

中序：若二叉树为空，则空操作，否则先中序遍历左子树，再先访问根节点，最后中序遍历右子树

后序：若二叉树为空，则空操作，否则先后序遍历左子树，再后序遍历右子树，最后访问根结点

四、程序的具体实现