二叉搜索树

二叉搜索树

二叉搜索数：父节点值大于左儿子的值小于右儿子的值

function Node(val) {
       this.data = val;
       this.left = null;
       this.right = null;
   }

   function BinarySearchTree() {
       this.root = null;
   }

   BinarySearchTree.prototype = {
       insert: function(val, node) {
           if (this.root == null) {
               this.root = new Node(val);
               return ;
           }

           if (node.data > val) {
               if (node.left == null) {
                   node.left = new Node(val);
               } else {
                  this.insert(val, node.left);
               }
           } else if (node.data < val) {
               if (node.right == null) {
                   node.right = new Node(val);
               } else {
                   this.insert(val, node.right);
               }
           } else {
               console.log('节点已经存在');
           }
       },
       insert2: function(val) {
           if (this.root == null) {
               this.root = new Node(val);
               return ;
           }

           var tmpNode = this.root;
           while (true) {
               if (tmpNode.data > val) {
                   if (tmpNode.left) {
                       tmpNode = tmpNode.left;
                   } else {
                       tmpNode.left = new Node(val);
                       return ;
                   }
               } else if (tmpNode.data < val) {
                   if (tmpNode.right) {
                       tmpNode = tmpNode.right;
                   } else {
                       tmpNode.right = new Node(val);
                       return ;
                   }
               } else {
                   console.log('节点已经存在');
                   return;
               }
           }
       },
       preOrderTraverseNode: function(node) {
           if (node) {
               console.log(node.data);
               this.preOrderTraverseNode(node.left);
               this.preOrderTraverseNode(node.right);
           }
       },
       inOrderTraverseNode: function(node) {
           if (node) {
               this.inOrderTraverseNode(node.left);
               console.log(node.data);
               this.inOrderTraverseNode(node.right);
           }
       },
       postOrderTraverseNode: function(node) {
           if (node) {
               this.postOrderTraverseNode(node.left);
               this.postOrderTraverseNode(node.right);
               console.log(node.data);
           }
       },
       breadthTraverseNode: function() {
           var stack = [this.root];

           while (stack.length > 0) {
               var tmpNode = stack.shift();
               console.log(tmpNode.data);

               if (tmpNode.left)
                   stack.push(tmpNode.left);

               if (tmpNode.right)
                   stack.push(tmpNode.right);
           }
       },
       minNode: function() {
           if (!this.root)
               return null;

           var tmpNode = this.root;
           while (tmpNode && tmpNode.left) {
               tmpNode = tmpNode.left;
           }
           return tmpNode.data;
       },
       maxNode: function() {
           if (!this.root)
               return null;

           var tmpNode = this.root;
           while (tmpNode && tmpNode.right) {
               tmpNode = tmpNode.right;
           }
           return tmpNode.data;
       },
       searchNodeWithData: function(val, node) {
           if (!node)
               return null;

           if (node.data > val) {
               return this.searchNodeWithData(val, node.left);
           } else if (node.data < val) {
               return this.searchNodeWithData(val, node.right);
           } else {
               return node;
           }

           return null;
       },
       // 删除的节点有左右孩子，则取右孩子的最小值，左孩子的最大值
       delNodeWithData: function(val, node) {
           if (!node)
               return null;

           if (node.data > val) {
               node.left = this.delNodeWithData(val, node.left);
           } else if (node.data < val) {
               node.right = this.delNodeWithData(val, node.right);
           } else {
               if (node.left && node.right) {
                   var tmpNode = this._findMinNode(node.right);
                   node.data = tmpNode.data;
                   node.right = this.delNodeWithData(node.data, node.right);
               } else {
                   if (!node.left) {
                       node = node.right;
                   } else if (!node.right) {
                       node = node.left;
                   } else {
                       node = null;
                   }
               }
           }

           return node;
       },
       _findMinNode: function(node) {
           if (!node)
               return null;

           while (node && node.right) {
               node = node.right;
           }

           return node;
       }

   }

   var bst = new BinarySearchTree();
   // bst.insert(10, bst.root);
   // bst.insert(20, bst.root);
   // bst.insert(5, bst.root);
   bst.insert2(10);
   bst.insert2(20);
   bst.insert2(5);
   bst.insert2(15);
   bst.insert2(29);
   bst.insert2(25);