一、树
定义
- 树是由根节点和若干颗子树构成的；
- 一棵树中的任意两个结点有且仅有唯一的一条路径连通；
- 一棵树如果有 n 个结点，那么它一定恰好有 n-1 条边；
- 一棵树不包含回路（树是特殊的图，树没有环）。
示例
树，二叉树
二、二叉树
定义
二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。
JAVA实现
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
二叉树的遍历(用递归实现)
前序遍历：根节点-左节点-右节点
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
中序遍历：左节点-根节点-右节点
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.println(root.val);
inOrder(root.right);
}
后序遍历：左节点-右节点-根节点
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
inOrder(root.right);
System.out.println(root.val);
}
三、二叉搜索树
定义
二叉搜索树，又称有序二叉树、排序二叉树，是具有下列性质的二叉树：
- 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
- 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
- 任意结点的左、右子树也分别为二叉搜索树；
根据性质可知，中序遍历二叉搜索树即可得到升序排列的数据。
示例
二叉搜索树
可以在这个网址尝试进行一些二叉搜索树的操作。
四、lintcode上的一些题目
94.二叉树的中序遍历
144. 二叉树的前序遍历
145. 二叉树的后序遍历
这三道题没什么难的，看一下上文二叉树的遍历即可。
589. N 叉树的前序遍历
这道题也很简单，只是简单拓展一下。
429. N 叉树的层序遍历
这道题也很简单，遍历一下就结束啦。
