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

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

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

二叉树简介

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


二叉树的概念


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

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

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
+关注
150文章2问答
目录
打赏
0
0
0
0
6
分享
相关文章
Cyan_RA9
|
1月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表（下）
408考研——《数据结构》算法题基础篇之链表（下）。
Cyan_RA9
86 29
Cyan_RA9
|
1月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表（上）
408考研——《数据结构》算法题基础篇之链表（上）。
Cyan_RA9
95 25
Cyan_RA9
|
1月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组（通俗易懂）
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
Cyan_RA9
72 23
RossyYan
|
2月前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
60 12
RossyYan
|
2月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
53 10
RossyYan
|
2月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
63 5
RossyYan
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
55 2
三三是该溜子
|
3月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
62 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
4月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
104 5
XIAZHI
|
4月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
138 4

热门文章

最新文章

  • 1
    C 408—《数据结构》易错考点200题（含解析）
    16
  • 2
    C 408—《数据结构》算法题基础篇—链表（上）
    9
  • 3
    C 408—《数据结构》算法题基础篇—链表（下）
    3
  • 4
    C 408—《数据结构》图、查找、排序专题考点（含解析）
    5
  • 5
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
    8
  • 6
    c语言及数据结构实现简单贪吃蛇小游戏
    7
  • 7
    Redis原理—1.Redis数据结构
    7
  • 8
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
    2
  • 9
    Python 实现单向链表，和单向链表的反转
    21
  • 10
    STL——栈和队列和优先队列
    16
  • 1
    【数据结构OJ题】复制带随机指针的链表
    69
  • 2
    【数据结构OJ题】环形链表II
    52
  • 3
    【数据结构OJ题】环形链表
    57
  • 4
    【数据结构OJ题】相交链表
    51
  • 5
    刷题训练之链表
    40
  • 6
    【数据结构OJ题】链表分割
    42
  • 7
    【数据结构OJ题】链表的回文结构
    67
  • 8
    【数据结构OJ题】合并两个有序链表
    56
  • 9
    【数据结构OJ题】链表中倒数第k个结点
    52
  • 10
    【数据结构OJ题】链表的中间结点
    39

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    通义万相：视觉生成大模型再进化
    目录
    AI助理

    你好，我是AI助理

    可以解答问题、推荐解决方案等