数据结构与算法-树

非顺序数据结构我们之前学习的有散列表,现在,我们接着学习另一个非顺序数据结构,树。树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱,或是公司的组织架构图

位于树顶部的节点叫做根节点,它没有父节点。节点分为内部节点和外部节点,至少有一个子节点的节点成为内部节点,一个子节点也没有的成为外部节点也叫做叶节点。

一个节点可以有祖先和后代,一个节点(除了根节点)的祖先包括父节点、祖父节点、曾祖 父节点等。一个节点的后代包括子节点、孙子节点、曾孙节点等。

节点的一个属性是深度,节点的深度取决于它的祖先节点的数量。树的高度取决于所有节点深度的最大值。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。这些定 义有助于我们写出更高效的向/从树中插入、查找和删除节点的算法。二叉树在计算机科学中的 应用非常广泛。

二叉搜索树(BST)是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值, 在右侧节点存储(比父节点)大(或者等于)的值。

而我们今天主要研究的就是二叉搜索树

function Node(data, left, right){  
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
function show(){  
  return this.data;
}
function BST(){  
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder;
  this.getMin = getMin;
  this.getMax = getMax;
  this.find = find;
  this.remove = remove;
}
function insert(data){  
  var n = new Node(data, null, null);
  if(this.root == null){
    this.root = n;
  }else{
    var current = this.root;
    var parent;
    while(true){
      parent = current;
      if(data<current.data){
        current = current.left;
        if(current == null){
          parent.left = n;
          break;
        }

      }else{
        current = current.right;
        if(current == null){
          parent.right = n;
          break;
        }
      }
    }
  }
}
function inOrder(node){  
  if(!(node == null)){
    inOrder(node.left);
    console.log(node.data);
    inOrder(node.right);
  }
}
function getMin(root){  
  var current = this.root || root;
  while(!(current.left == null)){
    current = current.left;
  }
  return current.data;
}
function getMax(){  
  var current = this.root || root;
  while(!(current.right == null)){
    current = current.right;
  }
  return current.data;
}
function find(data){  
  var current = this.root;
  while(current != null){
    if(current.data == data){
      return current;
    }else if(data < current.data){
      current = current.left;
    }else{
      current = current.right;
    }
  }
  return null;
}
function remove(data){  
  removeNode(this.root, data);
}
function removeNode(node, data){  
  if(node == null){
    return null;
  }
  if(data == node.data){
    if(node.left == null && node.right == null){
      return null
    }
    if(node.left == null){
      return node.right;
    }
    if(node.right == null){
      return node.left;
    }
    var tempNode = getmin(node.right);
    node.data = tempNode.data;
    node.right = removeNode(node.right, tempNode.data);
    return node;
  }else if(data<node.data){
    node.left = removeNode(node.left, data);
    return node;
  }else{
    node.right = removeNode(node.right, data);
    return node;
  }
}

var nums = new BST();  
nums.insert(23);  
nums.insert(45);  
nums.insert(26);  
nums.insert(47);  
nums.insert(37);  
nums.insert(3);  
nums.insert(101);  
//console.log(nums.getMin())
nums.remove(3);  
nums.inOrder(nums.root);  

作者:@lsxlsxxslxsl