java数据结构与算法之顺序存储二叉树

关键词：

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即 数组可以转换成树， 树也可以转换成数组

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

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

需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为1,2,4,5,3,6,7

package com.pierce.algorithm;

class ArrBinaryTree {
    private int[] arr;//存储数据结点的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    //重载 preOrder
    public void preOrder() {
        this.preOrder(0);
    }
//编写一个方法，完成顺序存储二叉树的前序遍历

    /**
     * @param index 数组的下标
     */
    public void preOrder(int index) {
        //如果数组为空，或者 arr.length = 0
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        //输出当前这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if ((index * 2 + 1) < arr.length) {
            preOrder(2 * index + 1);
        }
        //向右递归遍历
        if ((index * 2 + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }
}

数据结构与算法:树顺序存储二叉树(代码片段)

...言,关注博主,底部附有完整代码工具:IDEA本系列介绍的是数据结构:树这是第二篇目前计划一共有12篇:二叉树入门顺序二叉树(本篇)线索化二叉树堆排序赫夫曼树(一)赫夫曼树(二)赫夫曼树(三)二叉排序树平衡二叉树2-3树,2-3-4树,B树B&#... 查看详情

数据结构(12)---二叉树之顺序结构(代码片段)

二叉树文章目录二叉树二叉树的顺序结构及实现二叉树的顺序结构堆的概念及结构堆的创建堆向下调整算法建堆的过程堆的插入堆的删除堆的排序堆的代码实现二叉树的顺序结构及实现二叉树的顺序结构普通的二叉树是不适合用... 查看详情

数据结构与算法————二叉树全面总结(代码片段)

文章目录😎二叉树🍉二叉树定义🍑二叉树的基本术语🍑满二叉树🍑完全二叉树🍉二叉树的基本性质🍉二叉树遍历🍉二叉树的存储结构🍑顺序存储结构🌈代码实现🌟顺序存储结构实... 查看详情

考研数据结构与算法树与二叉树(代码片段)

考研数据结构与算法（六）树与二叉树文章目录考研数据结构与算法（六）树与二叉树一、树的概念和基础术语1.1定义1.2基础术语1.3树的性质二、二叉树2.1二叉树定义2.2二叉树性质2.2.1满二叉树2.2.2完全二叉树2.2.3... 查看详情

计算机软考笔记之《数据结构与算法》

...结构4、常用算法(1)算法概述①算法的基本概念②算法与数据结构③算法的描述 查看详情

.数据结构与算法基础(代码片段)

目录第六章.数据结构与算法基础（重点）第一节.数组与矩阵数组稀疏矩阵第二节.数据结构的定义第三节.线性表链表详解顺序存储与链式存储对比队列与栈第四节.广义表第五节.树与二叉树树的概念二叉树的分类二叉树... 查看详情

java数据结构与算法之线索化二叉树

线索化二叉树先看一个问题将数列{1,3,6,8,10,14}构建成一颗二叉树.n+1=7问题分析:1)当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,6,14}2)但是6,8,10,14这几个节点的左右指针，并没有完全的利用上.3)如果我们希望充分的利用各... 查看详情

数据结构与算法学习笔记树(代码片段)

数据结构与算法学习笔记(7)树前情回顾文章目录数据结构与算法学习笔记(7)树一.树和二叉树的定义1.树树的定义树的基本术语树结构与线性结构比较2.二叉树二叉树的定义二叉树与树的差别二叉树基本形态3.树和二叉树的抽象数... 查看详情

java数据结构与算法之翻转二叉树

该题本来不是一个具有代表性的题目，其实质就是考了一个对于二叉树的遍历问题，但是由于在面试中我多次被问到该题，所以做一个记录。题目描述给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其... 查看详情

javascript--数据结构与算法之二叉树

树是一种非线性的数据结构，以分层的方式存储数据。二叉树：查找非常快，而且二叉树添加或者删除元素也非常快。形象的可以描述为组织结构图，用来描述一个组织的结构。树是由边连接的点组成。树的一些基本概念：根节... 查看详情

java数据结构与算法之翻转二叉树(代码片段)

该题本来不是一个具有代表性的题目，其实质就是考了一个对于二叉树的遍历问题，但是由于在面试中我多次被问到该题，所以做一个记录。题目描述给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其... 查看详情

数据结构-二叉树的存储结构与遍历

定义二叉树的几个重要性质二叉树的抽象数据类型ADT二叉树的存储结构顺序存储结构链式存储结构结点定义二叉树初始化二叉树的遍历测试二叉树的实现定义一个有穷的结点集合，可以为空。若不为空，则它是由根结点... 查看详情

java数据结构和算法顺序存储的树结构

Java数据结构和算法（三）顺序存储的树结构二叉树也可以用数组存储，可以和完全二叉树的节点一一对应。一、树的遍历//二叉树保存在数组中int[]data;publicvoidpreOrder(){preOrder(0);}//前序遍历指定的节点publicvoidpreOrder(intindex){System.ou... 查看详情

王道数据结构与算法树(八——1)(代码片段)

✍、目录脑图树[第一部分]✍、目录脑图1、树1.1、树的基本概念1.2、结点之间的关系描述1.3、有序树、无序树、森林1.4、树的常考性质2、二叉树2.1、满二叉树2.2、完全二叉树2.3、二叉排序树2.4、平衡二叉树2.5、总结3、二叉树的... 查看详情

数据结构与算法之深入解析二叉树的基本算法和递归套路深度实践(代码片段)

一、二叉树的遍历二叉树节点定义： ClassNode//节点的值类型Vvalue;//二叉树的左孩子指针Nodeleft;//二叉树的右孩子指针Noderight;递归实现先序、中序、后序遍历：先序：任何子树的处理顺序都是，先头结点，再左... 查看详情

二叉树之线索二叉树

...，对于一个非叶子结点，其前驱和后继结点查找可以以下算法：1、preNode=node.left;//前去结点就是该结点的左 查看详情

数据结构与算法之二叉树(代码片段)

排序二叉树排序二叉树要求父节点的值大于左节点的值，小于有节点的值。没有父亲节点的节点称为根节点，没有子节点的节点称为叶子节点，其他都称为中间节点。用JS实现一个排序二叉树functionBinaryTree()this.root=null;//初始化根... 查看详情

java数据结构与算法之二叉树的最大宽度和最大深度问题

①、最大深度问题求二叉树的最大深度，最常见的无非两种方式第一种是，以【宽度优先遍历】统计树的层数，树有多少层，那么树就有多高第二种是，以【深度优先遍历】，以我们上面讲的【二叉树通用... 查看详情