树结构

1. 非线性结构
2. 可以表示一对多的关系
3. 树相关术语

• 树：n个节点构成的有限集合，n为0时，称为空树
• 节点的度：节点的子树个数
• 树的度：树的所有节点中最大的度数
• 叶节点：度为0的节点
• 父节点：有子树的节点是其子树的根节点的父节点
• 子节点：父节点相对应的节点
• 兄弟节点：具有同一父节点的各节点彼此是兄弟节点
• 路径长度：路径所包含边的个数为路径的长度 -节点的层次：根节点在1层，其他任意节点的层数是其父节点层数加1
• 树的深度：所有节点的最大层数是树的深度

4. 二叉树：每个节点最多只能有2个子节点
5. 二叉树可以为空，若不为空，由根节点和左子树、右子树两个不相交的二叉树组成
6. 二叉树特性

• 第i层最大节点数：2^(i-1)
• 深度为k的二叉树最大节点总数：2^k-1
• 页节点个数+1为度为2的非页节点个数

7. 二叉搜索树（BST）

• 可以为空
• 不为空，左子树所有键值小于根节点键值，右子树所有键值大于根节点键值
• 左右子树本身也是二叉搜索树 ８．二叉搜索树封装

function BST(){
	this.root=null
  	function Node(key){
    	this.key=key
      	this.left=null
      	this.right=null
    }
  //插入方法
  	BSt.prototype.insert=function(key){
    	var newnode=new Node(key)
        if(this.root==null){
        	this.root=newnode
        }else{
        	this.insertNode(this.root,newnode)
        }
    }
  //插入递归内部方法
  	BST.prototype.insertNode=function(oldnode,newnode){
      	if(oldnode.key>newnode.key){
        	if(oldnode.left==null){
            	oldnode.left=newnode
            }else{
            	this.insertNode(oldnode.left,newnode)
            }
        }else{
        	if(oldnode.right==null){
            	oldnode.right=newnode
            }else{
            	this.insertNode(oldnode.right,newnode)
            }
        }
    }
  //先序遍历
  BST.prototyep.preOrderTranversal=function(handler){
  	this.prototype.preOrderTranversalNode(this.root,handler)
  }
  //先序遍历内部递归
  BST.prototype.preOrderTranversalNode=function(node,handler){
  	if(node!==null){
    	handler(node.key)
      	this.preOrderTranversalNode(node.left,handler)
      	this.preOrderTranversalNode(node.right,handler)
    }
  }
  //中序遍历
  BST.prototype.midOrderTranversal=function(handler){
  	this.midOrderTranversalNode(this.root,handler)
  }
  //中序遍历内部递归
  BST.prototype.midOrderTranversalNode=function(node,handler){
  	if(node!==null){
    	this.midOrderTranversalNode(node.left,handler)
      	handler(node.key)
      	this.midOrderTranversalNode(node.right,handler)
    }
  }
  //后序遍历
  BST.prototype.postOrderTranversal=function(handler){
  	this.postOrderTranversalNode(this.root,handler)
  }
  BST.prototype.postOrderTranversalNode=function(node,handler){
  	if(node!==null){
    	this.postOrderTranversalNode(node.left,handler)
      	this.postOrderTranversalNode(node.right,handler)
      	handler(node.key)
    }
  }
  //最大值
  BST.prototype.min=function(){
  	var node=this.root
    while(node.left!==null){
    	node=node.left
    }
    return node.key
  }
  //最小值
  BST.prototype.max=function(){
  	var node=this.root
    while(node.right!==null){
    	node=node.right
    }
    return node.key
  }
  //搜索方法
  BST.prototype.search(key){
  	var node=this.root
    while(node!==null){
    	if(key<node.key){
        	node=node.left
        }else if(key>node.key){
        	node=node.right
        }else{
        	return true
        }
    }
    return false
  }
  //删除方法
  BST.prototype.remove=function(key){
  	var current=this.root
    var parent=null
    var isLeft=true
    //查找
    while(current.key!==key){
    	if(key<current.key){
        	this.isLeft=true
          	current=current.left
        }else{
        	this.isLeft=false
          	current=current.right
        }
      if(current.key==null) return false
    }
    //删除叶子节点
    if(current.left==null && current.right==null){
    	if(current==this.null){
        	this.root=null
        }else if(isLeft){
        	parrent.left=null
        }else{
        	parrent.right=null
        }
    }
    //删除带一个子节点的节点
    if(current.left==null){
      	if(current==this.root){
        	 this.root=current.right
        }else if(isLeft){
        	parent.left=current.right
        }else{
        	parent.right=current.right
        }
    }else if(current.right=null){
      	if(current==this.root){
        	this.root=current.left
        } else if(isLeft){
        	parent.left=current.left
        }else{
        	parent.right=current.left
        }
    }else{
    	var successor=this.getSuccessor(current)
        if(current==this.root){
        	this.root=successor
        }else if(isLeft){
        	parent.left=successor
        }else{
        	parent.right=successor
        }
      	successor.left=current.left
    }
  }
  //查找后继方法
  BST.prototype.getSuccessor=function(delnode){
  	var successor=delnode
    var current=delnode.right
    var successorParent=delnode
    while(current!==null){
    	successorParent=successor
      	successor=current
      	current=current.left
    }
    if(successor!==delnode.right){
    	successorParent.left=successor.right
      	successor.right=delnode.right
    }
    return successor
  }
}