[数据结构与算法] Java数据结构和算法---树

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java数据结构和算法---树 -> 正文阅读

[数据结构与算法]Java数据结构和算法---树

·二叉树
????????为什么需要树这种数据结构
? ? ? ? ①数组存储方式的分析
? ? ? ? ? ?优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 ???????????缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
? ? ? ? ②链式存储方式的分析
? ? ? ? ? ?优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。
? ? ? ? ?? 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)?
? ? ? ? ③树存储方式的分析能提高数据存储，读取的效率, ?比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
????????案例: [7, 3, 10, 1, 5, 9, 12]

?二叉树的概念
? ? ? ? ①树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
? ? ? ? ②二叉树的子节点分为左节点和右节点。
? ? ? ? ③如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
? ? ? ? ④如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

?????????完全二叉树，如果把 (61)节点删除，就不是完全二叉树了,因为叶子节点不连续了

二叉树的遍历
????????前序遍历: 先输出父节点，再遍历左子树和右子树
????????中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
????????后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
小结: 看输出父节点的顺序，就确定是前序，中序还是后序

代码:

package tree;

public class BinaryTree1 {
    public static void main(String[] args) {
        Node zhangke1 = new Node(1, "zhangke1");
        Node zhangke2 = new Node(2, "zhangke2");
        Node zhangke3 = new Node(3, "zhangke3");
        Node zhangke4 = new Node(4, "zhangke4");
        Node zhangke5 = new Node(5,"zhangke5");
        zhangke1.right=zhangke3;
        zhangke1.left=zhangke2;
        zhangke3.right=zhangke4;
        zhangke3.left=zhangke5;
        binaryTree binaryTree1 = new binaryTree();
        binaryTree1.setRoot(zhangke1);
        binaryTree1.preOrder();
        System.out.println();
        binaryTree1.midOrder();
        System.out.println();
        binaryTree1.postOrder();
    }
}
class binaryTree{
   private Node root;
   public void setRoot(Node root){
       this.root=root;
   }
   public void preOrder(){
       if (root != null) {
           root.preOrder();
       }else {
           System.out.println("EMPTY");
       }
   }
   public void midOrder(){
        if (root != null) {
            root.midOrder();
        }else {
            System.out.println("EMPTY");
        }
    }
    public void postOrder(){
        if (root != null) {
            root.postOrder();
        }else {
            System.out.println("EMPTY");
        }
    }
}
class Node{
    private int no;
    private String name;
    Node left;
    Node right;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\''
                +
                '}';
    }
    public void preOrder(){
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    public void midOrder(){
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }
    public void postOrder(){
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

二叉树-查找指定节点

?分别利用前中后序查找 找5: 前序比较了4次中序比较了3次后序比较了2次

?代码:

package tree;

public class BinaryTree1 {
    public static void main(String[] args) {
        Node zhangke1 = new Node(1, "zhangke1");
        Node zhangke2 = new Node(2, "zhangke2");
        Node zhangke3 = new Node(3, "zhangke3");
        Node zhangke4 = new Node(4, "zhangke4");
        Node zhangke5 = new Node(5,"zhangke5");
        zhangke1.right=zhangke3;
        zhangke1.left=zhangke2;
        zhangke3.right=zhangke4;
        zhangke3.left=zhangke5;
        binaryTree binaryTree1 = new binaryTree();
        binaryTree1.setRoot(zhangke1);
        System.out.println("前序遍历:");
        binaryTree1.preOrder();
        System.out.println();
        System.out.println("中序遍历:");
        binaryTree1.midOrder();
        System.out.println();
        System.out.println("后序遍历:");
        binaryTree1.postOrder();

        System.out.println("前序遍历查找5:");//四次
        Node node = binaryTree1.preOrderSearch(5);
        if(node!=null){
            System.out.println("找到了"+node.toString());
        }else {
            System.out.println("没找到");
        }
        System.out.println("中序遍历查找5:");//三次
        Node node1 = binaryTree1.midOrderSearch(5);
        if(node1!=null){
            System.out.println("找到了"+node.toString());
        }else {
            System.out.println("没找到");
        }
        System.out.println("后序遍历查找5:");//两次
        Node node2 = binaryTree1.postOrderSearch(5);
        if(node1!=null){
            System.out.println("找到了"+node.toString());
        }else {
            System.out.println("没找到");
        }

    }
}
class binaryTree{
   private Node root;
   public void setRoot(Node root){
       this.root=root;
   }
   public void preOrder(){
       if (root != null) {
           root.preOrder();
       }else {
           System.out.println("EMPTY");
       }
   }
   public void midOrder(){
        if (root != null) {
            root.midOrder();
        }else {
            System.out.println("EMPTY");
        }
    }
    public void postOrder(){
        if (root != null) {
            root.postOrder();
        }else {
            System.out.println("EMPTY");
        }
    }
    public Node preOrderSearch(int no){
       if(root!=null){
           return root.preOrderSearch(no);
       }else {
           return null;
       }
    }

    public Node midOrderSearch(int no){
        if(root!=null){
            return root.midOrderSearch(no);
        }else {
            return null;
        }
    }

    public Node postOrderSearch(int no){
        if(root!=null){
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}
class Node{
    private int no;
    private String name;
    Node left;
    Node right;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\''
                +
                '}';
    }
    public void preOrder(){
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    public void midOrder(){
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }
    public void postOrder(){
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }


    //前序遍历查找
    public Node preOrderSearch(int no){
        System.out.println("1");
        if(this.no==no){
            return this;
        }
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
       //这里无论找不找得到 都要返回 找不到的话返回一个null
            return resNode;

    }
    //中序遍历查找
    public Node midOrderSearch(int no){
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.midOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("2");
        if(this.no==no){
            return this;
        }
        if (this.right != null) {
            resNode = this.right.midOrderSearch(no);
        }
        //这里无论找不找得到 都要返回 找不到的话返回一个null
        return resNode;

    }
    //后序遍历查找
    public Node postOrderSearch(int no){

        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("3");
        if(this.no==no){
            return this;
        }
        return null;
    }
}

二叉树-删除节点

? ? ? ? 如果删除的节点是叶子节点，则删除该节点
????????如果删除的节点是非叶子节点，则删除该子树(临时要求后面会优化).
? ? ? ? 写代码测试，删除掉 5号叶子节点和 3号子树.

代码:

package tree;

import java.util.function.BiFunction;

public class BinaryTree1 {
    public static void main(String[] args) {
        Node zhangke1 = new Node(1, "zhangke1");
        Node zhangke2 = new Node(2, "zhangke2");
        Node zhangke3 = new Node(3, "zhangke3");
        Node zhangke4 = new Node(4, "zhangke4");
        Node zhangke5 = new Node(5,"zhangke5");
        zhangke1.right=zhangke3;
        zhangke1.left=zhangke2;
        zhangke3.right=zhangke4;
        zhangke3.left=zhangke5;
        binaryTree binaryTree1 = new binaryTree();
        binaryTree1.setRoot(zhangke1);
        System.out.println("前序遍历:");
        binaryTree1.preOrder();
        System.out.println();
        System.out.println("中序遍历:");
        binaryTree1.midOrder();
        System.out.println();
        System.out.println("后序遍历:");
        binaryTree1.postOrder();

        binaryTree1.deleteNode(5);
        System.out.println("前序遍历:");
        binaryTree1.preOrder();
        System.out.println();
        System.out.println("中序遍历:");
        binaryTree1.midOrder();
        System.out.println();
        System.out.println("后序遍历:");
        binaryTree1.postOrder();

    }
}
class binaryTree{
   private Node root;
   public void setRoot(Node root){
       this.root=root;
   }
   public void preOrder(){
       if (root != null) {
           root.preOrder();
       }else {
           System.out.println("EMPTY");
       }
   }
   public void midOrder(){
        if (root != null) {
            root.midOrder();
        }else {
            System.out.println("EMPTY");
        }
    }
    public void postOrder(){
        if (root != null) {
            root.postOrder();
        }else {
            System.out.println("EMPTY");
        }
    }
    public Node preOrderSearch(int no){
       if(root!=null){
           return root.preOrderSearch(no);
       }else {
           return null;
       }
    }

    public Node midOrderSearch(int no){
        if(root!=null){
            return root.midOrderSearch(no);
        }else {
            return null;
        }
    }

    public Node postOrderSearch(int no){
        if(root!=null){
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }

    public void deleteNode(int no) {
        if(this.root!=null){
            //只有一个root
            if(root.getNo()==no){
                root=null;
            }else {
                root.deleteNode(no);
            }
        }else {
            System.out.println("空树!");
        }
    }
}
class Node{
    private int no;
    private String name;
    Node left;
    Node right;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

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

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

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

    public void deleteNode(int no){
        if(this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        if(this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        if(this.left!=null){
            this.left.deleteNode(no);
        }
        if(this.right!=null){
            this.right.deleteNode(no);
        }
    }
    public void preOrder(){
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    public void midOrder(){
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }
    }
    public void postOrder(){
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }


    //前序遍历查找
    public Node preOrderSearch(int no){
        System.out.println("1");
        if(this.no==no){
            return this;
        }
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
       //这里无论找不找得到 都要返回 找不到的话返回一个null
            return resNode;

    }
    //中序遍历查找
    public Node midOrderSearch(int no){
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.midOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("2");
        if(this.no==no){
            return this;
        }
        if (this.right != null) {
            resNode = this.right.midOrderSearch(no);
        }
        //这里无论找不找得到 都要返回 找不到的话返回一个null
        return resNode;

    }
    //后序遍历查找
    public Node postOrderSearch(int no){

        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("3");
        if(this.no==no){
            return this;
        }
        return null;
    }
}

顺序存储二叉树的概念?
????????从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组? 如下图所示:

????????要求:
????????????????下图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 且在遍历数组 arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

? ? ? ? 顺序存储二叉树的特点:
????????????????顺序二叉树通常只考虑完全二叉树第n个元素的左子节点为 ?2 * n + 1 第n个元素的右子节点为 ?2 * n + 2 第n个元素的父节点为 ?(n-1) / 2 n : 表示二叉树中的第几个元素(按0开始编号如图所示)

?顺序存储二叉树遍历 (堆排序会用到这个)
????????需求:
????????????????给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。前序遍历的结果应当为 1,2,4,5,3,6,7
????????代码:

package tree;

public class shunxucunchu {
    public static void main(String[] args) {
        int []arr = {1,2,3,4,5,6,7};
        arrayBinaryTree arrayBinaryTree1 = new arrayBinaryTree(arr);//1 2 4 5 3 6 7
        arrayBinaryTree1.preOrder();
    }
}
class arrayBinaryTree{
    private int []arr;//存储结点的数组

    public arrayBinaryTree(int[] arr) {
        this.arr = arr;
    }
    //重载
    public void preOrder(){
        this.preOrder(0);
    }
    //编写一个方法完成顺序存储二叉树的前序遍历
    public void preOrder(int index){//index 数组下标
        if(arr==null||arr.length==0){
            return;
        }
        //输出当前元素
        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);
    }
}

线索化二叉树

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

线索二叉树应用案例
????????将下面的二叉树，进行中序线索二叉树。
????????????????中序遍历的数列为 {8, 3, 10, 1, 14, 6}

?????????tips:当线索化二叉树后，Node节点的属性 left 和 right ，有如下情况:
? ? ? ? ? ? ? ? ①left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
? ? ? ? ? ? ? ? ②right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.?

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2022-04-04 12:36:03 更:2022-04-04 12:39:00

360图书馆购物三丰科技阅读网日历万年历 2024年11日历

-2024/11/26 9:27:34-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码