[数据结构与算法]java数据结构之树结构入门到入土

1、树结构

是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。
它具有以下的特点：

①每个节点有零个或多个子节点；
②没有父节点的节点称为根节点；
③每一个非根节点有且只有一个父节点；
④除了根节点外，每个子节点可以分为多个不相交的子树；

树结构的基本逻辑模型：

2、树结构的相关术语

1、根节点：不能一棒子打死的说根结点就是树结构中的第一个结点，这是错误不全面的说法，个人认为正确的说法是：只有子结点而没有结点的结点，这一结论贯彻树结构，如果没有理解正确，则在树结构的数据不正确的时候很难找出错误。
2、子节点：有父节点也有子节点的结点。
3、叶子节点：只有父节点而没有子节点的结点
4、结点的度：指结点所拥有的子树的数量，也就是该节点的子节点个数。对于有父节点又有子节点的结点，我们可以称为子树。
5、树的高度：指从当前结点开始加上它的层级子节点。比如说

K节点在树的底层，是一个叶子节点，则一般定义为K的高度在最低为1，以此类推，O的高度也是为1，P的节点也是为1。M节点是叶子节点O的父节点，从下往上数，M节点高度为2。那么G节点的高度是多少呢？从G-L的高度为2，从G-M-O节点高度为3，到底G节点高度为多少呢，正确答案是3

3、二叉树结构

二叉树：每个节点最多含有两个子树的树称为二叉树。在二叉树的概念下又衍生出满二叉树和完全二叉树的概念
1、满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上
2、完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

4、简单二叉树的代码实现

一、简单的结构

public class Tree {
    private Node root; //树结构中的根节点
    //定义三个常量用于树结构的三种遍历方式
    private static final int PREVIOUS_ORDER = 1; 
    private static final int MEDIUM_ORDER = 2;
    private static final int END_ORDER = 3;

//使用内部类来完成结点类的定义
    private class Node{
        private Student data;
        private Node left;
        private Node right;

        public Node(Student data, Node left, Node right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

//定义一个针对于根节点的添加方法，对于不是根节点的结点会走addElement这个添加方法
    public void addNode(Student data){
        if(root == null){
            root = new Node(data,null,null);
            return;
        }
        addElement(data,root);
    }

二、子结点的添加方法

    //遵循二叉树左小右大的原则
    private void addElement(Student node, Node root){
        if(root.left != null && node.getId() < root.data.getId()){//输入的结点的ID大于树根结点的ID，所以向左遍历
            addElement(node,root.left);
            return;
        }else if(root.right != null && node.getId() > root.data.getId()){//向右遍历
            addElement(node,root.right);
            return; //遍历完毕后的返回是一定要的，不然在递归的回溯过程中会将中间的结点给代替掉
        }
		//遍历到树节点的最后一个元素，然后判断输入的结点的ID是否大于最后一个结点ID
        if(root.left == null && node.getId() < root.data.getId()){
            root.left = new Node(node,null,null);
        }else{
            root.right = new Node(node,null,null);
        }
    }

三、树的遍历

 //根据客户的输入进行树结构指定方式的遍历
    public void showElementByOrder(int order){
        order(root,order);
    }
    //树结构的三种遍历方式:前序遍历、中序遍历、后序遍历
    private void order(Node root,int order){
    	//前序遍历的情况
        if(order == PREVIOUS_ORDER) System.out.println(root.data.getName());
        if(root.left != null){
            order(root.left,order);
        }
		//中序遍历的情况
        if(order == MEDIUM_ORDER) System.out.println(root.data.getName());

        if(root.right != null){
            order(root.right,order);
        }
		//后序遍历的情况
        if(order == END_ORDER) System.out.println(root.data.getName());
    }

四、针对树的遍历的分模块写法

    //根据客户的输入进行树结构指定方式的遍历
    public void showElementByOrder(int order){
        switch(order){
            case PREVIOUS_ORDER:preOder(root);break;
            case MEDIUM_ORDER:mediumOrder(root);break;
            case END_ORDER:endOrder(root);break;
        }
        order(root,order);
    }

	//前序遍历
    private void preOder(Node root){
        System.out.println(root.data.getName());
        if(root.left != null){
            preOder(root.left);
        }
        if(root.right != null){
            preOder(root.right);
        }
    }

	//中序遍历
    private void mediumOrder(Node root){
        if(root.left != null){
            mediumOrder(root.left);
        }
        System.out.println(root.data.getName());
        if(root.right != null){
            mediumOrder(root.right);
        }
    }

	//后序遍历
    private void endOrder(Node root){
        if(root.left != null){
            endOrder(root.left);
        }
        if(root.right != null){
            endOrder(root.right);
        }
        System.out.println(root.data.getName());
    }

5、查找指定的元素

对于树结构中的元素查找，我将preOrder方法进行的修改，便用此方法来进行结点的查找

//实质上进行查找的方法，也就是遍历整棵树查找指定的结点
private Node preOder(Node root , int id){
   	if(root.data.getId() == id){
         return root; //找到了结点就返回
    	}
    	//当输入的ID小于当前结点的ID时，则向左遍历
    	//（添加一个判断条件可以不用整棵树都遍历，能大大的减少执行次数，节约更多时间）
    if(root.left != null && root.data.getId() > id){
            return preOder(root.left,id);
        }
        //当输入的ID大于当前结点的ID时，则向右遍历
    if(root.right != null && root.data.getId() < id) {
         return preOder(root.right,id);
      }
      //如果在整棵树上没找到指定的结点则返回NULL
      return null;
  }

//由用户进行输入需要查找的人员的ID
  public Student searchElement(int id){
      Node temp = preOder(root,id);
      return temp == null ? null : temp.data;
  }

6、测试

一、添加元素并遍历树

public class Text {

    public static void main(String[] args) {
       Tree tree = new Tree();
       tree.addNode(new Student(111,"张三",25));
       tree.addNode(new Student(222,"李四",55));
       tree.addNode(new Student(55,"王五",31));
       tree.addNode(new Student(555,"赵六",55));
       tree.showElementByOrder(1);
       tree.showElementByOrder(2);
       tree.showElementByOrder(3);
    }
}

添加成功后的树结构逻辑模型

结果
使用前序遍历 tree.showElementByOrder(1);
张三
王五
李四
赵六
使用中序遍历 tree.showElementByOrder(2);
王五
张三
李四
赵六
使用后序遍历 tree.showElementByOrder(3);
王五
赵六
李四
张三

二、在树结构中查找指定的元素

  Student temp = tree.searchElement(55);
  System.out.println(temp.getName());

结果
王五

7、总结

1、 在数据结构中主要理解两个模型：逻辑模型和内存模型，其次就是运用到的知识，比如本文就大量的使用到了递归，那么递归不得不注意两个逻辑思路：递推、回溯。递推到还好，主要是回溯过程，一不小心就是出现难以寻找的错误，这种错误不会导致程序运行报错，而是会导致数据出错，
2、程序报错作为开发人员倒是不怕，就怕在程序在运行期间数据出现错误，俗话常说：数据就是金钱。程序导致数据出错，无非就是让金钱在你眼皮子底下悄悄溜走。
不要问我为什么要注意或者说怎么样注意回溯过程？那么我只能说：“你代码写少了"，你的留心能让你省下很多”金钱“，至于如何注意回溯过程，其实在程序的世界里很多都是需要靠经验的。
3、切记，在程序的世界里不要拿理论出来说话，因为如果你没尝试过，理论就有可能只是理论。