java数据结构之树

1）二叉树

1.二叉树的概念：

2.常用术语：

1.节点
2.根节点
3.父节点
4.子节点
5.叶子节点（没有子节点的节点）
6.节点的权（节点的值）
7.路径（从root节点找到该节点的路线）
8.层
9.子树
10.树的高度
11.森林

3.二叉树的前序中序后序遍历

前序遍历：

先输出父节点，在遍历左子树和右子树

中序遍历

先输出左子树，在输出父节点，在输出右子树

后序遍历

先输出左子树，在输出右子树，在输出父节点

4.实现前序中序后序代码

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        HerNode root=new HerNode(1,"宋江");
        HerNode node2=new HerNode(2,"吴用");
        HerNode node3=new HerNode(3,"卢俊义");
        HerNode node4=new HerNode(4,"林冲");
        HerNode node5=new HerNode(5,"关胜");
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);
        System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();
       
    }
}
class BinaryTree{
    private HerNode root;

    public void setRoot(HerNode root) {
        this.root = root;
    }
    /**
     * 前序遍历
     */
    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空无法遍历");
        }
    }
    /**
     * 中序遍历
     */
    public void infixOrder(){
        if(this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空无法遍历");
        }
    }
    /**
     * 后序遍历
     */
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空无法遍历");
        }
    }
}
class HerNode{
    private int id;
    private String name;
    private HerNode left;
    private HerNode right;

    public HerNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HerNode getLeft() {
        return left;
    }

    public void setLeft(HerNode left) {
        this.left = left;
    }

    public HerNode getRight() {
        return right;
    }

    public void setRight(HerNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HerNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        //输出root节点
        System.out.println(this);
        if (this.left!=null) {
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        if(this.left!=null){
            this.left.postOrder();
        }
        if(this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

完成了前中后序遍历之后，我们可以试着进行前中后序查找

5.二叉树进行查找

 /**
 前序查找
 */
 public HerNode perHerNodeSearch(int id){
        System.out.println("进入前序遍历");
        if(this.id==id){
            return this;
        }
        HerNode resNode=null;
        if(this.left!=null){
            resNode=this.left.perHerNodeSearch(id);
        }
        //如果不为空，说明我们在左子树找到了
        if(resNode!=null){
            return resNode;
        }
        //如果左子树没找到，我们就在右子树上找
        if(this.right!=null){
             resNode = this.right.perHerNodeSearch(id);
        }
        return resNode;
    }
    

6.二叉树删除节点

我们先进行最简单的删除
如果一个节点没有叶子节点的话就直接删除，如果节点有叶子节点，就直接把这个节点连同叶子节点一起删除

代码实现

/**
     * 删除节点
     */
    public void delNode(int id){
        if(left != null && this.left.id==id){
            this.left=null;
            return;
        }
        if(right !=null && this.right.id==id){
            this.right=null;
            return;
        }
        //如果左右都没有查找到，那我们就要进行递归
        if(this.left!=null){
            this.left.delNode(id);
        }
        if(this.right !=null){
            this.right.delNode(id);
        }
    }

将有序数组转换成二叉树

数组
arr={1,2,3,4,5,6}
二叉树
			1
 		  /   \	
		2      3	
	   / \   /  \	
      4   5  6   7
将数组以这样的形式转成二叉树
(n*2)+1 左边
(n*3)+2 右边

代码实现

    /**
     * 前序遍历
     * @param index 开始索引
     */
    public void preOrder(int index){
        if(arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树进行前序遍历");
        }
        System.out.println(arr[index]);
        if((index*2+1)< arr.length){
            preOrder(index*2+1);
        }
        if((index*2+2)<arr.length){
            preOrder(index*2+2);
        }
    }

    /**
     * 中序遍历
     * @param index 开始遍历元素的数组下标
     */
    public void infixOrder(int index){
        if(arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树进行前序遍历");
        }
        if((index*2+1)<arr.length){
            infixOrder((index*2+1));
        }
        System.out.println(arr[index]);
        if((index*2+2)<arr.length){
            infixOrder((index*2+2));
        }
    }
    public void postOrder(int index){
        if(arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树进行前序遍历");
        }
        if((index*2+1)<arr.length){
            infixOrder((index*2+1));
        }
        if((index*2+2)<arr.length){
            infixOrder((index*2+2));
        }
        System.out.println(arr[index]);
    }

线索化二叉树

树结构的实际应用

• 堆排序

什么是堆排序：
堆排序是分为一个大顶堆和一个小顶堆
我们首先把一个数组转化成一个树形结构
根据一个公式 arr[i]=i*2+1 左子树
           arr[i]=i*2+2 右子树
           

• 堆排序的实现思路

首先把一个无须数组转换成一个大顶堆
将大顶堆的的头节点放入数组的最后一个，然后就行继续arr.length-1大顶堆的转换，最后得到的是一个有序的数组

• 堆排序的代码步骤

首先我们要将一个无序数组转换成一个大顶堆

 /**
     * 将数组转换成一个大顶堆
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int[] arr,int i,int length){
        //先取出当前的值
        int temp=arr[i];
        //k=i*2+1 的是左子节点
        for(int k=i*2+1;k<length;k=k*2+1){
            //如果左子节点的值小于右子节点的值
            if(k+1<length && arr[k]<arr[k+1]){
                k++; //k指向右子节点
            }
            //如果左节点大于父节点，则我们就交换位置
            if(arr[k]> temp){
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        //当for循环结束后，我们已将i为父节点的最大值放在最顶端
        //将temp放到调整后位置
        arr[i]=temp;
    }

这个代码是堆排序中最关键的代码

完成了最大堆的代码，剩下简单了

 public static void heapSort(int[] arr){
        System.out.println("堆排序");
        int temp=0;
     //循环等到非叶子节点的，然后一直进行交换，最后完成最大堆
        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //完成大顶堆之后，将头节点存入数组的最后一个，然后在进行大顶堆排序
        for(int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
        System.out.println("排序" + Arrays.toString(arr));
    }