本文共 6596 字，大约阅读时间需要 21 分钟。
一、树
1、什么是树
什么是树结构？从形状来看，树结构是现实中的树倒立得到的结构。现实生活中有很多这种结构，如，一个家族的家谱、一个机构的组织架构。
从定义来说，树是一些节点的集合，这个集合要么是空集，要么是一个根节点加上n个非空子树（n≥0），这是递归的定义方式。
这个节点包含数据域、指向n个子树的n条边。如下面所示，树T是根节点T+4个子树，同样，4个子树也分别可以看成类似的方式。
2、树的相关概念
（1）树节点之间的关系
叶节点：没有子节点的节点
根节点：没有父节点的节点，一棵树只有一个。如果单独看树的各个子树的话，每个子树也有一个根节点（只要不是空树）。
兄弟节点：有相同的父节点的节点互为兄弟节点
堂兄弟节点：父节点是兄弟节点的节点互为堂兄弟
（2）路径
节点n1到节点nk的路径：是一个包括n1和nk序列。如上图节点A到节点D的路径为：A，B，D （A、D包括在序列里面）
路径的长：是该路径边的个数（路径节点个数-1）。如路径A，B，D的长为3 - 1 = 2
（3）节点的高度、深度、层 以及 树的高度、深度
节点的深度：根到该节点的路径的长。注意：这条路径是唯一的。
节点的高度：该节点到它可到达的叶子节点的所有路径的长的最大值。注意：由于从一个节点可到达的叶子节点可能不只一个，所以路径不只一条，因此要取最大值。
节点的层数：层数与深度类似，只不过起点是1。层是一个集合，某一层包含多个节点。
关于深度、高度，可以用生活的概念来理解。在生活中，说到高度，就是从下往上度量的，起点都是地面。树中的高度也是一样，从最底层开始计数，并且计数的起点是0。
而生活中说到深度，是从上往下去度量的，比如水深多少米，起点是水平面。树中的深度也是一样，以根节点为“水平面”，计数起点也是1。
树中的2种特殊结点：叶节点的高度为0；根节点的深度为0
树的高度：是根节点的高度，上面的树的高度为3
树的深度：是树最深的叶节点的深度，上面的树的深度为3。树的深度总等于树的高度
二、二叉树
1、二叉树的定义
二叉树：每个节点最多有2个“分叉”的树，即每个节点最多只能有2个子节点
2、一些特殊的二叉树
（1）5种形态
（2）完全二叉树 和 满二叉树
完全二叉树：叶节点在最下面2层，最后一层的叶节点都靠左排列，并且除了最后一层，其它层的节点个数都要达到最大。
满二叉树：叶节点都在最底层，除了叶节点之外，每个节点都有2个子节点。换句话说，满二叉树没有子节点个数为1的节点。
3、二叉树的两种存储（表示）方式
（1）链式存储
如下图所示，我们用3个字段来表示一个节点。一个存储数据，另外2个存储指向左右子节点的地址。
大部分二叉树都是通过这种结构来实现的。通过这种方式，只要我们知道根节点，就可以通过其指向左右子节点的两个地址域，将整棵树串起来。
（2）顺序存储
如下图所示，我们把树存到一个数组中，利用数组下标来表示节点之间的关系（父节点、子节点）。我们把根节点存储在下标为 i =1的位置，根节点的左子节点存储在下标为2 * i = 2的位置，根节点的右子节点存储在下标为2 * i + 1=3的位置。以此类推。
我们可以看到，如果节点X存储在数组中下标为 i 的位置，那么下标为2 * i 的位置就是它的左子节点，下标为2 * i + 1的位置就是它的右子节点；反过来，下标为 i / 2的位置就是它的父节点。通过这种方式，我们可以通过下标计算，把整棵树都串起来。
顺序存储一般针对完全二叉树或者比较接近完全二叉树的二叉树，这也就是为什么要单独提出完全二叉树这个概念的原因，也是为什么在定义完全二叉树时，要强调最后一层的叶节点靠左排列。
三、二叉搜索树的实现
由于使用数组表示二叉树的话，为了不浪费空间，数组只适合表示完全二叉树、满二叉树或者与它们非常接近的树。正因为顺序结构有着这样的局限性，所以我实现二叉树时只用链式结构。
1、基本实现
class TreeNode { public TreeNode left; //左引用域 public TreeNode right; //右引用域 public int data; //数据域 //结点的三种构造方式 public TreeNode() { } public TreeNode(int data, TreeNode left, TreeNode right) { this.data = data; this.left = left; this.right = right; } public TreeNode(int data) { this.data = data; this.left = null; this.right = null; } //插入结点（并保持二叉搜索树的结构） public static TreeNode insert(TreeNode root, int data) { if (root == null) { root = new TreeNode(data); } else if (data <= root.data) { root.left = insert(root.left, data); } else { root.right = insert(root.right, data); } return root; } //判断是否存在值为给定值的结点 public static boolean find(TreeNode root, int data) { if(root == null) { // 出口1 return false; } else if (root.data == data) { // 出口2 return true; } else if (root.data < data) { return find(root.right, data); } else { return find(root.left, data); } } //查找树中值最小的结点，并返回其值 public static int findMin(TreeNode root) { if (root == null) { System.out.println("这是一个空树"); return -10000; } while (root.left != null) { root = root.left; } return root.data; } //查找树中值最大的结点，并返回其值 public static int findMax(TreeNode root) { if (root == null) { System.out.println("这是一个空树"); return -10000; } while (root.right != null) { root = root.right; } return root.data; } //中序遍历树 public static void inOrder(TreeNode root) { if (root == null) { return; } inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } //后序遍历树 public static void postOrder(TreeNode root) { if (root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.data+" "); } //先序遍历树 public static void preOrder(TreeNode root) { if (root == null) { return; } System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); }}public class TreeTest { public static void main(String[] args) {//插入结点，构造一棵树// 5// / \// 3 10// / \ \// 1 4 11 TreeNode root = null; root = TreeNode.insert(root, 5); root = TreeNode.insert(root, 10); root = TreeNode.insert(root, 3); root = TreeNode.insert(root, 4); root = TreeNode.insert(root, 1); root = TreeNode.insert(root, 11); TreeNode.inOrder(root); //中序遍历 System.out.println("\n======================================"); TreeNode.postOrder(root); //后序遍历 System.out.println("\n======================================"); TreeNode.preOrder(root); // 先序遍历 System.out.println(); System.out.println(); System.out.println(TreeNode.find(root, 11)); //查看是否有值为11的结点 System.out.println(TreeNode.find(root, 100));//查看是否有值为100的结点 System.out.println(TreeNode.findMin(root)+" "+TreeNode.findMax(root));//打印最大值、最小值 }} 初步测试结果如下图所示，说明各个方法都实现了我们想要的效果。
再测试如果是特殊的树，该类是否还可以正常使用。
public class TreeTest { public static void main(String[] args) { //构造三棵树 //第一棵树// 5// / // 3 // / // 1 //第二棵树// 5// \// 10// \// 11 //第三棵树：空树 TreeNode root1 = null; root1 = TreeNode.insert(root1, 5); root1 = TreeNode.insert(root1, 3); root1 = TreeNode.insert(root1, 1); TreeNode root2 = null; root2 = TreeNode.insert(root2, 5); root2 = TreeNode.insert(root2, 10); root2 = TreeNode.insert(root2, 11); TreeNode root3 = null; System.out.print("中序遍历： "); TreeNode.inOrder(root1); //中序遍历 System.out.print("后序遍历： "); TreeNode.postOrder(root1); //后序遍历 System.out.print("先序遍历： "); TreeNode.preOrder(root1); // 先序遍历 System.out.println(); System.out.println(TreeNode.find(root1, 5)); //查看是否有值为5的结点 System.out.println(TreeNode.find(root1, 100));//查看是否有值为100的结点 System.out.println(TreeNode.findMin(root1)+" "+TreeNode.findMax(root1));//打印最大值、最小值 System.out.println("\n======================================"); System.out.print("中序遍历： "); TreeNode.inOrder(root2); //中序遍历 System.out.print("后序遍历： "); TreeNode.postOrder(root2); //后序遍历 System.out.print("先序遍历： "); TreeNode.preOrder(root2); // 先序遍历 System.out.println(); System.out.println(TreeNode.find(root2, 5)); //查看是否有值为5的结点 System.out.println(TreeNode.find(root2, 100));//查看是否有值为100的结点 System.out.println(TreeNode.findMin(root2)+" "+TreeNode.findMax(root2));//打印最大值、最小值 System.out.println("\n======================================"); System.out.print("先序遍历： "); TreeNode.preOrder(root3); // 先序遍历 System.out.println(); System.out.println(TreeNode.find(root3, 5)); //查看是否有值为5的结点 System.out.println(TreeNode.findMin(root3)+" "+TreeNode.findMax(root3));//打印最大值、最小值 }} 其结果如下所示，输出正常。
2、功能完善
四、（链式存储的）二叉树的递归和非递归遍历
二叉树的遍历是实现其他几乎所有操作的前提，所以理解好遍历至关重要。由前面的讲解可以知道，链式存储的二叉树，每个节点可以通过它的2个地址域找到它的子节点。但，问题在于子节点却不能反过来找到它的父节点，而且，根节点每一次有2条路可以选择，这就造成了选择一条路之后，就不能从子节点回到根节点来选择第二条路。所以，第二条路上面的结点也就不能遍历到。
关于这个问题，有一些解决方案，比如，既然是因为子节点找不到它的父节点，那就在表示一个节点时多加一个地址域指向它的父节点（根节点的第三个地址域指向null），这是一种思路，不过，我们通常讲的前序、中序、后序遍历采用的还是最普通的2个地址域的存储结构。接下来我描述一下这些遍历的底层机制。
1、前序遍历
（1）递归实现
（2）非递归实现
2、中序遍历
（1）递归实现
（2）非递归实现
3、后序遍历
（1）递归实现
（2）非递归实现
4、层序遍历
转载地址：http://vbnii.baihongyu.com/