关于javascript:javascript学习数据结构二叉树图

39次阅读

共计 6584 个字符，预计需要花费 17 分钟才能阅读完成。

二叉树和二叉查找树

树是一种非线性的数据结构，以分层的形式存储数据。树被用来存储具备层级关系的数据，比方文件系统中的文件；树还被用来存储 有序列表。

二叉树是一种非凡的树，它的子节点个数不超过两个。二叉树具备一些非凡的计算性质，使得在它们之上的一些操作异样高效沿着一组特定的边，能够从一个节点走到另外一个与它不间接相连的节点。从一个节点到另一个节点的这一组边称为门路，树能够分为几个档次，根节点是第 0 层，它的子节点是第 1 层，子节点的子节点是第 2 层，以此类推。树中任何一层的节点能够都看做是子树的根，该子树蕴含根节点的子节点，子节点的子节点等。咱们定义树的层数就是树的深度每个节点都有一个与之相干的值，该值有时被称为键。一个节点到另一个节点的途程称为门路

二叉树每个节点的子节点不容许超过两个。通过将子节点的个数限定为 2，能够写出高效的程序在树中插入、查找和删除数据一个父节点的两个子节点别离称为左节点和右节点。在一些二叉树的实现中，左节点蕴含一组特定的值，右节点蕴含另一组特定的值。

当思考某种非凡的二叉树，比方二叉查找树时，确定子节点十分重要。
二叉查找树是一种非凡的二叉树，绝对较小的值保留在左节点中，较大的值保留在右节点中。这一个性使得查找的效率很高

上面实现二叉查找树

Node 类的定义

每一个节点都含有三个元素

  1. 键值 data
  2. 左节点指针 left

  3. 右节点指针 right

    class Node{constructor(data, left, right){
    this.data = data;
    this.left = left;
    this.right = right;
  }
  show(){return this.data}
}

二叉查找树类

初始化根节点 root 为 null

class BST{
  root=null
  constructor(){}
}

insert() 办法，用来向树中退出新节点 

  insert(data) {let node = new Node(data, null, null)
        if (this.root == null) {this.root = node} else {
            let current = this.root
            let parent
            while (true) {
                parent = current
                if (data < current.data) {
                    current = current.left
                    if (current == null) {
                        parent.left = node
                        break;
                    }
                } else {
                    current = current.right
                    if (current == null) {
                        parent.right = node
                        break;
                    }
                }
            }
        }
    }

遍历二叉查找树

有三种遍历 BST 的形式：中序、先序和后序。中序遍历依照节点上的键值，以升序拜访 BST 上的所有节点。先序遍历先拜访根节点，而后以同样形式拜访左子树和右子树。后序遍历先拜访叶子节点，从左子树到右子树，再到根节点。

先序遍历 preOrder()

preOrder(node) {if (node != null) {console.log(node.show())
            this.inOrder(node.left)
            this.inOrder(node.right)
        }
    }

中序遍历 inOrder()

  inOrder(node) {if (node != null) {this.inOrder(node.left)
            console.log(node.show())
            this.inOrder(node.right)
        }
    }

后序遍历 postOrder()

postOrder(node) {if (node != null) {this.inOrder(node.left)
            this.inOrder(node.right)
            console.log(node.show())
        }
    }

getMin() 查找最小值

最小值在最右边，统一遍历右边个元素，查找到最初一个元素，就是最小值 

getMin() {
        let node = this.root
        while (node.left != null) {node = node.left}
        return node.data
    }

getMax() 查找最大值

最大值在最左边，统一遍历左边个元素，查找到最初一个元素，就是最大值 

getMax() {
        let node = this.root
        while (node.right != null) {node = node.right}
        return node.data
    }

find() 查找指定值的节点 

