<Day7- 樹Tree>

• 非循序資料結構, 一種分層資料的抽象模型
• 架構
  • 根節點- 唯一沒有縛結點 - 第0層
  • 內部節點- 少有一個子結點
  • 外部節點= 葉節點- 沒有子結點
  • 子樹- 由節點和他的後代構成
  • 樹的高度 = 節點深度最大值
• 應用
  • • 二元樹 應用廣泛 ex 二元搜尋樹BST

BST

• 節點最多只能有兩個子節點

• 規則：在左側節點存放比縛結點小的 在右邊存放比縛結點大(或等於)的

• 每個節點包含兩個指位器(邊)

• 樹的遍歷：訪問樹每個節點並對他們進行某種操作的過程

  • 方法 visitor pattern
    • 中序 以升冪順序訪問BST 從最小到最大
    • 先序 以優先於後代節點的順序訪問每個節點 ex列印一個結構化文件
    • 後序 先訪問節點的後代 在訪問節點本身 ex 計算一個目錄和他的子目錄中所有檔案所佔的大小

• 搜尋樹中的值

  • min, max ,key值

• 移除

  1. 一個葉節點
  2. 只有一個子節點的節點
  3. 有兩個子節點的節點

• BST缺點： 很可能因為資料關係 樹的一條分支很多層 其他分支卻只有幾層

• -> AVL樹

• 其他： 紅黑樹, 堆積樹

//建立BST

function BinarySearchTree(){

  //setup Node & root
  let Node = function(key){
    this.key = key
    this.left = null
    this.right = null
  }
  let root = null

  //function
  this.insert = function(key){
    let newNode = new Node()
    let 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)
        }
      }
    }

    if (root === null){
      root = newNode
    }else {
      insertNode(root,newNode)
    }
  }
  
  //遍歷
  //中序
  this.inOrderTraverse = function(callback){
    inOrderTraverseNode(root,callback)
  }
  //先序
  this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root,callback)
  }
  this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback)
  }
  //搜尋
  this.min = () => minNode(root)
  this.max  = ()=> maxNode(root)
  this.search = (key) => searchNode(root, key)

  //移除
  this.remove = function(key){
    root = removeNode(root, key)
  }

  //function
  let inOrderTraverseNode = function(node, callback){
    if (node !== null){
      inOrderTraverseNode(node.left,callback)
      callback(node.key)
      inOrderTraverseNode(node.right, callback)
    }
  }
  let preOrderTraverseNode = function(node, callback){
    if (node !== null){
      callback(node.key)
      preOrderTraverseNode(node.left, callback)
      preOrderTraverseNode(node.right, callback)
    }
  }
  let postOrderTraverseNode = function(node, callback){
    if (node !== null){
      postOrderTraverseNode(node.left, callback)
      postOrderTraverseNode(node.right, callback)
      callback(node.key)
    }
  }
  let minNode = function(node){
    if (node){
      while ( node && node.left !== null){
        node = node.left
      }
       return node.key
    } return null
  } 
  let maxNode = function(node){
    if(node){
      while (node && node.right !== null){
        node = node.right
      }
      return node.key
    }return null
  }
  let searchNode = function(node, key){

    if(node === null){
      return false
    }
    if(key < node.key){
      return searchNode(node.left, key)
    }else if(key > node.key){
      return searchNode(node.right, key)
    }else {
      return true
    }
  }
  let findMinNode = function(node){
    if (node){
      while ( node && node.left !== null){
        node = node.left
      }
       return node
    } return null
  } 
  let removeNode = function(node,key){
    if (node === null){
      return null
    }

    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 {

      //1 葉節點
      if (node.left === null && node.right === null){
        node = null
        return node
      }
      //2 單一子節點
      if (node.left === null){
        node = node.right
        return node
      } else if (node.right === null){
        node = node.left
        return node
      }
      //3 兩個子節點
      let aux = findMinNode(node.right)
      node.key = aux.key
      node.right = removeNode(node.right , aux.key)
      return node
    
    }
  }
  
}



//使用
function printNode(value){
  console.log(value );
}
tree.inOrderTraverse(printNode)
......