「二叉树遍历」二叉树的三种遍历

二叉树遍历

二叉树是n(n≥0)个节点的有限集合，它或者是空树(n=0),或者是有一个根节点及两颗不相交的且分别称为左、右子树的二叉树所组成。可见，二叉树同样具有递归性质。

特别需要注意的是，尽管树和二叉树的概念之间有许多联系，但它们是两个不同的概念，树和二叉树之间最主要的区别是：二叉树结点的子树要区分左子树和右子树，即使在节点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。另外，二叉树结点最大度为2，二树中不限制节点的度数。

（1）二叉树第i层（i≥1）上至多有 $2^{i-1}$ 个节点

（2）高度为k的二叉树之多有 $2^{k}-1$ 个节点（k≥1）

（3）对于任一颗二叉树，若其终端的节点数为 $n_{0}$ ,度为2的节点数为 $n_{2}$ ，则 $n_{0}=n_{2}+1$

（4）具有n个节点的完全二叉树的深度为 $[\log_{2^{n}}]+1$

1）二叉树的顺序存储结构

用一组地址连续的存储单元存储二叉树中的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置能反映出节点之间的逻辑关系。

2）二叉树的链式存储结构

由于二叉树的节点中包含有数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点。

遍历二叉树的方法分别有先序遍历、中序遍历、后序遍历。

先序遍历：先遍历根节点，然后是左子树，最后是右子树；根节点->左子树->右子树

中序遍历：先遍历左子树，然后是根节点、最后是右子树；左子树->根节点->右子树

后序遍历：先遍历左子树，然后是右子树，最后是根节点；左子树->右子树->根节点

B C

D E

F G

先序遍历：ABDFEGC

中序遍历：DFBGEAC

后序遍历：FDGEBCA