find(data) {
        let node = this.root
        let result = null
        while (node) {if (node.data == data) {
                result = node
                break
            }
            if (node.data < data) {node = node.right} else {node = node.left}
        }

从二叉查找树上删除节点

BST 上删除节点的操作最简单，其复杂程度取决于删除哪个节点。如果删除没有子节点的节点，那么非常简单，间接移除节点即可。如果节点只有一个子节点，不论是左子节点还是右子节点，就变得略微有点简单了，须要将父节点指向删除节点的指针指向对应剩下的左子节点活右子节点。删除蕴含两个子节点的节点最简单，须要将右子树中最小的节点或左子树中最小的节点将要被移除的节点替换。
为了治理删除操作的复杂度，咱们应用递归操作，同时定义两个办法：remove() 和 removeNode()。

remove(data) {this.root = this.removeNode(this.root, data)
    }

    removeNode(node, data) {if (node == null) {return null}
        if (node.data == data) {if (node.left == null && node.right == null) {return null}
            if (node.left == null) {return node.right}
            if (node.right !== null) {return node.left}
            let smallestNode = this.getSmallest(node.right)
            node.data = smallestNode.data
            this.removeNode(node.right, smallestNode.data)
            return node
        } else if (node.data < data) {node.right = this.removeNode(node.right.data)
        } else {node.left = this.removeNode(node.left.data)
        }
    }
    getSmallest(node) {while (node.left != null) {node = node.left}
        return node
    }

残缺代码 

class Node {constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show() {return this.data}
}
class BST {
    root = null
    constructor() {}
    insert(data) {let node = new Node(data, null, null)
        if (this.root == null) {this.root = node} else {
            let current = this.root
            let parent
            while (true) {
                parent = current
                if (data < current.data) {
                    current = current.left
                    if (current == null) {
                        parent.left = node
                        break;
                    }
                } else {
                    current = current.right
                    if (current == null) {
                        parent.right = node
                        break;
                    }
                }
            }
        }
    }
    inOrder(node) {if (node != null) {this.inOrder(node.left)
            console.log(node.show())
            this.inOrder(node.right)
        }
    }
    preOrder(node) {if (node != null) {console.log(node.show())
            this.inOrder(node.left)
            this.inOrder(node.right)
        }
    }
    postOrder(node) {if (node != null) {this.inOrder(node.left)
            this.inOrder(node.right)
            console.log(node.show())
        }
    }
    getMin() {
        let node = this.root
        while (node.left != null) {node = node.left}
        return node.data
    }
    getMax() {
        let node = this.root
        while (node.right != null) {node = node.right}
        return node.data
    }
    find(data) {
        let node = this.root
        let result = null
        while (node) {if (node.data == data) {
                result = node
                break
            }
            if (node.data < data) {node = node.right} else {node = node.left}
        }
        return result
    }
    remove(data) {this.root = this.removeNode(this.root, data)
    }
    removeNode(node, data) {if (node == null) {return null}
        if (node.data == data) {if (node.left == null && node.right == null) {return null}
            if (node.left == null) {return node.right}
            if (node.right !== null) {return node.left}
            let smallestNode = this.getSmallest(node.right)
            node.data = smallestNode.data
            this.removeNode(node.right, smallestNode.data)
            return node
        } else if (node.data < data) {node.right = this.removeNode(node.right.data)
        } else {node.left = this.removeNode(node.left.data)
        }
    }
    getSmallest(node) {while (node.left != null) {node = node.left}
        return node
    }

}

图

图由边的汇合及顶点的汇合组成。边由顶点对 (v1,v2) 定义，v1 和 v2 别离是图中的两个顶点。顶点也有权重。如果一个图的顶点对是有序的，则能够称之为有向图。在对有向图中的顶点对排序后，便能够在两个顶点之间绘制一个箭头。有向图表明了顶点的流向。

如果图是无序的，则称之为无序图

咱们将示意图的边的办法称为邻接表或者邻接表数组。这种办法将边存储为由顶点的相邻顶点列表形成的数组，并以此顶点作为索引。

上面实现图类

示意顶点 

class Vertex{constructor(label){this.label=label}
}

构建图 

class Graph{
  edges=0
  adj=[]
  vertices=0
  marked=[]
  edgeTo=[]
  constructor(v){
    this.vertices = v
    for(let index=0;index < this.vertices;index++){this.adj[index]=[]
      this.marked[index]=false
    }
  }
}

addEdge() 增加节点 

 addEdge(v,w){this.adj[v].push(w)
    this.adj[w].push(v)
    this.edges++
  }

showGraph() 函数会通过打印所有顶点及其相邻顶点列表的形式来显示图 

showGraph() {for (var i = 0; i < this.vertices; ++i) {let resStr = `${i}-> `
      for (var j = 0; j < this.vertices; ++j) {if (this.adj[i][j] != undefined) {resStr=resStr+`${this.adj[i][j]} `
        }
      }
      console.log(resStr)
    }
  }

深度优先搜寻

深度优先搜寻包含从一条门路的起始顶点开始追溯，直到达到最初一个顶点，而后回溯，持续追溯下一条门路，直到达到最初的顶点，如此往返，直到没有门路为止。这不是在搜寻特定的门路，而是通过搜寻来查看在图中有哪些门路能够抉择 

  dfs(v){this.marked[v]=true
    if(this.adj[v] != undefined){console.log("Visited vertex:" + v)
    }
    for(let key of this.adj[v]){if(!this.marked[key]){this.dfs(key)
      }
    }
  }

广度优先搜寻

广度优先搜寻从第一个顶点开始，尝试拜访尽可能凑近它的顶点。实质上，这种搜寻在图上是逐层挪动的，首先查看最靠近第一个顶点的层，再逐步向下挪动到离起始顶点最远的层 

  bfs(s){let queue = []
    this.marked[s] = true
    queue.push(s)
    while(queue.length>0){let v = queue.shift()
      if(v == undefined){console.log(`Visisted vertex: ${v}`)
      }
      for(let key of this.adj[v]){if(!this.marked[key]){this.edgeTo[key]=v
          this.marked[key] = true
          queue.push(key)
        }
      }
    }
  }

残缺代码 

class Vertex{constructor(label){this.label=label}
}
class Graph{
  edges=0
  adj=[]
  vertices=0
  marked=[]
  edgeTo=[]
  constructor(v){
    this.vertices = v
    for(let index=0;index < this.vertices;index++){this.adj[index]=[]
      this.marked[index]=false
    }
  }
  addEdge(v,w){this.adj[v].push(w)
    this.adj[w].push(v)
    this.edges++
  }
  showGraph() {for (var i = 0; i < this.vertices; ++i) {let resStr = `${i}-> `
  
      for (var j = 0; j < this.vertices; ++j) {if (this.adj[i][j] != undefined) {resStr=resStr+`${this.adj[i][j]} `
        }
      }
      console.log(resStr)
    }
  }
  dfs(v){this.marked[v]=true
    if(this.adj[v] != undefined){console.log("Visited vertex:" + v)
    }
    for(let key of this.adj[v]){if(!this.marked[key]){this.dfs(key)
      }
    }
  }
  bfs(s){let queue = []
    this.marked[s] = true
    queue.push(s)
    while(queue.length>0){let v = queue.shift()
      if(v == undefined){console.log(`Visisted vertex: ${v}`)
      }
      for(let key of this.adj[v]){if(!this.marked[key]){this.edgeTo[key]=v
          this.marked[key] = true
          queue.push(key)
        }
      }
    }
  }
}

正文完
javascript
发表至： javascript
2021-12-17
 0
function-JavaScrip的一等公民
记2019前端面经
关于javascript:bunjs-一个新的JavaScript运行环境
每日 30 秒之 巧用可视区域