在使用java script实现基本的数据结构中，练习了好几周，对基本的数据结构如 栈、队列、链表、集合、哈希表、树、图等内容进行了总结并且写了笔记和代码。

在 github中可以看到  点击查看，可以关注一下我哈。

 

树的基本术语

二叉树节点的存储结构

创建一个二叉搜索树

二叉树的先序、中序、后续遍历算法

二叉树的非递归先序、中序、后续遍历算法。

 

 

 

文章对树了解的不多的人有点不友好，这里简单介绍（从书上抄下来）那些基本的一点概念吧。

 

看下面这个示意图

 

 

 

树的基本术语：

结点：A、B、C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。例如，A结点不仅包含数据元素A、还包含3个指向子树的指针。

结点的度：结点拥有的子树个数或者分支的个数，例如A结点有3棵子树，所以A结点的度为3.

树的度：树中各结点度的最大值。如例子中结点度最大为3（A、D结点）。最小为0（F、G、I、J、K、L、M），所以树的度为3。

叶子节点：又叫做终端节点，指度为0的节点，F、G、I、J、K、L、M节点都是叶子节点。

孩子：结点的子树的根，如A节点的孩子为B、C、D。

双亲：与孩子的定义对应，如B C D结点的双亲都是A。

兄弟：同一个双亲的孩子之间互为兄弟。如B、C、D互为兄弟，因为它们都是A节点的孩子。

祖先：从根到某节点的路径上的所有结点，都是这个节点的祖先。如K的祖先是A B E，因为从A到K的路径为 A---B---E--K。

子孙: 以某节点为根的子树中的所有结点，都是该结点的子孙。如D的子孙为H I J M。

层次：从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。

树的高度（或者深度）：树中结点的最大层次，如例子中的树共有4层，所以高度为4.

 

理解了上面的树一些基本一些的概念后，我们来看一下什么是二叉树。

1）每个结点最多只有两棵子树，即二叉树中的节点的度只能为0、1、2

2) 子树有左右之分，不能颠倒。

 

以下二叉树的5中基本状态

 

 

构造一个二叉树的节点存储结构

我们会发现，二叉树中的存储结构一个是值，一个是左边有一个，右边有一个。他们分别叫左孩子/左子树  右孩子/右子树。

所以我们会很容易的写出来一个节点的构造函数。

// 树的结构
class BTNode {
  constructor() {
    this.key = key;
    this.lchild = null;
    this.rchild = null;
  }
}

 

实现一个二叉搜索树 / 二叉排序树

看一下定义

二叉排序树或者是空树，或者是满足以下性质的二叉树。

1) 若它的左子树不空，则左子树上的所有关键字的值均小于根关键字的值。

2）若它的右子树不空，则右子树上所有关键字的值均大于根关键字的值。

3）左右子树又是一棵二叉排序树。

 

举个例子

假如要插入一堆数字，数字为 20 10 5 15 13 18 17 30

 

 

 

 

 那么用代码如何实现呢？

let BST = (function () {

  let ROOT = Symbol();

  // 节点结构
  let BTNode = class {
    constructor(key) {
      this.key = key;
      this.lchild = null;
      this.rchild = null;
    }
  }

  // 递归插入节点
  let recursionInsert = function (root, node) {
    if (node.key < root.key) {
      if (root.lchild) {
        recursionInsert(root.lchild, node);
      } else {
        root.lchild = node;
      }
    } else {
      if (root.rchild) {
        recursionInsert(root.rchild, node);
      } else {
        root.rchild = node;
      }
    }
  }

  // 二叉搜索树类
  return class {
    constructor() {
      this[ROOT] = null;
    }

    // 插入
    insert(key) {
      let node = new BTNode(key);
      let root = this[ROOT];
      if (!root) {
        this[ROOT] = node;
        return;
      }
      // 递归插入
      recursionInsert(root, node);
    }
  }

})();


let bst = new BST();


bst.insert(20);
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(13);
bst.insert(18);
bst.insert(17);
bst.insert(30);

console.log(bst);

 

 在浏览器中一层一层的展开看看是否和我们的一样。

 

二叉树的遍历算法 

二叉树的遍历算法，二叉树的遍历就是按照某种规则将二叉树中的所有数据都访问一遍。

二叉树的遍历方式有先序遍历、中序遍历、后续遍历和层次遍历，很多算法都是基于这几种遍历方式衍生出来的。

递归方式的具体的代码实现

let BST = (function () {

  let ROOT = Symbol();

  // 节点结构
  let BTNode = class {
    constructor(key) {
      this.key = key;
      this.lchild = null;
      this.rchild = null;
    }
  }

  // 递归插入节点
  let recursionInsert = function (root, node) {
    if (node.key < root.key) {
      if (root.lchild) {
        recursionInsert(root.lchild, node);
      } else {
        root.lchild = node;
      }
    } else {
      if (root.rchild) {
        recursionInsert(root.rchild, node);
      } else {
        root.rchild = node;
      }
    }
  };

  // 用于中序遍历二叉树的方法
  let inorderTraversal = function (root, arr) {
    if (!root) return;