二叉树的遍历和查找
2011 年 10 月 26 日
前序遍历
若二叉树非空,则执行以下操作:
- 访问根结点;
- 先序遍历左子树;
- 先序遍历右子树
中序遍历
若二叉树非空,则执行以下操作:
- 中序遍历左子树;
- 访问根结点;
- 中序遍历右子树。
后序遍历
若二叉树非空,则执行以下操作:
- 后序遍历左子树;
- 后序遍历右子树;
- 访问根结点
实例说明
graph TD
3–>1
3–>5
1–>2
5–>4
5–>6
对于上面的二叉树而言,
- 前序遍历结果: 3 1 2 5 4 6
- 中序遍历结果: 1 2 3 4 5 6
- 后序遍历结果: 2 1 4 6 5 3
树的遍历代码实现
定义一个树结构
@ToString class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
定义一个遍历方式的枚举
/** * 遍历的方向. */ enum Direct { /** * 中序 */ middle, /** * 前序 */ before, /** * 后序 */ after; }
实现代码
/** * 遍历. */ public void print(Direct direct) { StringBuffer stringBuffer = new StringBuffer(); print(stringBuffer, this, direct, "ROOT:"); System.out.println(stringBuffer.toString()); } private void print(StringBuffer stringBuffer, TreeNode treeNode, Direct direct, String node) { if (treeNode != null) { if (direct == Direct.before) { stringBuffer.append(node + treeNode.val + "\n"); print(stringBuffer, treeNode.left, direct, "L:"); print(stringBuffer, treeNode.right, direct, "R:"); } else if (direct == Direct.middle) { print(stringBuffer, treeNode.left, direct, "L:"); stringBuffer.append(node + treeNode.val + "\n"); print(stringBuffer, treeNode.right, direct, "R:"); } else { print(stringBuffer, treeNode.left, direct, "L:"); print(stringBuffer, treeNode.right, direct, "R:"); stringBuffer.append(node + treeNode.val + "\n"); } } }
二叉查询树实现了二分查找法
时间复杂度是Olog(n)到O(n),也就是说它最好的情况是Olog(n),当然运气不好,也就是你查询的是叶子节点,那就是O(n)了。
/* * 二分查找,最优时间复杂度OLog(n). */ private TreeNode search(TreeNode x, int key) { if (x == null) return x; int cmp = key - x.val; if (cmp 0) return search(x.right, key); else return x; } public TreeNode search(int key) { return search(this, key); } }
对于树的知识还有很多,本文章主要介绍树的遍历和查找!