数据结构——树

摘要：首先，我们了解一下关于树的基本知识每一个树都包含一系列的父子关系的节点，每个节点都有一个父节点和若干的子节点零个或者多个没有父节点的节点称作是根节点一个节点可以有祖先和后代，子树由节点和他的后代构成，节点的一个属性是深度深度就是一个节点祖先

首先，我们了解一下关于树的基本知识：

每一个树都包含一系列的父子关系的节点，每个节点都有一个父节点和若干的子节点（零个 或者 多个）

没有父节点的节点称作是根节点

一个节点 可以有祖先 和 后代，子树由节点和他的后代构成，节点的一个属性是深度：深度就是一个节点祖先节点的数量

、树的高度是 所有节点深度中的最大值

二叉树：就是每个节点最多只能有两个节点 一个是左侧的节点 另一个是右侧的节点
二叉树搜索又是一种特殊的二叉树：只允许在左侧存储比父节点小的值 在右侧存储比父节点大的值，如下面的图所示：

由上图可以看出每一个节点都有两个指针，一个是指向左侧节点，一个是指向右侧节点

由此，我们可以发现有关树的规则：

树的左侧所有的节点的值肯定是小于根节点的值，树的右侧肯定是大于根节点的值

所以当删除一个拥有两个节点的节点时，为了遵循树的规律，需要找到节点右侧树的最小节点值

接下来，我们将通过javascript 创建一个二叉树类，二叉树是由一个个节点组成的，所以，在类中需要有一个节点类，根节点属性，还有基本的操作方法，分别是 插入，删除，遍历（前序，中序，后序），查询（最大值，最小值，和某一指定值）

//创建一个二叉树类
function BinarySearchTree(key){
   //节点类，有值，左节点，右节点三个公有属性
    var Node = function(key){
        this.key = key;
        this.left = null;
        this.rigth = null;
    }
    //在树中插入一个节点
    this.insert = function(newNode){
        if(root === null){
            root = newNode;
        }else{
            insertNode(root,newNode);
        }
     }
    //在树中查找一个键，如果键存在就返回true
    this.search = function(key){
        return searchNode(root,key);
    }
    //通过中序遍历所有的节点
    this.inOrderTraverse = function(){
        inOrderTraverseNode(root,callback);
    }
    //通过先序遍历所有的节点
    this.preOrderTravers = function(){
        preOrderTraverseNode(root,callback);
    }
    //通过后续遍历所有的节点
    this.postOrderTravers = function(){
        postOrderTraverseNode(root,callback);
    }
    //返回树中最小的键值
    this.min = function(){
       return minNode(root);
    }
    //返回树中最大的键值
    this.max = function(){
        return maxNode(root);
    }
    //从树中移除某一个键值
    this.remove = function(key){
        root = removeNode(root,key);
    }
    var root = null;
}

首先，实现 insert方法，大致思路是这样的：先判断 根节点是否为空，如果为空的话，就直接将新的节点作为根节点，如果不为空的话就调用一个插入节点的私有方法。

//创建插入节点的方法"
     this.insert = function(newNode){
        if(root === null){
            root = newNode;
        }else{
            insertNode(root,newNode);
        }
     }

insertNode的具体实现是这样的：

    var insertNode = function(node,newNode){
      if(newNode.key < node.key){
          if(node.left === null){
              node.left = newNode;
          }else{
              insertNode(node.left,newNode);
          }
      }else{
          if(node.right === null){
              node.right = newNode;
          }else{
              insertNode(node.right,newNode);
          }
      }
    }

函数解释：基本思想就是 将节点 他的左节点 和 他的右节点 看作是一个小的子树，先判断新节点的键值 是否小于节点的键值，如果小，就判断左节点是否为空，如果左节点为空，就将新的节点直接赋值给左节点，如果左节点不为空，就将左节点作为搜索比较的基点，调用自身再进行搜索比较（递归算法），相反如果大于节点的键值，再判断右节点是否为空，如果为空就直接将节点赋值给右节点，如果节点不为空同样调用自身。

接下来，我们定义 中序遍历的函数：
中序遍历是二叉树的一种遍历方式之一，实质上就是以从小到大的顺序访问二叉树，中序遍历的一种应用就是对树中存储的值进行从小到大的排列，中序遍历的辅助方法如下所述：

 var inOrderTraverseNode = function(node,callback){
        if(node !== null){
            inOrderTraverseNode(node.left,callback);（1）
            callback(node.key);（2）
            inOrderTraverseNode(node.right.callback);（3）
        }
    }

我以一个例子画了调用过程（简单粗糙，后期会修改）：

