• Home
  • home > theory > algorithm > Tree2Graph >

    讲透学烂二叉树(四)：二叉树的存储结构—建堆-搜索-排序

    Author：zhoulujun Date：

    二叉树通常采用链式存储结构，存储结点由数据域和指针域。用一组连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将二叉树上编号为i的结点元素存储在加上定义的一维数组中下标为i-1的分量中。

    数据结构：逻辑结构和存储结构

    数据结构是组织数据的方式，例如树，但是要注意数据结构有两种形式：逻辑结构和存储结构，这两种结构在表示一种数据结构的时候不一定完全相同的，逻辑结构是我们分析数据结构和算法的主要形式，而存储结构则是数据结构在内存中的存储形式。

    逻辑结构是数据结构的逻辑的表示，同时用于分析数据结构时的形象表示，以后的数据结构设计方式按按照逻辑结构的形式，一般来说，所有的数据结构大部分都是讨论其逻辑结构，算法的操作按照逻辑结构的形式，算法的操作说明也是按照逻辑结构的形式。例如二叉堆的逻辑表示形式为树，但是实现的时候可以使用数组，这里的树就是逻辑形式，数组则是存储结构。逻辑结构又分为线性结构和非线性结构，线性结构例如线性表（数组和链表），栈和队列，非线性结构如树和图。

    存储结构是数据结构的实际实现时采取的结构形式，可采取与相应的逻辑结构不同的结构形式，不一定和逻辑结构相同，尽量以简单方便有效率为主，例如不相交集逻辑表示为树，实现的时候使用数组。但是算法的实现还是按照逻辑结构的形式，也就是即使使用数组表示一种数据结构，其操作算法也不一定和常规的数组操作相同。存储结构又分为：顺序结构（数组或顺序表，普通二叉堆使用数组，图可以使用二维数组）、链式结构（链表、栈和队列）、索引结构（树、堆和优先队列）、哈希结构（哈希表、散列结构、不相交集的数组形式是一种散列结构）。

    这里的介绍主要是为了明显区分逻辑结构和存储结构，逻辑结构是算法形式上的，存储结构是编程语言上的，在算法理解上，逻辑结构是需要重点关注的，因为描述算法是按照逻辑结构的形式。


    二叉树的存储结构

    二叉树通常采用链式存储结构，存储结点由数据域和指针域（指针域：左指针域和右指针域）组成，二叉树的链式存储结构也称为二叉链表，对满二叉树和完全二叉树可按层次进行顺序存储

    二叉树存储方式

    存储的方式和图一样，有链表和数组两种，用数组存访问速度快，但插入、删除节点操作就比较费时了。实际中更多的是用链来表示二叉树

    顺序存储结构

    用一组连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将二叉树上编号为i的结点元素存储在加上定义的一维数组中下标为i-1的分量中。“0”表示不存在此结点——广度优先-层序遍历。

    这种顺序存储结构仅适用于完全二叉树。因为，在最坏情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2的n次方-1的一维数组。


    二叉树数组表示

    通过上图我们可以分析得到数组表示的完全二叉树拥有以下几个性质：

    1. Left = index * 2 + 1，例如：根节点的下标为0，则左节点的值为下标array[0＊2+1]=1

    2. Right = index * 2 + 2，例如：根节点的下标为0，则右节点的值为下标array[0＊2+2]=2

    3. Parent(i) = floor((i-1)/2)，i 的父节点下标，Math.ceil((index/2)-1（向上取整），其父节点下标为floor((i-1)/2)（向下取整）

    4. 序数 >= floor(N/2)都是叶子节点，例如：floor(9/2) = 4，则从下标4开始的值都为叶子节点

    顺序存储结构JavaScript代码演示

    复习可以跳过此部分……

    数组转化二叉树
    /**
 * @name 层序遍历
 * @description
 * left = index * 2 + 1，例如：根节点的下标为0，则左节点的值为下标array[0＊2+1]=1
 * right = index * 2 + 2，例如：根节点的下标为0，则右节点的值为下标array[0＊2+2]=2
 * 序数 >= floor(N/2)都是叶子节点，例如：floor(9/2) = 4，则从下标4开始的值都为叶子节点
 * index>0，index的结点的父节点为Math.ceil((index/2)-1，
 * @param arr {number}
 * @return {null|[]}
 */
buildTreeByLevelOrder (arr) {
    let nodesList = this.createNodeList(arr)
    let length = nodesList.length
    if (length === 0) {
        return null
    }
    // 确定每个结点的左右结点
    for (let i = 0; i < length / 2 - 1; i++) {
        if (2 * i + 1 < length) {
            nodesList[i].leftChild = nodesList[2 * i + 1]
            nodesList[i].parentNode = nodesList[Math.floor((i - 1) / 2)]
        }
        if (2 * i + 2 < length) {
            nodesList[i].rightChild = nodesList[2 * i + 2]
            nodesList[i].parentNode = nodesList[Math.floor((i - 1) / 2)]
        }
    }
    // 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理
    let lastIndex = Math.round(length / 2) - 1
    // 左结点
    nodesList[lastIndex].leftChild = nodesList[lastIndex * 2 + 1]
    // 右结点，如果数组的长度为奇数才有右结点
    if (length % 2 === 1) {
        nodesList[lastIndex].rightChild = nodesList[lastIndex * 2 + 2]
    }
    this.tree = nodesList[0]
    return nodesList
}


    二叉树层转化为数组(层序遍历）
    /**
 * @description 深度优先递归
 * @param tree {Node}
 * @return {Array}
 */
levelTraverse (tree) {
    // 分层，每层放一个数组
    let buckets = [[tree]]
    let i = 0
    // 递归，
    function tempFunction (node, i) {
        i++
        let nodes = []
        if (node.leftChild) {
            nodes.push(node.leftChild)
        }
        if (node.rightChild) {
            nodes.push(node.rightChild)
        }
        if (nodes.length) {
            if (buckets[i] === undefined) {
                buckets[i] = nodes
            } else {
                buckets[i].push(...nodes)
            }
            nodes.forEach(item => {
                tempFunction(item, i)
            })
        }
    }
    tempFunction(tree, 0)
    let backs = []
    buckets.forEach(bucket=>{
        backs.push(...bucket.map((node)=>node.data))
    })
    return  backs
}

    演示代码，详情查看https://github.com/zhoulujun/algorithm  

    搜索树的链式存储结构

    二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左右指针域。有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表。 在含有n个结点的二叉链表中有n+1个空链域，我们可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构---线索链表。

    二叉搜索树的节点通常包含4个域，数据元素，分别指向其左，右节点的指针和一个指向父节点的指针所构成，一般把这种存储结构称为三叉链表。

    用代码初始化一个二叉搜索树的结点：

    • 一个指向父亲节点的指针 parent

    • 一个指向左节点的指针 left

    • 一个指向右节点的指针 right

    • 一个数据元素，里面可以是一个key和value

    class BinaryTreeNode {
    constructor (key, value) {
        this.parent = null;
        this.left = null;
        this.right = null;
        this.key = key;
        this.value = value;
    }
}

    链式存储结构JavaScript代码演示

    数组转换为二叉-先序遍历构建二叉树

    插入二叉树实现

    /**
 * @description 先序遍历构建二叉树
 * @param arr
 */
buildBinaryTreeByPreOrder (arr) {
    let root = new Node(arr.shift())
    arr.forEach(data => {
        this.insertNumber(data, root)
    })
    this.tree = root
    return root
}

/**
 * @description 插入节点
 * @param data {Number} 节点值，暂时为数字
 * @param tree {Node} 插入的树
 */
insertNumber (data, tree = this.tree) {
    let newNode = new Node(data)
    debugger
    if (!tree.data) {
        tree.data = data
    } else {
        this.insertNode(tree, newNode)
    }
}

/**
 * @description 插入节点
 * @param node {Node} 节点值，暂时为数字
 * @param newNode {Node} 插入的树
 */
insertNode (node, newNode) {
    newNode.parentNode = node
    if (newNode.data < node.data) {
        if (node.leftChild === null) {
            node.leftChild = newNode
        } else {
            this.insertNode(node.leftChild, newNode)
        }
    } else {
        if (node.rightChild === null) {
            node.rightChild = newNode
        } else {
            this.insertNode(node.rightChild, newNode)
        }
    }
}
    二叉树转换为数组
    /**
 * @description 前序遍历 =>1.访问根节点； 2.访问左子树； 3.访问右子树
 * @param node {Node} 遍历的树
 */
preOrderTraverse (node = this.tree) {
    // 数组存储数遍历值
    let backs = []

    // 递归，
    function tempFunction (node) {
        if (node.data !== null) {
            // 先取根结点
            backs.push(node.data)
            // 如果存在左结点，取左节点的值
            node.leftChild && tempFunction(node.leftChild)
            // 如果存在右结点，取右结点值
            node.rightChild && tempFunction(node.rightChild)
        }
    }

    tempFunction(node)
    return backs
}


    关于算法相关的详细代码，查看https://github.com/zhoulujun/algorithm  

    参考内容

    慕课网视频课程：http://www.imooc.com/learn/888

    javascript/js实现 排序二叉树数据结构 学习随笔 https://www.cnblogs.com/caimuguodexiaohongmao/p/11123933.html

    js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现) https://www.jianshu.com/p/5e9ea25a1aae

    二叉树就是这么简单 https://zhuanlan.zhihu.com/p/34887220



    转载本站文章《讲透学烂二叉树(四)：二叉树的存储结构—建堆-搜索-排序》,
    请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8284.html

    收藏
    上一篇：讲透学烂二叉树(三)：二叉树的遍历图解算法步骤及JS代码
    下一篇：讲透学烂二叉树(五)：分支平衡—AVL树与红黑树伸展树自平衡
    延伸阅读：