精华内容
下载资源
问答
  • 一、树、森林和二叉树之间的转换树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树;反之,任何一棵二叉树也能唯一地对应到一个森林或一棵树。1.1 将树转化为二叉树树中每个...

    一、树、森林和二叉树之间的转换

    树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树;反之,任何一棵二叉树也能唯一地对应到一个森林或一棵树。

    1.1 将树转化为二叉树

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树,具体步骤是:

    1)在所有兄弟结点之间加一连线;

    2)对每个结点,除了保留与其长子的连线外,去掉该结点与其他孩子的连线。

    示例:将图2.1所示的树转换为二叉树。

    0baef108420e405fac3c54151fc90db6.jpg

    根据树转二叉树的规则:第一步,加线;第二步:抹线;第三步:旋转。具体过程如图2.2所示。

    db8a84b66bae462da581957f4acecdc2.jpg

    注意:由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。

    1.2 将一个森林转换为二叉树

    具体方法:

    1)将森林中的每棵树变为二叉树;

    2)因为转换所得的二叉树的根结点的右树均为空,故将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

    示例:将如图2.3所示的森林转化为二叉树

    6dca830c6a934f9c9cc01f391f93a59a.jpg

    1.3 二叉树到树、森林的转换

    把二叉树转换成树和森林的方式是:若结点x是双亲y的左孩子。则把x的右孩子。右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。

    示例:将图2.4所示的二叉树转换为树。

    5144d70823a249d79227d92d62442375.jpg

    二、树、森林的遍历

    2.1 树的遍历

    树的遍历通常有先根遍历和后根遍历两种方式。

    1)先根遍历

    先根遍历的定义为:

    1、访问根结点;

    2、按照从左到右的顺序先根遍历根结点的每一棵子树。

    2)后根遍历

    后根遍历的定义为:

    1、按照从左到右的顺序后根遍历根结点的每一棵子树;

    2、访问根结点。

    示例:

    先根和后根遍历如图2.1(a)所示的树,及先根和中根遍历图2.1(b)所示的二叉树。

    64d2e386be634f89b144382520e976d1.jpg

    根据树的遍历规则,如图2.1(a)所示的树的先根遍历结果是:A,B,C,D,E,F,I,J,D,H;后根遍历结果是:E,C,I,F,J,B,D,H,A。

    根据二叉树的遍历规则:图2.1(a)所示的二叉树的先根遍历结果是:A,B,C,E,F,I,J,D,H;中根遍历结果是:E,C,I,F,J,B,D,H,A。

    图2.1(b)所示的二叉树其实是图2.1(a)`所示的树转换而来的,又示例的遍历结果可知:

    1)前序遍历一棵树恰好等价于前序遍历该树对应的二叉树。

    2)后序遍历树恰好等价于中序遍历该树对应的二叉树。

    2.2 森林的遍历

    森林的遍历右前序遍历和后序遍历两种方式。

    1)前序遍历

    前序遍历的定义为:

    1、访问森林中第一棵树的根结点;

    2、前序遍历第一棵树的根结点的子树;

    3、前序遍历去掉第一棵树后的子森林。

    2)后序遍历

    后序遍历的定义为:

    1、后序遍历第一棵树的根结点的子树;

    2、访问森林中第一棵树的根结点;

    3、后序遍历去掉第一棵树后的子森林。

    示例:

    先根和后根遍历如图2.2(a)所示的森林,及先根和中根遍历图2.2(b)所示的二叉树。

    1e717db2b7264771b21bd558b26f2358.jpg

    根据森林的遍历规则,图2.2(a)所示的树的先根遍历结果是:A,B,C,D,E,F,G,H,I,J,K,L;后根遍历的结果是:B,A,C,F,G,E,D,J,K,I,L,H。

    根据二叉树的遍历规则,图2.2(b)所示的二叉树的先根遍历结果是:A,B,C,D,E,F,G,H,I,J,K,L;中根遍历结果是:B,A,C,F,G,E,D,J,K,L,H。

    图2.2(b)所示的二叉树其实是图2.2(a)所示的森林转换而来的,由示例的遍历结果可推知:

    1、前序遍历一个森林恰好等价于前序遍历该森林对应的二叉树。

    2、后序遍历森林恰好等价于中序遍历该森林对应的二叉树。

    展开全文
  • Java数据结构中 我们有 森林 树 二叉树 (完全二叉树,满二叉树) 平衡树 红黑树 哈弗曼树 还有mysql中的B 树 B+ 树等树的结构 1.1 树 :在Java程序中 树的实现分为两种一种 是 数组实现还有一种是链表实现现在树的...

    JAVA(数据结构和算法)一 树结构

    树的概念

    1. 在Java数据结构中 我们有 森林 树 二叉树 (完全二叉树,满二叉树) 平衡树 红黑树 哈弗曼树 还有mysql中的B 树 B+ 树等树的结构

    1.1 树 :在Java程序中 树的实现分为两种一种 是 数组实现还有一种是链表实现现在树的实现一般是基于链表实现的。Java中树的结构如下

    在这里插入图片描述
    这就是一个常见的树结构 一个树有一个唯一的根节点root上图的A 为该树的根节点 那么 那么一个节点我称为Node 如果一个节点下面有多个节点我们称这些节点为 子节点(孩子节点,叶子节点) 反之这个拥有子节点的 节点我们称之为父节点 如果一个节点之间有多个 节点 我们称这些节点为兄弟节点

    一个树有以下这个特点
    1.1.1 度:什么是度 一个节点拥有的子节点个数我们称之为度 比如A的度为3 B的度为 2 C的度为0
    1.1.2 深度:由根节点开始 由上而下 的一个深度 比如B的深度为2
    1.1.3 高度: 与深度相反 从最下面的节点开始 由下到上 比如A的高度为3 这里注意一点 一个节点的高度和深度不一定相等 比如 A的深度为1 高度为3
    1.1.4.度数:整个树所有有叶子节点的度的总和 比如上面的 度数为5 度数是总节点数-1

    1.2 二叉树: 二叉树是树里面的一种特殊的 存在方式 从字面意思 也可以看出 二叉树 一个节点下面最多有两个子节点这样就形成了二叉树 二叉树 又分为
    完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    满二叉树: 在这里插入图片描述
    当一个二叉树 除最后一层没有子节点其他 都是两个子节点时 我们称这个二叉树为满二叉树
    广度优先: 这是最简单的一种遍历方式 从根节点开始 横向遍历 例如上面 的二叉树 广度遍历为 ABCDEFG

    深度优先: 这是最常用的一种遍历方式 由根节点开始往下深度遍历 深度遍历 又分为
    前序遍历 :从根节点开始依次遍历左边和右边 由上图遍历结果为 ABDECFG 前序遍历特点遍历时根节点一定是第一个
    中序遍历 :从最左边开始 以父节点为中心对称遍历 由上图遍历结果为 DBEAFCG 中序遍历的特点 遍历的时候根节点不可能出现在 头部 和尾部
    后序遍历: 从深度最深开始遍历 先遍历根节点左边然后是右边最后是根
    节点由上图遍历结果为 DEBFGCA 后序遍历的特点根节点一定是最后
    一个被遍历的

    1.3 红黑树 : 红黑树是平衡树的一种 红黑树 在java中最常见的地方是hashmap的在而hashmap是基于 链址算法实现的 也就是基于数组和链表 我们知道 链表的搜索很慢 所以这个时候使用红黑树的 二分查找大大加快的检索的效率

    1.4 B 树 :学过mysql的应该了解过 用于 优化索引 加快搜索效率 具体原理本人能力有限就不在叙述

    1.5 B+树 :B树的一个加强版用处跟B 树一样加快搜索效率但之间的有些结构不一样

    展开全文
  • 一、树、森林和二叉树之间的转换 树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树;反之,任何一棵二叉树也能唯一地对应到一个森林或一棵树。 2.1 将树转化为二叉树 树中...

    一、树、森林和二叉树之间的转换

    树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树;反之,任何一棵二叉树也能唯一地对应到一个森林或一棵树。

    1.1 将树转化为二叉树

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树,具体步骤是:
    1)在所有兄弟结点之间加一连线;
    2)对每个结点,除了保留与其长子的连线外,去掉该结点与其他孩子的连线。
    示例:将图2.1所示的树转换为二叉树。

    在这里插入图片描述

    根据树转二叉树的规则:第一步,加线;第二步:抹线;第三步:旋转。具体过程如图2.2所示。

    在这里插入图片描述

    注意:由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。

    1.2 将一个森林转换为二叉树

    具体方法:
    1)将森林中的每棵树变为二叉树;
    2)因为转换所得的二叉树的根结点的右树均为空,故将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

    示例:将如图2.3所示的森林转化为二叉树
    在这里插入图片描述

    1.3 二叉树到树、森林的转换

    把二叉树转换成树和森林的方式是:若结点x是双亲y的左孩子。则把x的右孩子。右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。

    示例:将图2.4所示的二叉树转换为树。
    在这里插入图片描述

    二、树、森林的遍历

    2.1 树的遍历

    树的遍历通常有先根遍历和后根遍历两种方式。
    1)先根遍历
    先根遍历的定义为:
    1、访问根结点;
    2、按照从左到右的顺序先根遍历根结点的每一棵子树。
    2)后根遍历
    后根遍历的定义为:
    1、按照从左到右的顺序后根遍历根结点的每一棵子树;
    2、访问根结点。

    示例:
    先根和后根遍历如图2.1(a)所示的树,及先根和中根遍历图2.1(b)所示的二叉树。
    在这里插入图片描述

    根据树的遍历规则,如图2.1(a)所示的树的先根遍历结果是:A,B,C,D,E,F,I,J,D,H;后根遍历结果是:E,C,I,F,J,B,D,H,A。
    根据二叉树的遍历规则:图2.1(a)所示的二叉树的先根遍历结果是:A,B,C,E,F,I,J,D,H;中根遍历结果是:E,C,I,F,J,B,D,H,A。
    2.1(b)所示的二叉树其实是图2.1(a)`所示的树转换而来的,又示例的遍历结果可知:
    1)前序遍历一棵树恰好等价于前序遍历该树对应的二叉树。
    2)后序遍历树恰好等价于中序遍历该树对应的二叉树。

    2.2 森林的遍历

    森林的遍历右前序遍历和后序遍历两种方式。
    1)前序遍历
    前序遍历的定义为:
    1、访问森林中第一棵树的根结点;
    2、前序遍历第一棵树的根结点的子树;
    3、前序遍历去掉第一棵树后的子森林。
    2)后序遍历
    后序遍历的定义为:
    1、后序遍历第一棵树的根结点的子树;
    2、访问森林中第一棵树的根结点;
    3、后序遍历去掉第一棵树后的子森林。

    示例:
    先根和后根遍历如图2.2(a)所示的森林,及先根和中根遍历图2.2(b)所示的二叉树。
    在这里插入图片描述

    根据森林的遍历规则,图2.2(a)所示的树的先根遍历结果是:A,B,C,D,E,F,G,H,I,J,K,L;后根遍历的结果是:B,A,C,F,G,E,D,J,K,I,L,H。
    根据二叉树的遍历规则,图2.2(b)所示的二叉树的先根遍历结果是:A,B,C,D,E,F,G,H,I,J,K,L;中根遍历结果是:B,A,C,F,G,E,D,J,K,L,H。
    图2.2(b)所示的二叉树其实是图2.2(a)所示的森林转换而来的,由示例的遍历结果可推知:
    1、前序遍历一个森林恰好等价于前序遍历该森林对应的二叉树。
    2、后序遍历森林恰好等价于中序遍历该森林对应的二叉树。

    展开全文
  • 总目录:地址如下看总纲1、树的常用...从root节点找到该节点的路线8、层9、子树10、树的高度:最大层数11、森林 :多颗子树构成森林2、二叉树的概念树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树...

    总目录:地址如下看总纲

    1、树的常用术语

    2d1f3520a8c4

    image.png

    1、节点:就是节点,没什么鸡毛好讲

    2、根节点:就是最上层,祖宗

    3、父节点:

    4、子节点:

    5、叶子节点:没有子节点的节点

    6、节点的权:就是节点值(大多时候是个对象)

    7、路径:从root节点找到该节点的路线

    8、层

    9、子树

    10、树的高度:最大层数

    11、森林 :多颗子树构成森林

    2、二叉树的概念

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

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

    以下三种均为二叉树:

    2d1f3520a8c4

    image.png

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

    2d1f3520a8c4

    image.png

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

    2d1f3520a8c4

    image.png

    3、二叉树的遍历说明

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

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

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

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

    4、前,中,后序遍历详解

    创建一颗二叉树

    前序遍历

    2.1 先输出当前节点(初始的时候是root节点)

    2.2 如果左子节点不为空,则递归继续前序遍历

    2.3 如果右子节点不为空,则递归继续前序遍历

    中序遍历

    3.1 如果当前节点的左子节点不为空,则递归中序遍历

    3.2 输出当前节点

    3.3 如果当前节点的右子节点不为空,则递归中序遍历

    后序遍历

    4.1 如果当前节点的左子节点不为空,则递归后序遍历

    4.2 如果当前节点的右子节点不为空,则递归后序遍历

    4.3 输出当前节点

    2d1f3520a8c4

    image.png

    5、前,中,后序代码实现

    package com.kk.datastructure.tree;

    /**

    * title: 二叉树的前,中,后序遍历

    * @author 阿K

    * 2020年12月29日 下午11:29:56

    */

    public class BinaryTreeDemo {

    public static void main(String[] args) {

    // 创建二叉树

    BinaryTree binaryTree = new BinaryTree();

    // 创建需要的结点

    HeroNode root = new HeroNode(1, "宋江");

    HeroNode node2 = new HeroNode(2, "吴用");

    HeroNode node3 = new HeroNode(3, "卢俊义");

    HeroNode node4 = new HeroNode(4, "林冲");

    HeroNode node5 = new HeroNode(5, "关胜");

    // 加入树

    root.setLeft(node2);

    root.setRight(node3);

    node3.setRight(node4);

    node3.setLeft(node5);

    binaryTree.setRoot(root);

    System.out.println("前序遍历,预计结果:1,2,3,5,4");

    binaryTree.perOrder();

    System.out.println("中序遍历,预计结果:2,1,5,3,4");

    binaryTree.infixOrder();

    System.out.println("后序遍历,预计结果:2,5,4,3,1");

    binaryTree.postOrder();

    }

    }

    // 定义二叉树

    class BinaryTree {

    private HeroNode root;// 根节点

    public void setRoot(HeroNode root) {

    this.root = root;

    }

    // 前序遍历

    public void perOrder() {

    if (this.root != null) {

    this.root.perOrder();

    } 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 HeroNode {

    private int no;

    private String name;

    private HeroNode left; // 左节点(默认为null)

    private HeroNode right; // 右节点(默认为null)

    public HeroNode(int no, String name) {

    this.no = no;

    this.name = name;

    }

    // 节点的前序遍历

    public void perOrder() {

    // 1.先输出入父节点

    System.out.println(this);

    // 2.递归左子树前序遍历

    if (this.left != null) {

    this.left.perOrder();

    }

    // 3.递归右子树前序遍历

    if (this.right != null) {

    this.right.perOrder();

    }

    }

    // 节点的中序遍历

    public void infixOrder() {

    // 1.递归左子树中序遍历

    if (this.left != null) {

    this.left.infixOrder();

    }

    // 2.输出父节点

    System.out.println(this);

    // 3.递归右子树中序遍历

    if (this.right != null) {

    this.right.infixOrder();

    }

    }

    // 节点的后序遍历

    public void postOrder() {

    // 1.递归左子树后序遍历

    if (this.right != null) {

    this.left.postOrder();

    }

    // 2.递归右子树后序遍历

    if (this.right != null) {

    this.right.postOrder();

    }

    // 3.输出父节点

    System.out.println(this);

    }

    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 HeroNode getLeft() {

    return left;

    }

    public void setLeft(HeroNode left) {

    this.left = left;

    }

    public HeroNode getRight() {

    return right;

    }

    public void setRight(HeroNode right) {

    this.right = right;

    }

    @Override

    public String toString() {

    return "HeroNode [no=" + no + ", name=" + name + "]";

    }

    }

    6、前,中,后序查找思路

    前序查找思路:

    1、先判断当前结点的 no 是否等于要查找的

    2、如果是相等,则返回当前结点

    3、如果不等,则判断当前结点的左子节点是否为空,如果不为空,则递归前序查找4、如果左递归前序查找,找到结点,则返回,否继续判断,当前的结点的右子节点是否为空,如果不空,则继续向右递归前序查找.

    中序查找思路:

    1、判断当前结点的左子节点是否为空,如果不为空,则递归中序查找

    2、如果找到,则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点,否则继续进行右递归的中序查找

    3、如果右递归中序查找,找到就返回,否则返回 null

    后序查找思路

    1、判断当前结点的左子节点是否为空,如果不为空,则递归后序查找

    2、如果找到,就返回,如果没有找到,就判断当前结点的右子节点是否为空,如果不为空,则右递归进行后序查找,如果找到,就返回

    3、最后和当前结点进行比较,是则返回,否则返回 null

    2d1f3520a8c4

    image.png

    7、前,中,后序查找代码

    package com.kk.datastructure.tree;

    /**

    * title: 前中后序查找

    * @author 阿K

    * 2020年12月30日 下午11:49:44

    */

    public class BinaryTreeDemo2 {

    public static void main(String[] args) {

    // 创建二叉树

    BinaryTree binaryTree = new BinaryTree();

    // 创建需要的结点

    HeroNode root = new HeroNode(1, "宋江");

    HeroNode node2 = new HeroNode(2, "吴用");

    HeroNode node3 = new HeroNode(3, "卢俊义");

    HeroNode node4 = new HeroNode(4, "林冲");

    HeroNode node5 = new HeroNode(5, "关胜");

    // 加入树

    root.setLeft(node2);

    root.setRight(node3);

    node3.setRight(node4);

    node3.setLeft(node5);

    binaryTree.setRoot(root);

    System.out.println("前序遍历,预计统计次数:4 ===> 查找顺序 1,2,3,5,4");

    binaryTree.perOrderSearch(5);

    System.out.println("中序遍历,预计统计次数:3 ===》 查找顺序 2,1,5,3,4");

    binaryTree.infixOrderSearch(5);

    //

    System.out.println("后序遍历,预计统计次数:2 ===》 查找顺序 2,5, 4,3,1");

    binaryTree.postOrderSearch(5);

    }

    }

    // 定义二叉树

    class BinaryTree {

    private HeroNode root;// 根节点

    public void setRoot(HeroNode root) {

    this.root = root;

    }

    // 前序遍历查找

    public HeroNode perOrderSearch(int no) {

    if (root != null) {

    return root.perOrderSearch(no);

    } else {

    return null;

    }

    }

    // 中序遍历查找

    public HeroNode infixOrderSearch(int no) {

    if (root != null) {

    return root.infixOrderSearch(no);

    } else {

    return null;

    }

    }

    // 后序遍历查找

    public HeroNode postOrderSearch(int no) {

    if (root != null) {

    return root.postOrderSearch(no);

    } else {

    return null;

    }

    }

    }

    // 定义节点

    class HeroNode {

    private int no;

    private String name;

    private HeroNode left; // 左节点(默认为null)

    private HeroNode right; // 右节点(默认为null)

    public HeroNode(int no, String name) {

    this.no = no;

    this.name = name;

    }

    /**

    * 须知:关于查找次数的统计

    * 为了有效的统计出正确的次数,应该放在 if(this.no == no) 上面

    * @param no

    * @return

    */

    // 节点的前序遍历查找

    public HeroNode perOrderSearch(int no) {

    System.out.println("记录前序遍历查找,打印次数决定查找运行次数!");

    // 比较当前节点是否

    if (this.no == no) {

    return this;

    }

    // 1、判断当前节点的左子节点是否为空,若不为空,则左递归前序查找

    // 2、若左递归前序查找,找到节点则返回

    HeroNode resNode = null;

    if (this.left != null) {

    resNode = this.left.perOrderSearch(no);

    }

    if (resNode != null) {// 说明在左子树上找到了

    return resNode;

    }

    // 1、当前节点的右子树是否为空,若不为空,则右递归前序查找

    // 2、若右递归前序查找,找到节点则返回

    if (this.right != null) {

    resNode = this.right.perOrderSearch(no);

    }

    return resNode;

    }

    // 节点的中序遍历查找

    public HeroNode infixOrderSearch(int no) {

    // 1、判断当前左节点是否为空,若不为空,则继续左递归中序遍历查找

    HeroNode resNode = null;

    if (this.left != null) {

    resNode = this.left.infixOrderSearch(no);

    }

    // 2、若不为空,则返回(既找到)

    if (resNode != null) {

    return resNode;

    }

    System.out.println("进入中序查找的次数统计");

    // 3、和当前节点进行比较,若是则返回

    if (this.no == no) {

    return this;

    }

    // 4、若不是,则继续右递归中序遍历查找

    if (this.right != null) {

    resNode = this.right.infixOrderSearch(no);

    }

    return resNode;

    }

    // 节点的后序遍历查找

    public HeroNode postOrderSearch(int no) {

    // 1、判断当前左节点是否为空,若不为空,则继续左递归后序遍历查找

    HeroNode resNode =null;

    if(this.left!=null) {

    resNode = this.left.postOrderSearch(no);

    }

    // 2、若不为空,则返回

    if(resNode !=null) {

    return resNode;

    }

    // 3、若当前左子树没有找到,则开始右子树后序递归遍历查找

    if(this.right!=null) {

    resNode = this.right.postOrderSearch(no);

    }

    // 4、若不为空,则返回

    if(resNode!=null) {

    return resNode;

    }

    System.out.println("进入后序号查找次数统计");

    // 5、若左右子树都没有找到,就比较当前节点是否

    if(this.no==no) {

    return this;

    }

    return resNode;

    }

    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 HeroNode getLeft() {

    return left;

    }

    public void setLeft(HeroNode left) {

    this.left = left;

    }

    public HeroNode getRight() {

    return right;

    }

    public void setRight(HeroNode right) {

    this.right = right;

    }

    @Override

    public String toString() {

    return "HeroNode [no=" + no + ", name=" + name + "]";

    }

    }

    8、删除树节点思路分析(入门版)

    规定

    1、若删除的节点是叶子节点,则删除该节点

    2、若删除的节点是非叶子节点,则删除该子树

    思路:

    1、判空,若只有一个 root 根节点存在,则等价于二叉树置空

    2、故当前入门级二叉树是单向的,所以我们是只判断当前节点的子节点是否为需要删除的

    3、若当前节点的左子节点不为空,并且左子节点就是要删除的节点,就将 this.left =null(既删除),并返回(return 结束递归)

    4、若当前节点的右子节点不为空,并且右子节点就是要删除的节点,就将 this.rigth=null (既删除),并返回(return 结束递归)

    5、若 以上两步都没有删除节点,那么就进行左子树递归删除

    6、如若以上三步都没有删除,则进行右子树递归删除

    9、删除树节点代码(入门版)

    package com.kk.datastructure.tree;

    /**

    * title: 删除节点

    * @author 阿K

    * 2020年12月31日 下午11:57:45

    */

    public class BinaryTreeDemo3 {

    public static void main(String[] args) {

    // 创建二叉树

    BinaryTree binaryTree = new BinaryTree();

    // 创建需要的结点

    HeroNode root = new HeroNode(1, "宋江");

    HeroNode node2 = new HeroNode(2, "吴用");

    HeroNode node3 = new HeroNode(3, "卢俊义");

    HeroNode node4 = new HeroNode(4, "林冲");

    HeroNode node5 = new HeroNode(5, "关胜");

    // 加入树

    root.setLeft(node2);

    root.setRight(node3);

    node3.setRight(node4);

    node3.setLeft(node5);

    binaryTree.setRoot(root);

    // 删除测试。。

    System.out.println("删除前:");

    binaryTree.perOrder();

    binaryTree.delNode(3);

    System.out.println("删除后:");

    binaryTree.perOrder();

    }

    }

    // 定义二叉树

    class BinaryTree {

    // 前序遍历

    public void perOrder() {

    if (this.root != null) {

    this.root.perOrder();

    } else {

    System.out.println("二叉树为空,无法遍历~");

    }

    }

    private HeroNode root;// 根节点

    public void setRoot(HeroNode root) {

    this.root = root;

    }

    // 删除节点

    public void delNode(int no) {

    if (this.root != null) {

    // 1、判空,若只有一个 root 根节点存在,则等价于二叉树置空

    if (root.getNo() == no) {

    root = null;

    } else {

    // 否则 递归删除

    root.delNode(no);

    }

    } else {

    System.out.println("当前二叉树为空,删个鸡毛??");

    }

    }

    }

    // 定义节点

    class HeroNode {

    private int no;

    private String name;

    private HeroNode left; // 左节点(默认为null)

    private HeroNode right; // 右节点(默认为null)

    public HeroNode(int no, String name) {

    this.no = no;

    this.name = name;

    }

    // 节点删除

    // 1、若删除的节点是叶子节点,则删除该节点

    // 2、若删除的节点是非叶子节点,则删除该子树

    public void delNode(int no) {

    // 2、故当前入门级二叉树是单向的,所以我们是只判断当前节点的子节点是否为需要删除的

    // 3、若当前节点的左子节点不为空,并且左子节点就是要删除的节点,就将 this.left =null(既删除),并返回(return 结束递归)

    // 4、若当前节点的右子节点不为空,并且右子节点就是要删除的节点,就将 this.rigth=null (既删除),并返回(return 结束递归)

    // 5、若 以上两步都没有删除节点,那么就进行左子树递归删除

    // 6、如若以上三步都没有删除,则进行右子树递归删除

    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.delNode(no);

    }

    if (this.right != null) {

    this.right.delNode(no);

    }

    }

    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 HeroNode getLeft() {

    return left;

    }

    public void setLeft(HeroNode left) {

    this.left = left;

    }

    public HeroNode getRight() {

    return right;

    }

    public void setRight(HeroNode right) {

    this.right = right;

    }

    // 节点的前序遍历

    public void perOrder() {

    // 1.先输出入父节点

    System.out.println(this);

    // 2.递归左子树前序遍历

    if (this.left != null) {

    this.left.perOrder();

    }

    // 3.递归右子树前序遍历

    if (this.right != null) {

    this.right.perOrder();

    }

    }

    @Override

    public String toString() {

    return "HeroNode [no=" + no + ", name=" + name + "]";

    }

    }

    展开全文
  • Java数据结构和算法.

    2013-10-24 14:33:16
    java语言基础知识 数据结构与算法基础 线性表 List、单链表、双链表、迭代器 栈和队列 递归 树 二叉树、树和森林、Huffman树 图 查找 排序
  • 树树的定义结点分类结点间的相互关系树的其他概念树的抽象数据类型树的存储结构双亲表示法双亲孩子表示法孩子兄弟表示法二叉树二叉树的特点特殊二叉树二叉树的性质...树是一种一对多的数据结构。 树是含有n个结点的...
  • java算法与数据结构

    2012-04-14 12:34:38
    算法与数据结构基本概念 (1)数据、数据对象和数据结构 (2)抽象数据类型 (3)算法的特征及评价的标准 (4)数据的存储结构类型 2.线形结构 (1)顺序表的特点及存储结构 (2)链表的特点及存储结构 (3)栈的...
  • Java编写一个并查集,森林版,V1.0呦。
  • 1 树转换为二叉树对树采用孩子兄弟表示法即可,关于孩子兄弟表示法,可以看这篇文章:树结构的入门以及Java通用实现方式,其中的实现方法中有介绍。树转换为二叉树的具体步骤:加线。在所有兄弟结点之间加一条连线。...
  • 5.9 森林 5.10 不相交集合的表示 5.11 二叉树的计数 5.12 参考文献和选读材料 第6章 图 6.1 图的抽象数据类型 6.2 图的基本操作 6.3 最小代价生成树 6.4 最短路径和迁移闭包 6.5 活动网络 6.6 参考文献和...
  • 结点包含 数据域信息data + 父结点在存储结构中的位置信息parent +孩子链表的头指针firstChild。 孩子兄弟链表存储结构: 结点包含 数据域信息data + (左指针)孩子链表的头指针firstChild + (右指针)该...
  • 森林版查集 并查集V1.1不使用联合启发式或路径压缩算法,新版本采用同样的基本思路,但使用了按等级和路径压缩的并集。 核心功能 void union(root1, root2) → Merge two sets int find(x) → Return set ...
  • 并查集 并查集是重要的数据结构,在算法编写中很常见。 这里写的比较平实,不使用联合启发式或路径压缩算法。 集合中的元素从0开始编号。 可结合着看:并查集V1.0——森林版。 核心功能 void union(root1, root2) →...
  • 一、树结构概述 根节点:1号节点 双亲节点:10号节点和11号节点的双亲节点是5号节点 子节点:7、8、9号节点是4号节点的子节点 路径:1号到11号的路径:1、2、5、11 节点的度:子节点的个数,1号的度为3 节点的权:节点存储...
  • 数据结构--二叉树(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 树的常用术语(结合示意图理解) 节点 根节点 父节点 子...
  • 初入数据结构的树(Tree)以及Java代码实现 树的定义 为什么叫树? 树型结构的元素具有一对多关系 树的定义 树的一些基本概念 树的结点 后代,祖先 子树、空树 树的度与高(深度),结点的度与层次 有序树,无序...
  • 图(Java)图的基本概念完全图子图邻接点顶点的度连通图和连通分量强连通图和强连通分量生成树和生成森林图的存储结构主要方法邻接矩阵邻接表 图的基本概念 图是由顶点(Vertex)的有穷非空集合和顶点之间边(Edge)...
  • 通用树的理论知识一、树的定义由一个或多个(n>=0)节点组成的有限集合T,有且仅有一个节点称为根(root),当n>1时,其7余的节点为m(m>=0)个互不相交的有限集合T1,T2,......3. 森林:m棵不相交树的集合。4....
  • 学习视频:尚硅谷韩老师Java讲解数据结构与算法 一、树 树示意图: 树的常用术语(结合示意图理解): 1) 节点 2) 根节点 3) 父节点 4) 子节点 5) 叶子节点 (没有子节点的节点) 6) 节点的权(节点值) 7) 路径(从...
  • 3.二叉树转换为森林 3去掉每个结点之间原有连线 四.树和森林 A C B E D X 3.二叉树转换为森林 4去掉虚拟根结点 四.树和森林 A C B E D 3.二叉树转换为森林 5将连线逆时针旋转整理成多棵树并列的森林 四.树和森林 A C...
  • 初入数据结构的树(Tree)以及Java代码实现(一) 树的定义 为什么叫树? 树型结构的元素具有一对多关系 树的定义 树的一些基本概念 树的结点 后代,祖先 子树、空树 树的度与高(深度),结点的度与...
  • 首先生成已给权重的所有的叶子结点,然后取所有节点中最小和次小的结点作为左右孩子生成一个哈夫曼树,计算出父节点的权重放入给出的权重森林中,并把之前的最小和次小的结点从森林中删除,再在种种森林中找最小和次...
  • 数据结构--二叉树(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 树的常用术语(结合示意图理解) 节点 根节点 父节点 子...
  • 一棵树只有一个根节点,如果一棵树有了多个根节点,那它已经不再是一棵树了,而是多棵树的集合,也被称为森林。 实现一颗树,采用数组的存储方式,将树中的节点用Node类表示,方便与操作。 首先,整棵树的数组结构...
  • 首先生成已给权重的所有的叶子结点,然后取所有节点中最小和次小的结点作为左右孩子生成一个哈夫曼树,计算出父节点的权重放入给出的权重森林中,并把之前的最小和次小的结点从森林中删除,再在种种森林中找最小和次...
  • 基本概念树状图(Tree)又称为树,是一种复杂的数据结构。树是由 n(n>=0)个有限节点组成一个具有层次关系的集合,把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。当 n=0 时,称之为...
  • 二叉树作为数据结构中的一种,是树的一种特殊结构。 其具备许多树结构:根节点(1)、双亲节点、子节点、路经、节点的度(子的个数)、节点的权(存储数字)、叶子节点(无子节点的节点)、子树、层、树的高度...
  • 树和树的算法一、树1.1 树的概念树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它...
  • 伪代码(DFS思路): DFS(G){ //初始化图 for(each vertex u∈v[G]){ color[u]=WHITE; parent[u[=null;...//计算时间的全局变量for(each vertex u∈v[G]){//搜森林 if(color==WHITE){//搜一棵树,一次...
  • Java结构基础

    2020-02-10 21:02:56
    为什么需要树这种数据结构: 树存储方式能够提高数据存储、读取的效率,比如利用**二叉排序树(Binary Sort Tree),**既可以保证数据的检索速度,同时可以保证数据的插入、删除、修改的速度 树的常用术语: 节点...

空空如也

空空如也

1 2 3 4
收藏数 71
精华内容 28
关键字:

java森林数据结构

java 订阅
数据结构 订阅