先序遍历的作用是打印树的一个结构化文档，他的辅助函数如下面所述：

    var preOrderTraverseNode = function(node,callback){
        if(node !== null){
            callback(node.key);
            preOrderTraverseNode(node.left,callback);
            preOrderTraverseNode(node.right,callback);
        }
    }

调用过程图 与 中序遍历相似

后序遍历的作用的计算树的子目录 和 父目录的所有文件所占空间的大小，其辅助函数的具体实现如下面所示：

 var postOrderTraverseNode = function(node,callback){
        if(node!== null){
            postOrderTraverseNode(node.left,callback);
            postOrderTraverseNode(node.right.callback);
            callback(node.key);
        }
    }

以上我们对三种遍历方式做了具体的实现，接下来我们完成对树中的所有值进行搜索。
基于构建树时所遵循的具体规则，我们可以看出在树的最左端是树的最小值，树的最右端就是树的最大值
那么寻找最小值的辅助函数是这样实现的：

    //搜索最小值时的搜索函数
    var minNode = function(node){
        //判断节点是否存在，如果存在就执行循环
        if(node){
            while(node && node.left !== null){
                node = node.left;
            }
            return node.key;
        }
        return null;
    }

函数解释:首先判断所传的节点（一般是根节点，看是否存在），如果存在的话就进行循环，直到找到最左端的节点（节点的左节点不存在，那么这就是最左边的节点），返回节点的所有值

寻找最大值的辅助函数是这样实现的：

//搜索树中的最大值函数
    var maxNode = function(node){
        if(node){
            while(node && node.right !== null){
                node = node.right;
            }
            return node.key;
        }
        return null;
     }

与寻找最小值相反，该函数是循环找最右边的节点

搜索特定值得辅助函数如下：

 //搜索特定值得辅助函数
     var searchNode = fucntion(node,key){
       var result;
       if(node === null){
           result = false;
       }
       if(key < node.key){
            searchNode(node.left,key);
       }else if(key > node.key){
            searchNode(node.right,key);
       }else{
           result = true;
       }
      return result; 
     }

函数解释：如果想要寻找的key值小于节点值就在节点的右侧树上寻找，在节点不为空的情况下回调该函数，缩小右侧树的寻找范围，最后节点如果为空就是没有找到，反之，找到；大于节点值同理

最后，我们完成移除节点的方法
根据子节点的数量，我们将节点分为三种情况：

叶子节点，既没有左节点也没有右节点

只有一个节点，左节点 或者 右节点

有两个节点左节点和右节点

针对上面三种情况，有三种删除节点的方法
对于第一种情况：因为叶子节点即没有左节点，也没有右节点，所以直接将该节点赋值为null就可以了，但是，单单这样是远远不够的，我们还需要对其相应的指针进行处理，对于叶子节点来说，我们需要处理叶子节点父节点的指针，使其的指针指向null，所以需要在执行完删除以后返回当前所基于的node节点,层层返回后实质上是以node节点为root的子树

对于第二种情况：移除只有一个节点时的节点，那么节点的左侧节点或者右侧节点就可以取代节点的位置

对于第三种情况：当移除有两个子节点的节点时，需要找到该节点右侧树上节点值最小的节点，并用该节点代替它，最后使其的右侧节点指向删除节点后的树

    //移除一个节点的辅助函数
     var removeNode = function(node,key){
       if(node === null){
           return null;
       }
       //寻找节点是key值的节点
       if(key < node.key){
           node.left = removeNode(node.left,key);
           return node;
       }else if(key > node.key){
           node.right = removeNode(node.right,key);
           return node;
       }else{
           //第一种情况——两个叶子节点都没有
           if(node.left === null && node.right === null){
               node = null;
               return node;
           }
           //第二种情况——只有一个叶子节点
           if(node.left === null){
              node = node.right;
              return node;
           }else if(node.right === null){
               node = node.left;
               return node;
           }
           //第三种情况——有两个叶子节点的节点
           var min = minNode(node.right);
           node.key = min;
           node.right = removeNode(node.right,min);
           return node;        
       }
     
     }

最后，我们详细解释一下第三种情况为什么会这样写，当该节点被删除的时候，我们需要寻找一个节点来代替，寻找哪个节点呢？肯定是寻找比他值大的节点，因为要保证左节点的值要小于寻找到的新值，所以我们锁定的目标是节点的右侧树，然而找的节点值还必须小于右节点的值，所以寻找右侧树的最小值，并将该节点删除

以上是我对树的理解和总结，本人接受各位同仁大神的指点，谢谢