# 二叉树的遍历和查找

1. 访问根结点；
2. 先序遍历左子树；
3. 先序遍历右子树

1. 中序遍历左子树；
2. 访问根结点；
3. 中序遍历右子树。

### 后序遍历

1. 后序遍历左子树；
2. 后序遍历右子树；
3. 访问根结点

#### 实例说明

graph TD
3–>1
3–>5
1–>2
5–>4
5–>6

1. 前序遍历结果： 3 1 2 5 4 6
2. 中序遍历结果： 1 2 3 4 5 6
3. 后序遍历结果： 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).
*/
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);
}
}