AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】对比数组链表我发现二叉树的好

2022-03-27 389
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】对比数组链表我发现二叉树的好

二叉树简介

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


二叉树的概念


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

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

2.png



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


3.png


如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数二


层的叶子节点在右边连续，我们称为完全二叉树

10.png



数组

数组存储方式的分析


优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低


画出操作示意图：

4.png



链表

链式存储方式的分析


优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，


删除效率也很好)。


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


操作示意图：

5.png



二叉树

树存储方式的分析


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


可以保证数据的插入，删除，修改的速度


案例: [7, 3, 10, 1, 5, 9, 12]

6.png



认识树结构

树的常用术语(结合示意图理解:


认识树结构

树的常用术语(结合示意图理解:


1) 节点  


2) 根节点  


3) 父节点  


4) 子节点  


5) 叶子节点 (没有子节点的节点)  6) 节点的权(节点值)  7) 路径(从 root 节点找到该节点的路线)  8) 层  


6) 子树  


7) 树的高度(最大层数)  


8.森林 :多颗子树构成森林

7.png



二叉树遍历的说明

前序遍历: 先输出父节点，再遍历左子树和右子树

中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

小结: 看输出父节点的顺序，就确定是前序，中序还是后序

二叉树遍历应用实例(前序,中序,后序)

8.png


二叉树遍历代码实例

 public static void main(String[] args){
     //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
            前序遍历
        //binaryTree.PreOrder();
        中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        后序遍历
        //System.out.println();
        //binaryTree.PostOrder();
 }    
class BinaryTree {
    //确定根节点
    private heroNode head;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(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;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
}

二叉树查找思路

请编写前序查找，中序查找和后序查找的方法。

并分别使用三种查找方式，查找 heroNO = 5 的节点

并分析各种查找方式，分别比较了多少次

思路图解

9.png



二叉树查找代码示例

为了方便更好的阅读代码，就把节点和树类的查找代码专门的写出来，后面会有全代码的部分


class BinatyTree{
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
}
class heroNode{
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
}

二叉树-删除节点

如果删除的节点是叶子节点，则删除该节点

如果删除的节点是非叶子节点，则删除该子树.

测试，删除掉 5 号叶子节点 和 3 号子树.

思路分析

2.png


有关二叉树的，遍历，查找，删除的全代码

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: BinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/3 16:47
 * @version: 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
            前序遍历
        //binaryTree.PreOrder();
        中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        后序遍历
        //System.out.println();
        //binaryTree.PostOrder();
        //System.out.println("前中后查找");
        //System.out.println("开始前序查找");
        //heroNode resNode = binaryTree.preOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始中序查找");
        //heroNode resNode = binaryTree.infixOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始后序查找");
        //heroNode resNode = binaryTree.postOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //    删除测试
        System.out.println("删除前");
        binaryTree.PreOrder();
        System.out.println("删除后");
        binaryTree.deleteNode(5);
        binaryTree.PreOrder();
    }
}
class BinaryTree {
    //确定根节点
    private heroNode head;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(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;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }
    //   中序查找
    public heroNode infixOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }
    //   后序查找
    public heroNode postOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }
    //    删除 
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }
        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }
}


文章标签：
存储
关键词：
数据结构链表
数据结构二叉树
数据结构数组链表
数据结构数组
数组链表
冷环渊Doomwatcher
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
59 4
三三是该溜子
|
1天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
10 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
28天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
54 5
XIAZHI
|
1月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
85 4
XIAZHI
|
1月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念，并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素，以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用，还涉及到了算法逻辑的设计与优化。实验结果显示，学生能够有效掌握并运用这些知识完成指定任务。
XIAZHI
57 4
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
133 8
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
98 4
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
50 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
69 0
数据分析螺丝钉
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
数据分析螺丝钉
52 0

热门文章

最新文章

  • 1
    【C语言】深入浅出：C语言链表的全面解析
  • 2
    Python编程数据结构的深入理解
  • 3
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 4
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 5
    Python 中的数据结构与其他编程语言数据结构的区别
  • 6
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
  • 7
    Python 中的数据结构和算法优化策略
  • 8
    Python 中数据结构和算法的关系
  • 9
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 10
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 1
    数据结构中二叉树，哈希表，顺序表，链表的比较补充
    10
  • 2
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
    43
  • 3
    Pandas数据结构：Series与DataFrame
    43
  • 4
    Java 集合江湖：底层数据结构的大揭秘！
    36
  • 5
    es采用什么数据结构
    36
  • 6
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
    142
  • 7
    Redis 5 种基础数据结构？
    28
  • 8
    C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
    41
  • 9
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
    60
  • 10
    Python 中的数据结构和算法优化策略
    56

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)