二叉树 深度优先与广度优先

image

对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序

为：ABDECFG。怎么实现这个顺序呢 ？深度优先搜索二叉树是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，

现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。

广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.

可以利用队列实现广度优先搜索。

二叉树深度的性质：

1、在非空二叉树中，第i层的结点总数不超过2^(i-1) , i>=1；

2、深度为h的二叉树最多有2^h -1个结点(h>=1)，最少有h个结点；

3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

4、具有n个结点的完全二叉树的深度为(㏒ n) +1;

5、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I>1，则其父结点的编号为I/2；

如果2I<=N，则其左孩子（即左子树的根结点）的编号为2I；若2*I>N，则无左孩子；

参考资料：百度百科—二叉树