侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--树(java实现)

林贤钦
2020-06-24 / 0 评论 / 9 点赞 / 743 阅读 / 0 字
温馨提示:
本文最后更新于 2020-06-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

树结构基础部分

为什么需要树这种数据结构

  • 数组存储方式的分析

    优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。

    缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低

  • 链式存储方式的分析

    优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可, 删除效率也很好)。

    缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历)

  • 树存储方式的分析

    能提高数据存储,读取的效率, 比如利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。

树具有的特点有

(1)每个结点有零个或多个子结点

(2)没有父节点的结点称为根节点

(3)每一个非根结点有且只有一个父节点

(4)除了根结点外,每个子结点可以分为多个不相交的子树。

树的常见用语

1、二叉树

1.1、定义

二叉树是每个结点最多有两个子树的树结构。它有五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。

  • 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。

  • 二叉树的子节点分为左节点和右节点。

  • 如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,则我们称为满二叉树。

  • 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。

1.2、二叉树的性质

性质1:二叉树第i层上的结点数目最多为2i-1(i>=1)

性质2:深度为k的二叉树至多有2k-1个结点(k>=1)

性质3:包含n个结点的二叉树的高度至少为(log2n)+1

性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1

1.3、满二叉树

1.4、完全二叉树

面试题:如果一个完全二叉树的结点总数为768个,求叶子结点的个数。

由二叉树的性质知:n0=n2+1,将之带入768=n0+n1+n2中得:768=n1+2n2+1,因为完全二叉树度为1的结点个数要么为0,要么为1,那么就把n1=0或者1都代入公式中,很容易发现n1=1才符合条件。所以算出来n2=383,所以叶子结点个数n0=n2+1=384。

总结规律:如果一棵完全二叉树的结点总数为n,那么叶子结点等于n/2(当n为偶数时)或者(n+1)/2(当n为奇数时)

2、二叉树的前中后序遍历

前置准备,准备一棵树

假设该树中有这7个结点.那么前中后序则为

class BinaryTree{
    private HeroNode root;
    
    //TODO 前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空,无法遍历");
        }
    }

    //TODO 中序遍历
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空,无法遍历");
        }
    }
    //TODO 后序遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空,无法遍历");
        }
    }
}

结点

