树形结构的相关术语
- 结点：树里面的元素
- 父子关系：结点之间相连的边
- 子树：当结点大于1时，其余结点分为的互不相交的集合
- 度：一个结点拥有的子树数量称为结点的度
- 叶子：度为0的结点
- 孩子：结点的子树
- 双亲：子树的根节点
- 兄弟：同一个双亲结点
- 森林：由N个互不相交的树构成深林
- 结点的高度：结点到叶子结点的最长路径
- 结点的深度：根结点到该结点的边的个数
- 结点的层度：结点的深度+1
- 树的高度：根节点的高度
图
二叉树.png
满二叉树：除叶子结点外，其他的结点都有两个子结点
完全二叉树：除去最后一层外，其余层为满二叉树状态，并且最后一层的叶子结点都往左排列
完全二叉树是满二叉树的一个子集
实现方式
- 数组：推导公式，当前结点：i 两个子结点：
i*2i*2+1,适用于满二叉树和完全二叉树 - 链表：left right
树的遍历
- 前序遍历 根（输出） 左 右
- 中序遍历 左 根（输出） 右
- 后序遍历 左 右 根（输出）
根（输出）：表示遇到根节点则输出
代码实现
public class MyTree<E> { public void print(TreeNode<E> treeNode) { System.out.print(treeNode.getData()); } //前序遍历 根 左 右 public void pre(TreeNode<E> treeNode) { print(treeNode); if (treeNode.getLeftNode() != null) pre(treeNode.getLeftNode()); if (treeNode.getRightNode() != null) pre(treeNode.getRightNode()); } //中序遍历 左 根 右 public void mid(TreeNode<E> treeNode) { if (treeNode.getLeftNode() != null) { mid(treeNode.getLeftNode()); } print(treeNode); if (treeNode.getRightNode() != null) mid(treeNode.getRightNode()); } //后序遍历 左 右 根 public void post(TreeNode<E> treeNode) { if (treeNode.getLeftNode() != null) { post(treeNode.getLeftNode()); } if (treeNode.getRightNode() != null) { post(treeNode.getRightNode()); } print(treeNode); } //层序遍历 public void level(TreeNode<E> treeNode) { MyQueue<TreeNode<E>> queue = new MyQueue<>(20); levelRecursion(queue, treeNode); } private void levelRecursion(MyQueue<TreeNode<E>> queue, TreeNode<E> treeNode) { print(treeNode); if (treeNode.getLeftNode() != null) { queue.push(treeNode.getLeftNode()); } if (treeNode.getRightNode() != null) { queue.push(treeNode.getRightNode()); } while (!queue.isEmpty()) { levelRecursion(queue, queue.pop()); } } }
