投稿015期 | 数据结构与算法

这些都是数据结构与算法，一部分方法是团队其他成员实现的，一部分我自己做的，有什么其他实现方法或错误，欢迎各位大佬指点，感谢。

1.树有什么特点，什么是二叉树和二叉搜索树（BST: Binary Search Tree）？
2.生活中常见的例子有哪些？

解析：

1. 树有什么特点，什么是二叉树和二叉搜索树：

• 树是一种非线性的数据结构，以分层方式存储数据，用来表示有层级关系的数据。

• 每棵树至多只有一个根结点，根结点会有很多子节点，每个子节点只有一个父结点。

• 父结点和子节点是相对的。

2. 生活中的例子：
   如：家谱、公司组织架构图。

• insert(key)：向树中插入一个新的键；
• search(key)：树中查找一个键，如果节点存在返回true，不存在返回false；
• min()：返回树中最小的值/键；
• max()：返回树中最大的值/键；
• remove(key)：移除某个键；

提示：所谓的键对应于之前章节所学的节点（Node）

class Node {
    constructor(key){
 this.key = key
 this.left = null
 this.right = null
    }
}
class BST {
    constructor(){
 this.root = null
    }
    
    insertNode (node, newNode){
 if(newNode.key < node.key){
     if(node.left === null && node.right === null){
  node.left = newNode
     }else if(node.left !== null && node.right === null){
  node.right = newNode
     }else{
  this.insertNode(node.left, newNode)
     }
 }else{
     if(node.left === null && node.right === null){
  node.left = newNode
     }else if(node.left !== null && node.right === null){
  node.right = newNode
     }else{
  this.insertNode(node.right, newNode)
     }
 }
    }
    
    insert (key){
 let newNode = new Node(key)
 if(this.root === null){
     this.root = newNode
 }else{
     this.insertNode(this.root, newNode)
 }
    }
    searchNode (node, key){
 if(node === null) return false
 if(key < node.key){
     return this.searchNode(node.left, key)
 }else if(key > node.key){
     return this.searchNode(node.right, key)
 }else{
     return true
 }
    }
    
    search (key){
 return this.searchNode(this.root, key)
    }
    
    min (){
 let node = this.root
 if(node === null) return null
 while(node && node.left !== null){
     node = node.left
 }
 return node.key
    }
    
    max (){
 let node = this.root
 if(node === null) return null
 while(node && node.right !== null){
     node = node.right
 }
 return node.key
    }
    
    findMinNode (node){
 if(node === null) return null
 while(node && node.left !== null){
     node = node.left
 }   
 return node
    }
    
    removeNode (node, key){
 if(node === null) return null
 if(key < node.key){
     node.left = this.removeNode(node.left, key)
     return node
 }else if(key > node.key){
     node.right = this.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
     }
     // 3.有两个子节点
     let curNode = this.findMinNode(node.right)
     node.key = curNode.key
     node.right = this.removeNode(node.right, curNode.key)
     return node
 }
    }
    
    remove (key){
 if(this.root === null) return null
 this.root = this.removeNode(this.root, key)
    }
}

// 1. 先序
BST.prototype.preOrderTraverseNode = function(node, callback){
    if(node !== null){
 callback(node.key)
 this.preOrderTraverseNode(node.left, callback)
 this.preOrderTraverseNode(node.right, callback)
    }
}
BST.prototype.preOrderTraverse = function(callback){
    this.preOrderTraverseNode(this.root, callback)
}

// 2. 中序
BST.prototype.inOrderTraverseNode = function(node, callback){
    if(node !== null){
 this.inOrderTraverseNode(node.left, callback)
 callback(node.key)
 this.inOrderTraverseNode(node.right, callback)
    }
}
BST.prototype.inOrderTraverse = function(callback){
    this.inOrderTraverseNode(this.root, callback)
}

// 3. 后序
BST.prototype.postOrderTraverseNode = function(node, callback){
    if(node !== null){
 this.postOrderTraverseNode(node.left, callback)
 this.postOrderTraverseNode(node.right, callback)
 callback(node.key)
    }
}
BST.prototype.postOrderTraverse = function(callback){
    this.postOrderTraverseNode(this.root, callback)
}

    3
   / 
  9  20
     / 
    15  7

[
  [3],
  [9, 20],
  [15, 7]
]

BST.prototype.printLevelOrder = function (root, arr = [], i = 0){
    if (root && (root.key || root.key === 0)) {
      !arr[i] && (arr[i] = [])
      arr[i].push(root.key)
      i++
      root.left && this.printLevelOrder(root.left, arr, i)
      root.right && this.printLevelOrder(root.right, arr, i)
    }
    return arr
}

BST.prototype.printLevelOrder = function (){
    if(this.root === null) return []
    let result = [], queue = [this.root]
    while(true){
 let len = queue.length, arr = []
 while(len > 0){
     console.log(queue)
     let node = queue.shift()
     len -= 1
     arr.push(node.key)
     if(node.left !== null) queue.push(node.left)
     if(node.right !== null) queue.push(node.right)
 }
 if(arr.length === 0) return result
 result.push([...arr])
    }
}

输入:
    2
   / 
  1   3
输出: true

输入:
    5
   / 
  1   4
     / 
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

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


function isValidBST(root) {};

function isValidBST(root) {
    let arr = []
    function inOrderTraverse(node){
 if(node === null) return;
 node.left && inOrderTraverse(node.left);
 arr.push(node.val);
 node.right && inOrderTraverse(node.right);
    }
    inOrderTraverse(root)
    for(let i = 0; i < arr.length - 1; i++){
 if(arr[i] >= arr[i+1]) return false
    }
    return true
};