class Node{
    public int no;
    public Node left;
    public Node right;
    public Node(int no) {
        this.no = no;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                '}';
    }
    //TODO 编写前序遍历的方法
    public void preOrder(){
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if (this.left!=null){
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right!=null){
            this.right.preOrder();
        }
    }
    //TODO 编写中序遍历的方法
    public void infixOrder(){
        //递归向左子树前序遍历
        if (this.left!=null){
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归向右子树前序遍历
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    //TODO 编写后序遍历的方法
    public void postOrder(){
        //递归向左子树前序遍历
        if (this.left!=null){
            this.left.postOrder();
        }
        //递归向右子树前序遍历
        if (this.right!=null){
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }
} 

总结: 前中后序的区别简单来说就是任意三个结点,一个父结点,一对兄弟结点,父结点的输出位置就是前中后序的区别了,前序:父结点,左结点,右节点;中序:左结点,父结点,右节点;后序:左结点,右结点,父结点。

3、顺序存储二叉树

3.1、顺序存储二叉树的特点:

  • 顺序二叉树通常只考虑完全二叉树
  • 第n个元素的左子节点为 2 * n + 1
  • 第n个元素的右子节点为 2 * n + 2
  • 第n个元素的父节点为 (n-1) / 2

3.2、顺序存储的遍历

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr= {1,2,3,4,5,6,7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        arrayBinaryTree.preOrder();
//        arrayBinaryTree.infixOrder();
//        arrayBinaryTree.postOrder();

    }
}
//编写一个ArrayBinaryTree,实现顺序存储二叉树遍历
class ArrayBinaryTree{
    private int[] arr;
    public ArrayBinaryTree(int[] arr){
        this.arr=arr;
    }
    public void preOrder(){
        //如果数组位空,或者arr.length=0;
        if (arr==null||arr.length==0){
            System.out.println("数组为空,不能遍历");
            return;
        }
        preOrder(0);
    }
    //编写一个方法,完成顺序存储二叉树的前序遍历
    private void preOrder(int index){
        //输出当前这人元素
        System.out.print(arr[index]+",");
        //向左递归遍历
        if ((index *2 +1)<arr.length){
            preOrder(2*index+1);
        }
        if ((index*2+2)<arr.length){
            preOrder(2*index+2);
        }
    }
    public void infixOrder(){
        //如果数组位空,或者arr.length=0;
        if (arr==null||arr.length==0){
            System.out.println("数组为空,不能遍历");
            return;
        }
        infixOrder(0);
    }
    private void infixOrder(int index){
        if ((index*2+1)<arr.length){
            infixOrder(index*2+1);
        }
        System.out.print(arr[index]+",");
        if ((index*2+2)<arr.length){
            infixOrder(index*2+2);
        }
    }
    //TODO 后序遍历
    public void postOrder(){
        if (arr==null||arr.length==0){
            System.out.println("数组为空,不能遍历");
            return;
        }
        postOrder(0);
    }
    //TODO 后序遍历
    private void postOrder(int index){
        if ((index*2+1)<arr.length){
            postOrder(index*2+1);
        }
        if ((index*2+2)<arr.length){
            postOrder(index*2+2);
        }
        System.out.print(arr[index]+",");
    }
}

总结:顺序存储的遍历,和二叉树的遍历,变化的也就是将左右结点的引用改成了数组的下标

3.3、顺序存储二叉树的应用

八大排序算法中的堆排序,就会使用到顺序存储二叉树, 关于堆排序,在经典排序算法--java代码实现这篇中

4、线索化二叉树

4.1、线索二叉树基本介绍

  1. n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")
  2. 这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
  3. 一个结点的前一个结点,称为前驱结点
  4. 一个结点的后一个结点,称为后继结点

4.2、构建中序线索化二叉树过程

1、递归线索化左子树 threadedNodes(node.getLeft());

2、线索化当前节点

  • 处理当前结点的前驱结点

  • 如果当前结点的left等于null,即没有指向左子树,让当前结点的左指针指向前驱结点,修改当前结点的左指针的类型

  • 如果得到的前个结点不为null,且当前结点的right等于null。那么将前一个结点pre的right指向当前结点,并设置前一个结点的右指针类型

3、每处理一个结点后,让当前结点是下一个结点的前驱结点 pre=node

4、递归线索化右子树 threadedNodes(node.getRight());

//重载一把threadedNodes方法
public void threadedNodes(){
    this.threadedNodes(root);
}

//编写对二叉树进行中序线索化的方法
public void threadedNodes(Node node){
    //如果node==null 。不能线索化
    if (node==null){
        return;
    }
    //1.线索化左子树
    threadedNodes(node.getLeft());
    //2.线索化当前节点

    //处理当前结点的前驱结点
    if(node.getLeft()==null){
        //让当前结点的左指针指向前驱结点
        node.setLeft(pre);
        //修改当前结点的左指针的类型
        node.setLeftType(1);
    }
    //处理后继结点
    if (pre!=null&&pre.getRight()==null){
        pre.setRight(node);
        pre.setRightType(1);
    }
    //TODO !! 每处理一个结点后,让当前结点是下一个结点的前驱结点
    pre =node;
    //3.线索化右子树
    threadedNodes(node.getRight());
}

4.3、中序线索化遍历

遍历中序线索化二叉树过程:

  1. 如果结点的left 指向的是左子树,node = node.getLeft(); 获取最左边的结点 图中的 4 和 6
  2. 输出这个结点
  3. 如果这个结点的right指向的是后继节点,就一直输出,也就是图中的虚线部分 4--->2、5--->1、 6---->3
  4. 替换这个遍历的结点node=node.getRight();,
  5. 重复 步骤1 ,2, 3, 4直到node==null
//遍历线索化二叉树的方法
public void threadedList(){
    //定义一个变量,存储当前遍历的结点,从root开始
    Node node = root;
    while (node!=null){
        //循环的找到leftType == 1的结点,第一个找到就是4结点
        //后面随着遍历而变化。因为当leftType ==1 时,说明该节点时按照线索化
        //处理后的有效结点
        while (node.getLeftType() == 0){
            node = node.getLeft();
        }
        //打印这个结点
        System.out.println(node);
        //如果当前结点的右指针指向的时后继结点,就一直输出
        while (node.getRightType()==1){
            //获取到当前结点的后继结点
            node =node.getRight();
            System.out.println(node);
        }
        //替换这个遍历的结点
        node=node.getRight();
    }
}

5、二叉排序树

二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。

5.1、定义

二叉排序树:BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。

特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点

5.2、二叉排序树的创建

  1. 判断传入node是否为空,为空直接返回
  2. 判断传入的结点的值,和当前子树的根结点的值的关系
  3. 如果传入结点的值<当前子树的根结点的值
    • 如果当前子树的左子树为空,直接令传入结点的作为子树的左子树
    • 如果当前子树的左子树不为空,则递归进入步骤1
  4. 如果传入结点的值> 当前子树的根结点的值
    • 如果当前子树的右子树为空,直接令传入结点的作为子树的右子树
    • 如果当前子树的右子树不为空,则递归进入步骤1
class BinarySortTree{
    private Node root;
    //添加结点的方法
    public void add(Node node){
        if(root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
}
class Node{
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value=value;
    }

    //添加结点的方法
    //递归的形式添加结点,注意需要满足二叉排序树的要求
    public void add(Node node){
        if (node==null){
            return;
        }
        //判断传入的结点的值,和当前子树的根结点的值的关系
        if (node.value<this.value){
            //如果当前结点的左子结点为null
            if (this.left==null){
                this.left =node;
            }else {
                //否则就递归向左子树添加
                this.left.add(node);
            }
        }else {
            if (this.right==null) {
                this.right =node;
            }else {
                this.right.add(node);
            }
        }
    }
}    

5.3、遍历

二叉排序树的前中后序和二叉树一样

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

5.4、二叉排序树的删除

二叉排序树的删除稍微麻烦一点点,可以分以下几种情况

  • 情况一: 如果没有找到要删除的结点
  • 情况二: 我们发现当前这颗二叉排序树只有一个结点,也就是只有根结点
  • 情况三: 如果要删除的结点是叶子结点,也就是没有左右结点
  • 情况四: 删除有两个子树的节点
  • 情况五: 删除只有一颗子树的结点,也就是有一边子树

情况五又可以分为以下四种情况

  • 父结点不为空,且删除的结点是parent的左子结点
  • 父结点不为空,且删除的结点是parent的右子结点
  • 父结点为空,删除的结点时根结点的左子结点
  • 父结点为空,删除的结点时根结点的右子结点
class BinarySortTree{
    private Node root;
    //添加结点的方法
    public Node getRoot(){
        return root;
    }
   
    //查找要删除的结点
    public Node search(int value){
        if (root==null){
            return  null;
        }else {
            return  root.search(value);
        }
    }

    //查找父结点
    public Node searchParent(int value){
        if(root == null){
            return null;
        }else {
            return root.searchParent(value);
        }
    }
    // 查找右子树最小结点,删除并返回
    public int delRightTreeMin(Node node){
        Node target = node;
        //循环的查找左子结点,就会找到最小值
        while (target.left!=null){
            target=target.left;
        }
        //这时target就指向的最小结点
        //删除最小结点
        delNode(target.value);
        return target.value;
    }
    //删除结点
    public void delNode(int value) {
        if (root==null){
            return;
        }else {
            //先去找到要删除的结点
            Node searchNode = search(value);
            //TODO:情况一:  如果没有找到要删除的结点
            if (searchNode==null){
                return;
            }
            //TODO:情况二:  我们发现当前这颗二叉排序树只有一个结点,也就是只有根结点
            if (root.left ==null && root.right ==null&&root.value==value){
                root=null;
                return;
            }
            //TODO:情况三:  如果要删除的结点是叶子结点,也就是没有左右结点
            Node parentNode = searchParent(value);
            if (searchNode.left==null&& searchNode.right ==null){
                //判断searchNode是父结点的左子结点还是右子结点
                if (parentNode.left!=null&&parentNode.left.value==value){
                    parentNode.left=null;
                }else if (parentNode.right!=null&& parentNode.right.value==value){
                    parentNode.right=null;
                }
            }else if (searchNode.left!=null&& searchNode.right!=null){
                //TODO: 情况四:  删除有两个子树的节点
                int minVal = delRightTreeMin(searchNode.right);
                searchNode.value=minVal;
            }else {
                //TODO: 情况五:  删除只有一颗子树的结点,也就是有一边子树
                if (searchNode.left!=null){//要删除的结点只有左子结点
                    if (parentNode!=null){//父结点不为空
                        if (parentNode.left.value ==value){
                            //要删除的结点是parent的左子结点
                            parentNode.left = searchNode.left;
                        }else {
                            //要删除的结点是parent的右子结点
                            parentNode.right=searchNode.left;
                        }
                    }else {
                        root=searchNode.left;
                    }
                }else {
                    if (parentNode!=null){//父结点不为空
                        if (parentNode.left.value ==value){
                            //要删除的结点是parent的左子结点
                            parentNode.left = searchNode.right;
                        }else {
                            //要删除的结点是parent的右子结点
                            parentNode.right=searchNode.right;
                        }
                    }else {
                        root=searchNode.right;
                    }
                }
            }


        }

    }

}
class Node{
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value=value;
    }

    /**
     * 查找要删除的结点
     * @param value 希望删除的结点的值
     * @return 如果找到就返回该结点,否则就返回null
     */
    public Node search(int value){
        if (value== this.value){
            return this;
        }else if(value<this.value){
            //如果左子结点为空
            if (this.left==null){
                return null;
            }
            return this.left.search(value);
        }else {
            if (this.right== null){
                return null;
            }
            return this.right.search(value);
        }
    }

    /**
     *  查找要删除结点的父结点
     * @param value 要找到的结点的值
     * @return 返回的时要删除的结点的父结点,如果没有就返回null
     */
    public Node searchParent(int value){
        if((this.left!=null && this.left.value == value)||
             (this.right!=null&& this.right.value==value)){
            return this;
        }else {
            //如果查找的值,小于当前结点的值,并且当前结点不为空
            if (value<this.value && this.left !=null){
                return this.left.searchParent(value);//向左子树递归查找
            }else if (value>=this.value&& this.right!=null){
                return this.right.searchParent(value);//向右子树递归查找
            }else {
                return null; // 没有找到父结点
            }
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

9

评论区