[数据结构与算法]JS简单实现树结构

本文借鉴于此

一、树的基本概念

1、树： 树是由n(n>0)个有限节点组成的一个具有层次关系的集合，它具有以下的特点：

每个节点有0个或多个结点
没有父节点的节点叫做根节点
每个非根节点有且只有一个父节点
除了根节点外，每个子节点可以分为多个不相交的子树

2、节点的度： 节点拥有的子树个数，例如图中节点A的度为2，节点H的度为1

3、树的度： 树的最大节点的度，例如图中最大的节点B的度为3，树的度为3

4、叶节点： 度为0的节点，图中K，J，F，L，O，P都是叶节点

5、父节点： 一个含有子节点的节点。图中A节点就是B 和 C的父节点

6、子节点： 一个含有子树的根节点的节点，把子树的根节点叫做该节点的该节点的子节点，图中节点G和节点H为节点C的子节点

7、兄弟节点： 具有相同父节点的节点，节点B和节点C就是兄弟节点

8、祖先节点： 从根到该节点所经分支的所有节点，图中节点A，B，E是节点J的祖先节点

9、子孙节点： 以某节点为根节点的子树中所有节点，图中节点D、E、F、J、K、I是节点B的子孙节点

10、节点层次： 以根开始，根为第一层，根的子节点为第二层…，如果一个节点在第n层，则它的子树的根节点在n+1层

11、深度或高度： 树中节点的最大层次

12、森林： 由n棵互不相交的树的集合，例如图中节点A去掉，以节点B为根的树和以节点C为根的树组成的集合就叫做森林

二、二叉树

1、二叉树的概念

（1）二叉树：是每个节点最多只有两个子树的树结构，这两种子树通常叫做左子树和右子树，具有左右次序，不能颠倒

（2）二叉树的特点：

a、二叉树的第i层至多有2^（i-1）个节点（i>= 1）
b、高度为k的二叉树至多有2^k-1个节点（k>=1）
c、非空二叉树中，叶子结点数为n0,度为2的节点数为n2，则n0 = n2 + 1
d、具有n个节点的完全二叉树的深度为不大于log2n的最大整数

特点 c 推导：

	设n为二叉树的总节点数，n0为二叉树中叶子节点数，n1为二叉树中度为1的节点数，n2为二叉树中度为2的节点数
	可得  n = n0 + n1 + n2
	根据二叉树中的连接线数可再得一个关系  (总线数)n - 1 = n1 + 2n2
	求方程可得   n0 = n2 + 1

2、满二叉树

在一棵二叉树中，所有的分支节点都存在左子树和右子树，并且所有的叶子结点都在同一层上

3、完全二叉树

对于一棵具有n个节点的二叉树按层序编号，如果编号为 i （i <= i <= n）的节点与同样深度的满二叉树中编号为i的结点在二叉树中的位置

完全相同，则这棵二叉树称为完全二叉树

三、二叉搜索树

1、二叉搜索树的性质

（1）若任意节点的左子树不为空，则左子树上所有节点的值都小于它根节点的值
（2）若任意节点的右子树不为空，则右子树上所有节点的值都大于它根节点的值
（3）任意节点的左右子树也分别为二叉搜索树
（4）没有值相等的节点

2、定义节点类和二叉树类

（1）由二叉树的定义，我们可以对节点定义代表存储左子树和右子树的属性

function Node(data) {
    this.data = data
    this.leftChild = null
    this.rightChild = null
}

对于二叉树来说，定义一个根节点的属性

function BinaryTree() {
    this.root = null//根结点
}

例如下图是Node环境输出的二叉树的结构，一个对象嵌套着一个对象

3、插入节点

由二叉搜索树的性质，可以得到插入的过程：

1、二叉树为空，新节点为根节点
2、二叉树不为空，由根节点开始，新节点的值小于当前节点，往左子树递归，若大于当前节点，往右子树递归，直到为null的时候插入

BinaryTree.prototype.inserNode = function(data) {
    var newNode = new Node(data);  // 构造Node的实例
  
    if (this.root === null) {  // 根节点为空, 新节点为根节点
      this.root = newNode;
    } else {
      insert(this.root, newNode);
    }
};


var insert = function(node, newNode) {
    if (newNode.data < node.data) {
      insertChild(node, 'leftChild', newNode);
    } else {
      insertChild(node, 'rightChild', newNode);
    }
};


var insertChild = function(node, childName, newNode) {
    if (node[childName] === null) {
      node[childName] = newNode;
    } else {
      insert(node[childName], newNode);
    }
};

4、判断空树

判断空树很简单，当root为null的时候，树就是空树，返回true

BinaryTree.prototype.isBinaryTreeEmpty = funciton() {
    if(this.root) {
        return false
    }

    return true
}

5、二叉搜索树的高度

高度是树的最大层次，可以用递归的方式，分别计算左子树的高度和右子树的高度，然后区取他们之间的最大值

var treeDepth = function(node) {
    var i,j;

    if(node === null) {//空树，高度为0
        return 0
    }

    if(node.leftChild) { //计算左子树的高度
        i = treeDepth(node.leftChild)
    } else {
        i = 0
    }

    if(node.rightChild) {
        j = treeDepth(node.rightChild)
    } else {
        j = 0
    }
    return i > j? i+1 : j+1
}

BinaryTree.prototype.binaryTreeDepth = function() {
    return treeDepth(this.root)
}

6、遍历

（1）先序遍历（深度优先遍历）：先访问根节点，其次左子树，再右子树

var preOrderTraverseNode = function(node,callback) {
    checkCallback(callback) //检查callback参数是否为函数的方法

    if(node) {
        callback(node)
        preOrderTraverseNode(node.leftChild,callback)
        preOrderTraverseNode(node.rightChild,callback)
    }
}

BinaryTree.prototype.preOrderTraverseNode = function(callback) {
    preOrderTraverseNode(this.root,callback)
}

var checkCallback = function(callback) {
    if(!callback || typeof callback !== 'function') {
        throw ('Callback function error.')
    }
}

（2）中序遍历：先访问左子树，其次是根节点，最后右子树

var inOrderTraverseNode = function(node,callback) {
    checkCallback(callback)

    if(node) {
        inOrderTraverseNode(node.leftChild,callback)
        callback(node)
        inOrderTraverseNode(node.rightChild,callback)
    }
}

BinaryTree.prototype.inOrderTraverseNode = function(callback) {
    inOrderTraverseNode(this.root,callback)
}

（3）后序遍历：先访问左子树，其次是根节点，最后右子树

var postOrderTraverseNode = function(node, callback) {
  checkCallback(callback);

  if (node) {
    postOrderTraverseNode(node.leftChild, callback);
    postOrderTraverseNode(node.rightChild, callback);
    callback(node);
  }
};

BinaryTree.prototype.postOrderTraverse = function(callback) {
  postOrderTraverseNode(this.root, callback);
};

（4）层次遍历（广度优先遍历）：层次遍历是指同深度节点从左到右一次遍历，借助队列，从根节点开始，入列，判断队列是否为空，若不为空，队首出列，将队首的左右子树根节点入列，不断循环至队列的元素全部出列

BinaryTree.prototype.levelOrderTraverse = function(callback) {
    var queue = [], e = null;

    checkCallback(callback)

    if(this.root) {
        queue.push(this.root)
    }

    while(queue.length > 0 ) {
        e = queue.shift()
        callback(e)

        if(e.leftChild) {
            queue.push(e.leftChild)
        }

        if(e.rightChild) {
            queue.push(e.rightChild)
        }
    }
}