遍历
2018-07-19 本文已影响230人
菁华浮英梦
一、树
遍历是指对树中所有结点信息的访问，即依次对树中每个结点访问依次且仅访问一次。
1.前序遍历
也叫先根遍历，按照先根后子的顺序遍历，字节点从左到右的顺序递归遍历。
2.后序遍历
也叫后根遍历，字节点从左到右的顺序递归遍历，最后访问根，递归遍历。
3.层次遍历
从上到下，从左到右的顺序遍历。
注意：二叉树才有中序遍历！
二、二叉树
①二叉树结点最大度为2，而树不限制结点的度。
②二叉树的结点的子树要区分左子树和右子树。
二叉树性质
二叉树第i层上的结点数目最多为2的i-1次方（i>=2）
深度为k的二叉树至多有2的k次方-1个结点（k>=1）
在任意一棵二叉树中，若终端结点树为n0，度为2的结点树为n2，则n0=n2+1
具有n个结点的完全二叉树的深度为log2n的下限+1
二叉树遍历：
①前序遍历
②中序遍历
先访问左子树，再访问根，最后访问右子树
③后序遍历
