1.什么是数？
- 树这种数据结构在计算机中是非常重要的，是一种非线性数据结构。一些数据库的底层与快速索引都离不开树这种数据结构。
- 树是有很多节点组成的具有一定层次关系的集合。最上面的可以看成是树的头，下面的很多节点就在这个头的基础上不断的向下延伸，类似一颗倒挂的树。
- 树是由n>=0个结点的有限集，当n=0的时候，这个树被叫做空树.
当n>1的时候，表明它是一颗非空的树，在一颗非空的树里面。
- 树的特点
- 在每一个节点会有0个或者0个以上的子节点
- 没有父节点的节点被称为根节点
- 非根节点只有一个父节点
- 每个节点的子节点整体上来看像一颗倒挂的树，也被称为父节点子树。
- 树的专业术语
- 节点：是指数据元素和指向子树的分支
- 根节点：在非空树中没有前驱结点的结点，被称为根节点（注意，只有一个根节点）
- 节点的度：结点所拥有子树个数
- 树的度：树里的各个节点度的最大值
- 父节点：A是B的父节点
- 子节点：B是A的子节点
- 叶子节点：当度等于0的时候被称为叶子节点。
- 路径：从根节点找该节点的路径，比如要找K节点。路径为：A->C->G->K
- 层：同一个层面为一层。如A为1层，BC为2层
2.二叉树基本概念
- 什么是二叉树
- 树有很多种，但是每一个结点最多只有两个子节点的树，被称作为二叉树。
- 二叉树的子节点又分成左节点与右节点
- 二叉树又分为满二叉树与完全二叉树
- 满二叉树
- 概念为：如果这颗二叉树的所有叶子节点都在该树的最后一层的话，并且节点的总数=2^n-1（n为层数）。
- 节点总数=2^4-1=15
完全二叉树
- 概念：当前二叉树所有的叶子节点再倒数第一层或者是倒数第二层当中，而且的话最后一层的叶子节点是在左边连续的，而在倒数第二层的叶子节点是右边连续的。
- 如果把G节点删除的话，它就不属于完全二叉树了，因为它的叶子结点已经是不连续了。
- 二叉排序树
- 概念：也叫作二叉查找树。二叉排序树的任何一个非叶子节点，都要求他的左子节点的值要比当前的节点值小，右子节点值要比当前的节点值大。
- 排序树的左子树不为空，那么左子树的所有节点都小于他根节点的值
- 他的右子树不为空，那么右子树的所有节点的值都大于它根节点的值
3.二叉树的前中后续遍历
- 二叉树的遍历
- 在学数组的时候，需要查找某一个值的时候，是不是需要遍历数据来查找的。
- 那在树结构查找某一个值的时候，它与线性结构不一样，没有办法从头开始遍历，那它是如何进行遍历的呢？
我们可以把上图的树分成根节点、左子树和右子树。再根据根节点什么时候被访问，我们就把二叉树遍历分成三种方式
- 前序遍历：首先访问根节点，然后先是访问左子树，最后才到右子树。
- 6 4 2 1 3 5 9 8 11
- 中序遍历：首先访问左子树，然后到根节点，最后才到右子树。
- 1 2 3 4 5 6 8 9 11
- 后序遍历：首先访问左子树，然后到右子树，最后到根节点。
- 1 3 2 6 4 8 11 9 6
4.排序二叉树实战
public class BinaryTree { //创建根节点 public Node root; /** * 查看二叉树 * @return */ public Node getRoot(){ return root; } /** * 求二叉树的最大深度 * @param root * @return */ public int maxDep(Node root){ //根节点是否为空 if(root == null) return 0; return Math.max(maxDep(root.left),maxDep(root.right))+1; } /** * 查找二叉树节点 * @param id * @return */ public String get(Node root,int id){ //判断根节点是否为null if(root == null){ return ""; } //判断传入的ID是否是小于根节点 if(id < root.id){ return get(root.left,id); } //判断传入的ID是否大于根节点 if(id > root.id){ return get(root.right,id); } return root.name; } /** * 二叉树添加节点 * @param node */ public void add(Node node){ //先判断根是否为null if(root == null){ root = node; }else{ root.add(node); } } /** * 前序遍历 */ public void preTraversal(){ getRoot().preTraversal(); } /** * 中序遍历 */ public void infixTraversal(){ getRoot().infixTraversal(); } /** * 后续遍历 */ public void postTraversal(){ getRoot().postTraversal(); } static class Node{ //定义ID private int id; //定义name private String name; //定义左节点 private Node left; //定义右节点 private Node right; //初始化节点的值 public Node(int id,String name){ this.id = id; this.name = name; } /** * 添加节点 * @param node */ public void add(Node node){ //首先先判断node是否为null if(node == null){ return; } //判断是否比根小,向左插入 if(node.id<this.id){ if(this.left == null){ this.left = node; }else{ this.left.add(node); } } //判断是否比根大，向右插入 if(node.id>this.id){ if(this.right == null){ this.right = node; }else{ this.right.add(node); } } } /** * 前序遍历 */ public void preTraversal(){ //输出根节点 System.out.println("id:"+this.id+",name:"+this.name); //输出左节点 if(this.left!=null){ this.left.preTraversal(); } //输出右节点 if(this.right!=null){ this.right.preTraversal(); } } /** * 中序遍历 */ public void infixTraversal(){ //输出左节点 if(this.left!=null){ this.left.infixTraversal(); } //输出根节点 System.out.println("id:"+this.id+",name:"+this.name); //输出右节点 if(this.right!=null){ this.right.infixTraversal(); } } /** * 后续遍历 */ public void postTraversal(){ //输出左节点 if(this.left!=null){ this.left.postTraversal(); } //输出右节点 if(this.right!=null){ this.right.postTraversal(); } //输出根节点 System.out.println("id:"+this.id+",name:"+this.name); } } public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); int [] arr = {4,2,9,7,1,5}; // 向树中添加元素 for (int i = 0; i < arr.length; i++) { binaryTree.add(new Node(arr[i], "李祥"+i)); } // 前序遍历 System.out.println("前序遍历："); binaryTree.preTraversal(); // 中序遍历 System.out.println("中序遍历："); binaryTree.infixTraversal(); // 后序遍历 System.out.println("后序遍历："); binaryTree.postTraversal(); //快速查找二叉树中的元素 System.out.println("查找节点为 2 的元素:"+binaryTree.get(binaryTree.getRoot(), 2)); //查询二叉树的最大深度 System.out.println("二叉树的最大深度:"+binaryTree.maxDep(binaryTree.getRoot())); } }
