12月01, 2016

二叉🌲🌲两三下

一、前言

树和图一样,是常用的数据结构模型,但是我的理解树是图的一个用于更具体的数据结构。今天温习的是树中比较简单、常用的二叉树。因为一个简单固定的结构更有利于查询,所以有了二叉查找树的概念。

简单介绍下🌲

研究依然以点-线模型的分析理解,不过树是从一个方向顺势的分支结构。这里可以是自上向下,也可以自下向上。

树的常见术语有几个:

  • 根节点
  • 子节点
  • 叶子节点
  • 子树
  • 路径
  • 键(这里是抽象主要的数据)

二叉树:

  • 子节点不超过两个
  • 左节点
  • 右节点

如果具备查找特性:

较小值在左,较大值在右

这里准备一组值来构建树:

[ 23, 45, 16, 37, 3, 99, 22 ]

然后我需要构建的树的成品是:

树

二、具体实现

1.首先需要构造一个节点对象,来表示节点这一个描述元素

class Node {
    constructor (data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    getData () {
        return this.data;
    }

    output() {
        console.log(this.data);
    }
}

主要包含:

  • data: 节点的键
  • left: 左节点
  • right: 右节点
  • getData: 获取键
  • output: 辅助输出函数

2.树的对象以及树的操作

class Tree {
    constructor () {
        // 根节点默认是 null
        this.root = null;
    }

    // 插入节点
    insert (data) {
        const node = new Node(data, null, null);

        if(this.root === null) {
            this.root = node;
        } else {
            let current = this.root;
            let parent = null;

            while(1) {
                parent = current;
                if(data < current.data) {

                    current = current.left;
                    if(current === null) {
                        parent.left = node;
                        break;
                    }
                } else {

                    current = current.right;
                    if(current === null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }

        return this;
    }

    // 中序遍历
    ascOrder (node) {
        if(node !== null) {
            this.ascOrder(node.left);
            node.output();
            this.ascOrder(node.right);
        }
    }

    // 先序遍历
    rootOrder (node) {
        if(node !== null) {
            node.output();
            this.rootOrder(node.left);
            this.rootOrder(node.right);
        }
    }

    // 后序遍历
    leafOrder (node) {
        if(node !== null) {
            this.leafOrder(node.left);
            this.leafOrder(node.right);
            node.output();
        }
    }

    // 执行路径的 action: left or right
    action (path) {
        let node = this.root;

        while(node[path] !== null) {
            node = node[path];
        }

        return node;
    }

    // 最小值
    min () {
        return this.action("left");
    }

    // 最大值
    max () {
        return this.action("right");
    }

    // 查找固定值
    find (data) {
        let node = this.root;

        while(node !== null) {
            if(data === node.data) {
                return node;
            } else if(data < node.data) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }
}

最后我在 Node 环境下测试,所以导出一下 Tree 类:

module.exports = Tree;

对于每一种排序后的结果是不一样的,可以用图形来表示一下:

中序遍历的过程:

中

先序遍历的过程:

先

后序遍历的过程:

后

其实看图是最直观的,其实算法这玩意最好的就是能够体会思想,然后根据实际的场景进行映射建立数据结构模型,以最优或更平衡的去解决问题。

测试代码如下:

const Tree = require("./binTree");

const log = s => console.log(s);

const tree = new Tree();
[23, 45, 16, 37, 3, 99, 22].forEach(n => tree.insert(n));

log("中-排序:");
tree.ascOrder(tree.root);

log("先-排序:");
tree.rootOrder(tree.root);

log("后-排序:");
tree.leafOrder(tree.root);

console.log("=====================");

log("最小值:");
log( tree.min() );

log("最大值:");
log( tree.max() );

log("查找 3:");
log( tree.find(3) );

log("查找 11:");
log( tree.find(11) );

终端跑的结果如下:

测试结果

本文链接:http://www.60sky.com/post/bst-tree-simple.html

-- EOF --

Comments