New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
data-footstone
Advanced tools
data-footstone - npm Package Compare versions
Comparing version 0.1.12 to 0.1.13
@@ -44,2 +44,5 @@ 'use strict'; | ||
| } | ||
| peek() { | ||
| return this.items[0]; | ||
| } | ||
| } | ||
@@ -175,2 +178,7 @@ // 优先队列 | ||
| } | ||
| // 优先队列不能反转 | ||
| peek() { | ||
| let t = this.items[0]; | ||
| return t ? t.value : undefined; | ||
| } | ||
| } | ||
@@ -177,0 +185,0 @@ |
| 'use strict'; | ||
| // class BaseTree<T> implements BT<T> { | ||
| // // root: BTN<T> | null | ||
| // // constructor() { | ||
| // // this.root = null | ||
| // // } | ||
| // // createNode(v: T) { | ||
| // // return { | ||
| // // value: v, | ||
| // // left: null, | ||
| // // right: null, | ||
| // // } | ||
| // // } | ||
| // // 先父节点，再左节点，再右节点 | ||
| // _preOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 整体从左到右依次操作 | ||
| // _inOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 先左节点，再右节点，再父节点 | ||
| // _postOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| // // _findMinNode(node: BTN<T> | null) { | ||
| // // let cur = node | ||
| // // while (cur && cur.left) { | ||
| // // cur = cur.left | ||
| // // } | ||
| // // return cur | ||
| // // } | ||
| // // 不应该在这里搞这样的逻辑 | ||
| // _remove(node: BTN<T>, value: T) { | ||
| // if (!node) { | ||
| // return null | ||
| // } | ||
| // if (value < node.value) { | ||
| // node.left = this._remove(node.left, value) | ||
| // return node | ||
| // } else if (value > node.value) { | ||
| // node.right = this._remove(node.right, value) | ||
| // return node | ||
| // } else { | ||
| // // 有0个节点 | ||
| // if (!node.left && !node.right) { | ||
| // node = null | ||
| // return node | ||
| // } | ||
| // // 有1个节点 | ||
| // if (!node.left) { | ||
| // node = node.right | ||
| // return node | ||
| // } else if (!node.right) { | ||
| // node = node.left | ||
| // return node | ||
| // } | ||
| // // 有2个节点 | ||
| // let t = this._findMinNode(node.right) | ||
| // node.value = t.value | ||
| // node.right = this._remove(node.right, t.value) | ||
| // return node | ||
| // } | ||
| // } | ||
| // 返回节点的高度。 | ||
| // heightNode(node: BTN<T>): N { | ||
| // return node | ||
| // ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| // : -1 | ||
| // } | ||
| // // 待测试 | ||
| // shortPathNodeLength(node = null, deep = 0) { | ||
| // if (!node) { | ||
| // return deep | ||
| // } else { | ||
| // let queue = new Queue<BTN<T>>() | ||
| // queue.enqueue(node) | ||
| // let len = queue.size() | ||
| // while (len) { | ||
| // let i = 0 | ||
| // while (i < len) { | ||
| // let n = queue.dequeue() | ||
| // if (!n.left && !n.right) { | ||
| // return deep | ||
| // } else { | ||
| // n.left && queue.enqueue(n.left) | ||
| // n.right && queue.enqueue(n.right) | ||
| // } | ||
| // i++ | ||
| // } | ||
| // deep++ | ||
| // len = queue.size() | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| class BinarySearchTree { | ||
| var queue = require('./queue.js'); | ||
| var stack = require('./stack.js'); | ||
| class BinaryTree { | ||
| constructor() { | ||
@@ -119,22 +15,280 @@ this.root = null; | ||
| right: null, | ||
| parent: null, | ||
| }; | ||
| } | ||
| // 还缺少设置根节点的方法 | ||
| insertAsLeft(parent, current) { | ||
| let cur = this.createNode(current); | ||
| let oldLeft = parent.left; | ||
| if (oldLeft) { | ||
| oldLeft.parent = cur; | ||
| cur.left = oldLeft; | ||
| cur.parent = parent; | ||
| parent.left = cur; | ||
| } | ||
| else { | ||
| parent.left = cur; | ||
| cur.parent = parent; | ||
| } | ||
| } | ||
| insertAsRight(parent, current) { | ||
| let cur = this.createNode(current); | ||
| let oldRight = parent.right; | ||
| if (oldRight) { | ||
| oldRight.parent = cur; | ||
| cur.right = oldRight; | ||
| cur.parent = parent; | ||
| parent.right = cur; | ||
| } | ||
| else { | ||
| parent.right = cur; | ||
| cur.parent = parent; | ||
| } | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| let stack$1 = new stack.Stack(); | ||
| stack$1.push(node); | ||
| while (stack$1.size()) { | ||
| let n = stack$1.pop(); | ||
| cb(n); | ||
| n.right && stack$1.push(n.right); | ||
| n.left && stack$1.push(n.left); | ||
| } | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node); | ||
| } | ||
| } | ||
| _levelTraverse(cb, node) { | ||
| if (node) { | ||
| let queue$1 = new queue.Queue(); | ||
| queue$1.enqueue(node); | ||
| while (!queue$1.isEmpty()) { | ||
| let n = queue$1.dequeue(); | ||
| cb(n); | ||
| n.left && queue$1.enqueue(n.left); | ||
| n.right && queue$1.enqueue(n.right); | ||
| } | ||
| } | ||
| } | ||
| isEmpty() { | ||
| return !this.root; | ||
| } | ||
| _height(node, h = 0) { | ||
| let res; | ||
| if (!node) { | ||
| res = h; | ||
| } | ||
| else if (node.left && node.right) { | ||
| res = Math.max(this._height(node.left, h + 1), this._height(node.right, h + 1)); | ||
| } | ||
| else if (node.left) { | ||
| res = this._height(node.left, ++h); | ||
| } | ||
| else if (node.right) { | ||
| res = this._height(node.right, ++h); | ||
| } | ||
| else { | ||
| res = h + 1; | ||
| } | ||
| return res; | ||
| } | ||
| // 得到指定根节点的二叉树的高度。 | ||
| // 从1开始数 | ||
| height(node = this.root) { | ||
| return this._height(node); | ||
| } | ||
| // 得到指定子树的深度 | ||
| deep(node = this.root) { | ||
| let d = -1; | ||
| if (node) { | ||
| let cur = node; | ||
| while (cur) { | ||
| d++; | ||
| cur = cur.parent; | ||
| } | ||
| } | ||
| return d; | ||
| } | ||
| // 得到最小深度 | ||
| // 认为深度与层数 值相等。 | ||
| minDeep() { | ||
| if (this.root) { | ||
| let queue$1 = new queue.Queue(); | ||
| queue$1.enqueue(this.root); | ||
| let len = queue$1.size(); | ||
| let deep = 0; // 认为根节点的深度是0 | ||
| while (len) { | ||
| for (let i = 0; i < len; i++) { | ||
| let n = queue$1.dequeue(); | ||
| if (!n.left && !n.right) { | ||
| return deep; | ||
| } | ||
| n.left && queue$1.enqueue(n.left); | ||
| n.right && queue$1.enqueue(n.right); | ||
| } | ||
| len = queue$1.size(); | ||
| deep++; | ||
| } | ||
| } | ||
| else { | ||
| return -1; | ||
| } | ||
| } | ||
| // 得到最大深度 就是 根节点的深度 | ||
| // 得到指定层数的节点 | ||
| // 层数从0开始数 | ||
| // -1表示最后一层。-x表示最后第x层。 | ||
| getLevelNode(p) { | ||
| if (!this.root) { | ||
| return []; | ||
| } | ||
| let maxHeight = this.height(this.root); | ||
| if (0 <= p && p <= maxHeight) { | ||
| let level = 0; | ||
| let queue$1 = new queue.Queue(); | ||
| queue$1.enqueue(this.root); | ||
| while (level < p) { | ||
| let len = queue$1.size(); | ||
| for (let i = 0; i < len; i++) { | ||
| let n = queue$1.dequeue(); | ||
| n.left && queue$1.enqueue(n.left); | ||
| n.right && queue$1.enqueue(n.right); | ||
| } | ||
| level++; | ||
| } | ||
| return queue$1.toArray(); | ||
| } | ||
| else { | ||
| p = maxHeight + p; | ||
| if (0 <= p && p <= maxHeight) { | ||
| return this.getLevelNode(p); | ||
| } | ||
| else { | ||
| return []; | ||
| } | ||
| } | ||
| } | ||
| // 是否是真二叉树 | ||
| // 每个节点的出度是 0 或 2. | ||
| // to test | ||
| isProper() { | ||
| if (!this.root) { | ||
| return true; | ||
| } | ||
| let stack$1 = new stack.Stack(); | ||
| stack$1.push(this.root); | ||
| let res = true; | ||
| while (!stack$1.isEmpty()) { | ||
| let n = stack$1.pop(); | ||
| if ((n.left && n.right) || (!n.left && !n.right)) { | ||
| n.left && stack$1.push(n.left); | ||
| n.right && stack$1.push(n.right); | ||
| } | ||
| else { | ||
| res = false; | ||
| break; | ||
| } | ||
| } | ||
| return res; | ||
| } | ||
| // 树中节点总数 | ||
| vertexCount() { | ||
| let res = 0; | ||
| this._preOrderTraverse(() => { | ||
| res++; | ||
| }, this.root); | ||
| return res; | ||
| } | ||
| // 是否是满二叉树 | ||
| // 叶子节点在最后一层上的真二叉树。 | ||
| // to test | ||
| isFull() { | ||
| let p = this.height(); | ||
| return this.vertexCount() === (Math.pow(2, p) - 1); | ||
| } | ||
| // 是否是完全二叉树 | ||
| // 非最后一层为满二叉树，最后一层从左到右分布。 | ||
| // to test | ||
| isComplete() { | ||
| let h = this.height(); | ||
| let fullCount = Math.pow(2, h) - 1; | ||
| let treeCount = this.vertexCount(); | ||
| if (treeCount === fullCount) { | ||
| return true; | ||
| } | ||
| else { | ||
| let lastLevelCount = this.getLevelNode(-1).length; | ||
| let lastLevelFullCount = Math.pow(2, h - 1); | ||
| if (lastLevelFullCount - lastLevelCount != fullCount - treeCount) { | ||
| return false; | ||
| } | ||
| else { | ||
| let lastSecondLevelNodeList = this.getLevelNode(-2); | ||
| let i = 0; | ||
| // 找到第一个不是2度的节点 | ||
| while (i < lastSecondLevelNodeList.length) { | ||
| if (lastSecondLevelNodeList[i].left && lastSecondLevelNodeList[i].right) { | ||
| i++; | ||
| } | ||
| else { | ||
| break; | ||
| } | ||
| } | ||
| // 该节点只有左节点或无节点 | ||
| if (lastSecondLevelNodeList[i].right) { | ||
| return false; | ||
| } | ||
| i++; | ||
| // 剩下的节点都是0度 | ||
| while (i < lastSecondLevelNodeList.length) { | ||
| if (lastSecondLevelNodeList[i].left || lastSecondLevelNodeList[i].right) { | ||
| return false; | ||
| } | ||
| i++; | ||
| } | ||
| return true; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| class BinarySearchTree extends BinaryTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| // if (!node.left) { | ||
| // node.left = newNode | ||
| // } else { | ||
| // this._insertNode(node.left, newNode) | ||
| // } | ||
| node.left ? this._insertNode(node.left, newNode) : (node.left = newNode); | ||
| // node.left ? this._insertNode(node.left, newNode) : (node.left = newNode) | ||
| // let oldLeft = node.left | ||
| if (node.left) { | ||
| this._insertNode(node.left, newNode); | ||
| } | ||
| else { | ||
| node.left = newNode; | ||
| newNode.parent = node; | ||
| } | ||
| } | ||
| else { | ||
| node.right | ||
| ? this._insertNode(node.right, newNode) | ||
| : (node.right = newNode); | ||
| // if (!node.right) { | ||
| // node.right = newNode | ||
| // } else { | ||
| // this._insertNode(node.right, newNode) | ||
| // } | ||
| // node.right | ||
| // ? this._insertNode(node.right, newNode) | ||
| // : (node.right = newNode) | ||
| if (node.right) { | ||
| this._insertNode(node.right, newNode); | ||
| } | ||
| else { | ||
| node.right = newNode; | ||
| newNode.parent = node; | ||
| } | ||
| } | ||
@@ -151,2 +305,3 @@ } | ||
| } | ||
| // 可能后期会删除此方法 | ||
| // 是否存在 | ||
@@ -170,34 +325,64 @@ search(v) { | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| // for del 2023/02/15 | ||
| // T<n> = O(1) + T(a) + T(n-a-1) = O(n) | ||
| // _preOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // 递归 =》 迭代 | ||
| // _preOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // let stack = new Stack<BinarySearchTreeNode<T>>() | ||
| // stack.push(node) | ||
| // while (!stack.isEmpty()) { | ||
| // let n = stack.pop() | ||
| // cb(n.value) | ||
| // n.right && stack.push(n.right) | ||
| // n.left && stack.push(n.left) | ||
| // } | ||
| // } | ||
| // } | ||
| // _inOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // _postOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| traverse(cb, order = 'inOrder') { | ||
| switch (order) { | ||
| case 'preOrder': | ||
| this._preOrderTraverse(cb, this.root); | ||
| // this._preOrderTraverse(cb, this.root) | ||
| this._preOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'inOrder': | ||
| this._inOrderTraverse(cb, this.root); | ||
| // this._inOrderTraverse(cb, this.root) | ||
| this._inOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'postOrder': | ||
| this._postOrderTraverse(cb, this.root); | ||
| // this._postOrderTraverse(cb, this.root) | ||
| this._postOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'level': | ||
| // this._levelTraverse(cb, this.root) | ||
| this._levelTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| } | ||
@@ -285,2 +470,3 @@ } | ||
| exports.BinarySearchTree = BinarySearchTree; | ||
| exports.BinaryTree = BinaryTree; | ||
| //# sourceMappingURL=tree.js.map |
@@ -42,2 +42,5 @@ // 可以抽象出BaseQueue | ||
| } | ||
| peek() { | ||
| return this.items[0]; | ||
| } | ||
| } | ||
@@ -173,2 +176,7 @@ // 优先队列 | ||
| } | ||
| // 优先队列不能反转 | ||
| peek() { | ||
| let t = this.items[0]; | ||
| return t ? t.value : undefined; | ||
| } | ||
| } | ||
@@ -175,0 +183,0 @@ |
@@ -1,109 +0,5 @@ | ||
| // class BaseTree<T> implements BT<T> { | ||
| // // root: BTN<T> | null | ||
| // // constructor() { | ||
| // // this.root = null | ||
| // // } | ||
| // // createNode(v: T) { | ||
| // // return { | ||
| // // value: v, | ||
| // // left: null, | ||
| // // right: null, | ||
| // // } | ||
| // // } | ||
| // // 先父节点，再左节点，再右节点 | ||
| // _preOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 整体从左到右依次操作 | ||
| // _inOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 先左节点，再右节点，再父节点 | ||
| // _postOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| // // _findMinNode(node: BTN<T> | null) { | ||
| // // let cur = node | ||
| // // while (cur && cur.left) { | ||
| // // cur = cur.left | ||
| // // } | ||
| // // return cur | ||
| // // } | ||
| // // 不应该在这里搞这样的逻辑 | ||
| // _remove(node: BTN<T>, value: T) { | ||
| // if (!node) { | ||
| // return null | ||
| // } | ||
| // if (value < node.value) { | ||
| // node.left = this._remove(node.left, value) | ||
| // return node | ||
| // } else if (value > node.value) { | ||
| // node.right = this._remove(node.right, value) | ||
| // return node | ||
| // } else { | ||
| // // 有0个节点 | ||
| // if (!node.left && !node.right) { | ||
| // node = null | ||
| // return node | ||
| // } | ||
| // // 有1个节点 | ||
| // if (!node.left) { | ||
| // node = node.right | ||
| // return node | ||
| // } else if (!node.right) { | ||
| // node = node.left | ||
| // return node | ||
| // } | ||
| // // 有2个节点 | ||
| // let t = this._findMinNode(node.right) | ||
| // node.value = t.value | ||
| // node.right = this._remove(node.right, t.value) | ||
| // return node | ||
| // } | ||
| // } | ||
| // 返回节点的高度。 | ||
| // heightNode(node: BTN<T>): N { | ||
| // return node | ||
| // ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| // : -1 | ||
| // } | ||
| // // 待测试 | ||
| // shortPathNodeLength(node = null, deep = 0) { | ||
| // if (!node) { | ||
| // return deep | ||
| // } else { | ||
| // let queue = new Queue<BTN<T>>() | ||
| // queue.enqueue(node) | ||
| // let len = queue.size() | ||
| // while (len) { | ||
| // let i = 0 | ||
| // while (i < len) { | ||
| // let n = queue.dequeue() | ||
| // if (!n.left && !n.right) { | ||
| // return deep | ||
| // } else { | ||
| // n.left && queue.enqueue(n.left) | ||
| // n.right && queue.enqueue(n.right) | ||
| // } | ||
| // i++ | ||
| // } | ||
| // deep++ | ||
| // len = queue.size() | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| class BinarySearchTree { | ||
| import { Queue } from './queue.js'; | ||
| import { Stack } from './stack.js'; | ||
| class BinaryTree { | ||
| constructor() { | ||
@@ -117,22 +13,280 @@ this.root = null; | ||
| right: null, | ||
| parent: null, | ||
| }; | ||
| } | ||
| // 还缺少设置根节点的方法 | ||
| insertAsLeft(parent, current) { | ||
| let cur = this.createNode(current); | ||
| let oldLeft = parent.left; | ||
| if (oldLeft) { | ||
| oldLeft.parent = cur; | ||
| cur.left = oldLeft; | ||
| cur.parent = parent; | ||
| parent.left = cur; | ||
| } | ||
| else { | ||
| parent.left = cur; | ||
| cur.parent = parent; | ||
| } | ||
| } | ||
| insertAsRight(parent, current) { | ||
| let cur = this.createNode(current); | ||
| let oldRight = parent.right; | ||
| if (oldRight) { | ||
| oldRight.parent = cur; | ||
| cur.right = oldRight; | ||
| cur.parent = parent; | ||
| parent.right = cur; | ||
| } | ||
| else { | ||
| parent.right = cur; | ||
| cur.parent = parent; | ||
| } | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| let stack = new Stack(); | ||
| stack.push(node); | ||
| while (stack.size()) { | ||
| let n = stack.pop(); | ||
| cb(n); | ||
| n.right && stack.push(n.right); | ||
| n.left && stack.push(n.left); | ||
| } | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node); | ||
| } | ||
| } | ||
| _levelTraverse(cb, node) { | ||
| if (node) { | ||
| let queue = new Queue(); | ||
| queue.enqueue(node); | ||
| while (!queue.isEmpty()) { | ||
| let n = queue.dequeue(); | ||
| cb(n); | ||
| n.left && queue.enqueue(n.left); | ||
| n.right && queue.enqueue(n.right); | ||
| } | ||
| } | ||
| } | ||
| isEmpty() { | ||
| return !this.root; | ||
| } | ||
| _height(node, h = 0) { | ||
| let res; | ||
| if (!node) { | ||
| res = h; | ||
| } | ||
| else if (node.left && node.right) { | ||
| res = Math.max(this._height(node.left, h + 1), this._height(node.right, h + 1)); | ||
| } | ||
| else if (node.left) { | ||
| res = this._height(node.left, ++h); | ||
| } | ||
| else if (node.right) { | ||
| res = this._height(node.right, ++h); | ||
| } | ||
| else { | ||
| res = h + 1; | ||
| } | ||
| return res; | ||
| } | ||
| // 得到指定根节点的二叉树的高度。 | ||
| // 从1开始数 | ||
| height(node = this.root) { | ||
| return this._height(node); | ||
| } | ||
| // 得到指定子树的深度 | ||
| deep(node = this.root) { | ||
| let d = -1; | ||
| if (node) { | ||
| let cur = node; | ||
| while (cur) { | ||
| d++; | ||
| cur = cur.parent; | ||
| } | ||
| } | ||
| return d; | ||
| } | ||
| // 得到最小深度 | ||
| // 认为深度与层数 值相等。 | ||
| minDeep() { | ||
| if (this.root) { | ||
| let queue = new Queue(); | ||
| queue.enqueue(this.root); | ||
| let len = queue.size(); | ||
| let deep = 0; // 认为根节点的深度是0 | ||
| while (len) { | ||
| for (let i = 0; i < len; i++) { | ||
| let n = queue.dequeue(); | ||
| if (!n.left && !n.right) { | ||
| return deep; | ||
| } | ||
| n.left && queue.enqueue(n.left); | ||
| n.right && queue.enqueue(n.right); | ||
| } | ||
| len = queue.size(); | ||
| deep++; | ||
| } | ||
| } | ||
| else { | ||
| return -1; | ||
| } | ||
| } | ||
| // 得到最大深度 就是 根节点的深度 | ||
| // 得到指定层数的节点 | ||
| // 层数从0开始数 | ||
| // -1表示最后一层。-x表示最后第x层。 | ||
| getLevelNode(p) { | ||
| if (!this.root) { | ||
| return []; | ||
| } | ||
| let maxHeight = this.height(this.root); | ||
| if (0 <= p && p <= maxHeight) { | ||
| let level = 0; | ||
| let queue = new Queue(); | ||
| queue.enqueue(this.root); | ||
| while (level < p) { | ||
| let len = queue.size(); | ||
| for (let i = 0; i < len; i++) { | ||
| let n = queue.dequeue(); | ||
| n.left && queue.enqueue(n.left); | ||
| n.right && queue.enqueue(n.right); | ||
| } | ||
| level++; | ||
| } | ||
| return queue.toArray(); | ||
| } | ||
| else { | ||
| p = maxHeight + p; | ||
| if (0 <= p && p <= maxHeight) { | ||
| return this.getLevelNode(p); | ||
| } | ||
| else { | ||
| return []; | ||
| } | ||
| } | ||
| } | ||
| // 是否是真二叉树 | ||
| // 每个节点的出度是 0 或 2. | ||
| // to test | ||
| isProper() { | ||
| if (!this.root) { | ||
| return true; | ||
| } | ||
| let stack = new Stack(); | ||
| stack.push(this.root); | ||
| let res = true; | ||
| while (!stack.isEmpty()) { | ||
| let n = stack.pop(); | ||
| if ((n.left && n.right) || (!n.left && !n.right)) { | ||
| n.left && stack.push(n.left); | ||
| n.right && stack.push(n.right); | ||
| } | ||
| else { | ||
| res = false; | ||
| break; | ||
| } | ||
| } | ||
| return res; | ||
| } | ||
| // 树中节点总数 | ||
| vertexCount() { | ||
| let res = 0; | ||
| this._preOrderTraverse(() => { | ||
| res++; | ||
| }, this.root); | ||
| return res; | ||
| } | ||
| // 是否是满二叉树 | ||
| // 叶子节点在最后一层上的真二叉树。 | ||
| // to test | ||
| isFull() { | ||
| let p = this.height(); | ||
| return this.vertexCount() === (Math.pow(2, p) - 1); | ||
| } | ||
| // 是否是完全二叉树 | ||
| // 非最后一层为满二叉树，最后一层从左到右分布。 | ||
| // to test | ||
| isComplete() { | ||
| let h = this.height(); | ||
| let fullCount = Math.pow(2, h) - 1; | ||
| let treeCount = this.vertexCount(); | ||
| if (treeCount === fullCount) { | ||
| return true; | ||
| } | ||
| else { | ||
| let lastLevelCount = this.getLevelNode(-1).length; | ||
| let lastLevelFullCount = Math.pow(2, h - 1); | ||
| if (lastLevelFullCount - lastLevelCount != fullCount - treeCount) { | ||
| return false; | ||
| } | ||
| else { | ||
| let lastSecondLevelNodeList = this.getLevelNode(-2); | ||
| let i = 0; | ||
| // 找到第一个不是2度的节点 | ||
| while (i < lastSecondLevelNodeList.length) { | ||
| if (lastSecondLevelNodeList[i].left && lastSecondLevelNodeList[i].right) { | ||
| i++; | ||
| } | ||
| else { | ||
| break; | ||
| } | ||
| } | ||
| // 该节点只有左节点或无节点 | ||
| if (lastSecondLevelNodeList[i].right) { | ||
| return false; | ||
| } | ||
| i++; | ||
| // 剩下的节点都是0度 | ||
| while (i < lastSecondLevelNodeList.length) { | ||
| if (lastSecondLevelNodeList[i].left || lastSecondLevelNodeList[i].right) { | ||
| return false; | ||
| } | ||
| i++; | ||
| } | ||
| return true; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| class BinarySearchTree extends BinaryTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| // if (!node.left) { | ||
| // node.left = newNode | ||
| // } else { | ||
| // this._insertNode(node.left, newNode) | ||
| // } | ||
| node.left ? this._insertNode(node.left, newNode) : (node.left = newNode); | ||
| // node.left ? this._insertNode(node.left, newNode) : (node.left = newNode) | ||
| // let oldLeft = node.left | ||
| if (node.left) { | ||
| this._insertNode(node.left, newNode); | ||
| } | ||
| else { | ||
| node.left = newNode; | ||
| newNode.parent = node; | ||
| } | ||
| } | ||
| else { | ||
| node.right | ||
| ? this._insertNode(node.right, newNode) | ||
| : (node.right = newNode); | ||
| // if (!node.right) { | ||
| // node.right = newNode | ||
| // } else { | ||
| // this._insertNode(node.right, newNode) | ||
| // } | ||
| // node.right | ||
| // ? this._insertNode(node.right, newNode) | ||
| // : (node.right = newNode) | ||
| if (node.right) { | ||
| this._insertNode(node.right, newNode); | ||
| } | ||
| else { | ||
| node.right = newNode; | ||
| newNode.parent = node; | ||
| } | ||
| } | ||
@@ -149,2 +303,3 @@ } | ||
| } | ||
| // 可能后期会删除此方法 | ||
| // 是否存在 | ||
@@ -168,34 +323,64 @@ search(v) { | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| // for del 2023/02/15 | ||
| // T<n> = O(1) + T(a) + T(n-a-1) = O(n) | ||
| // _preOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // 递归 =》 迭代 | ||
| // _preOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // let stack = new Stack<BinarySearchTreeNode<T>>() | ||
| // stack.push(node) | ||
| // while (!stack.isEmpty()) { | ||
| // let n = stack.pop() | ||
| // cb(n.value) | ||
| // n.right && stack.push(n.right) | ||
| // n.left && stack.push(n.left) | ||
| // } | ||
| // } | ||
| // } | ||
| // _inOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // _postOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| traverse(cb, order = 'inOrder') { | ||
| switch (order) { | ||
| case 'preOrder': | ||
| this._preOrderTraverse(cb, this.root); | ||
| // this._preOrderTraverse(cb, this.root) | ||
| this._preOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'inOrder': | ||
| this._inOrderTraverse(cb, this.root); | ||
| // this._inOrderTraverse(cb, this.root) | ||
| this._inOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'postOrder': | ||
| this._postOrderTraverse(cb, this.root); | ||
| // this._postOrderTraverse(cb, this.root) | ||
| this._postOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'level': | ||
| // this._levelTraverse(cb, this.root) | ||
| this._levelTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| } | ||
@@ -282,3 +467,3 @@ } | ||
| export { BinarySearchTree }; | ||
| export { BinarySearchTree, BinaryTree }; | ||
| //# sourceMappingURL=tree.js.map |
| { | ||
| "name": "data-footstone", | ||
| "version": "0.1.12", | ||
| "version": "0.1.13", | ||
| "description": "data structure", | ||
@@ -75,3 +75,3 @@ "author": "feigebaobei <18515195415@163.com>", | ||
| }, | ||
| "gitHead": "95f949439a162635ee92bb2b0660ba9fe5a1237a" | ||
| "gitHead": "9a8b00dcbc961707886c7d03db1a0541fea137d4" | ||
| } |
@@ -42,2 +42,5 @@ // 可以抽象出BaseQueue | ||
| } | ||
| peek() { | ||
| return this.items[0]; | ||
| } | ||
| } | ||
@@ -173,4 +176,9 @@ // 优先队列 | ||
| } | ||
| // 优先队列不能反转 | ||
| peek() { | ||
| let t = this.items[0]; | ||
| return t ? t.value : undefined; | ||
| } | ||
| } | ||
| // 不写循环队列。它应该写在循环链表。 | ||
| export { Queue, PriorityQueue }; |
@@ -1,109 +0,4 @@ | ||
| // class BaseTree<T> implements BT<T> { | ||
| // // root: BTN<T> | null | ||
| // // constructor() { | ||
| // // this.root = null | ||
| // // } | ||
| // // createNode(v: T) { | ||
| // // return { | ||
| // // value: v, | ||
| // // left: null, | ||
| // // right: null, | ||
| // // } | ||
| // // } | ||
| // // 先父节点，再左节点，再右节点 | ||
| // _preOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 整体从左到右依次操作 | ||
| // _inOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // // 先左节点，再右节点，再父节点 | ||
| // _postOrderTraverse(cb: F, node: BTN<T> | null) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| // // _findMinNode(node: BTN<T> | null) { | ||
| // // let cur = node | ||
| // // while (cur && cur.left) { | ||
| // // cur = cur.left | ||
| // // } | ||
| // // return cur | ||
| // // } | ||
| // // 不应该在这里搞这样的逻辑 | ||
| // _remove(node: BTN<T>, value: T) { | ||
| // if (!node) { | ||
| // return null | ||
| // } | ||
| // if (value < node.value) { | ||
| // node.left = this._remove(node.left, value) | ||
| // return node | ||
| // } else if (value > node.value) { | ||
| // node.right = this._remove(node.right, value) | ||
| // return node | ||
| // } else { | ||
| // // 有0个节点 | ||
| // if (!node.left && !node.right) { | ||
| // node = null | ||
| // return node | ||
| // } | ||
| // // 有1个节点 | ||
| // if (!node.left) { | ||
| // node = node.right | ||
| // return node | ||
| // } else if (!node.right) { | ||
| // node = node.left | ||
| // return node | ||
| // } | ||
| // // 有2个节点 | ||
| // let t = this._findMinNode(node.right) | ||
| // node.value = t.value | ||
| // node.right = this._remove(node.right, t.value) | ||
| // return node | ||
| // } | ||
| // } | ||
| // 返回节点的高度。 | ||
| // heightNode(node: BTN<T>): N { | ||
| // return node | ||
| // ? Math.max(this.heightNode(node.left), this.heightNode(node.right)) + 1 | ||
| // : -1 | ||
| // } | ||
| // // 待测试 | ||
| // shortPathNodeLength(node = null, deep = 0) { | ||
| // if (!node) { | ||
| // return deep | ||
| // } else { | ||
| // let queue = new Queue<BTN<T>>() | ||
| // queue.enqueue(node) | ||
| // let len = queue.size() | ||
| // while (len) { | ||
| // let i = 0 | ||
| // while (i < len) { | ||
| // let n = queue.dequeue() | ||
| // if (!n.left && !n.right) { | ||
| // return deep | ||
| // } else { | ||
| // n.left && queue.enqueue(n.left) | ||
| // n.right && queue.enqueue(n.right) | ||
| // } | ||
| // i++ | ||
| // } | ||
| // deep++ | ||
| // len = queue.size() | ||
| // } | ||
| // } | ||
| // } | ||
| // } | ||
| class BinarySearchTree { | ||
| import { Queue } from './queue'; | ||
| import { Stack } from './stack'; | ||
| class BinaryTree { | ||
| constructor() { | ||
@@ -117,22 +12,282 @@ this.root = null; | ||
| right: null, | ||
| parent: null, | ||
| }; | ||
| } | ||
| // 还缺少设置根节点的方法 | ||
| insertAsLeft(parent, current) { | ||
| let cur = this.createNode(current); | ||
| let oldLeft = parent.left; | ||
| if (oldLeft) { | ||
| oldLeft.parent = cur; | ||
| cur.left = oldLeft; | ||
| cur.parent = parent; | ||
| parent.left = cur; | ||
| } | ||
| else { | ||
| parent.left = cur; | ||
| cur.parent = parent; | ||
| } | ||
| } | ||
| insertAsRight(parent, current) { | ||
| let cur = this.createNode(current); | ||
| let oldRight = parent.right; | ||
| if (oldRight) { | ||
| oldRight.parent = cur; | ||
| cur.right = oldRight; | ||
| cur.parent = parent; | ||
| parent.right = cur; | ||
| } | ||
| else { | ||
| parent.right = cur; | ||
| cur.parent = parent; | ||
| } | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| let stack = new Stack(); | ||
| stack.push(node); | ||
| while (stack.size()) { | ||
| let n = stack.pop(); | ||
| cb(n); | ||
| n.right && stack.push(n.right); | ||
| n.left && stack.push(n.left); | ||
| } | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node); | ||
| } | ||
| } | ||
| _levelTraverse(cb, node) { | ||
| if (node) { | ||
| let queue = new Queue(); | ||
| queue.enqueue(node); | ||
| while (!queue.isEmpty()) { | ||
| let n = queue.dequeue(); | ||
| cb(n); | ||
| n.left && queue.enqueue(n.left); | ||
| n.right && queue.enqueue(n.right); | ||
| } | ||
| } | ||
| } | ||
| isEmpty() { | ||
| return !this.root; | ||
| } | ||
| _height(node, h = 0) { | ||
| let res; | ||
| if (!node) { | ||
| res = h; | ||
| } | ||
| else if (node.left && node.right) { | ||
| res = Math.max(this._height(node.left, h + 1), this._height(node.right, h + 1)); | ||
| } | ||
| else if (node.left) { | ||
| res = this._height(node.left, ++h); | ||
| } | ||
| else if (node.right) { | ||
| res = this._height(node.right, ++h); | ||
| } | ||
| else { | ||
| res = h + 1; | ||
| } | ||
| return res; | ||
| } | ||
| // 得到指定根节点的二叉树的高度。 | ||
| // 从1开始数 | ||
| height(node = this.root) { | ||
| return this._height(node); | ||
| } | ||
| // 得到指定子树的深度 | ||
| deep(node = this.root) { | ||
| let d = -1; | ||
| if (node) { | ||
| let cur = node; | ||
| while (cur) { | ||
| d++; | ||
| cur = cur.parent; | ||
| } | ||
| } | ||
| return d; | ||
| } | ||
| // 得到最小深度 | ||
| // 认为深度与层数 值相等。 | ||
| minDeep() { | ||
| if (this.root) { | ||
| let queue = new Queue(); | ||
| queue.enqueue(this.root); | ||
| let len = queue.size(); | ||
| let deep = 0; // 认为根节点的深度是0 | ||
| while (len) { | ||
| for (let i = 0; i < len; i++) { | ||
| let n = queue.dequeue(); | ||
| if (!n.left && !n.right) { | ||
| return deep; | ||
| } | ||
| n.left && queue.enqueue(n.left); | ||
| n.right && queue.enqueue(n.right); | ||
| } | ||
| len = queue.size(); | ||
| deep++; | ||
| } | ||
| } | ||
| else { | ||
| return -1; | ||
| } | ||
| } | ||
| // 得到最大深度 就是 根节点的深度 | ||
| // 得到指定层数的节点 | ||
| // 层数从0开始数 | ||
| // -1表示最后一层。-x表示最后第x层。 | ||
| getLevelNode(p) { | ||
| if (!this.root) { | ||
| return []; | ||
| } | ||
| let maxHeight = this.height(this.root); | ||
| if (0 <= p && p <= maxHeight) { | ||
| let level = 0; | ||
| let queue = new Queue(); | ||
| queue.enqueue(this.root); | ||
| while (level < p) { | ||
| let len = queue.size(); | ||
| for (let i = 0; i < len; i++) { | ||
| let n = queue.dequeue(); | ||
| n.left && queue.enqueue(n.left); | ||
| n.right && queue.enqueue(n.right); | ||
| } | ||
| level++; | ||
| } | ||
| return queue.toArray(); | ||
| } | ||
| else { | ||
| p = maxHeight + p; | ||
| if (0 <= p && p <= maxHeight) { | ||
| return this.getLevelNode(p); | ||
| } | ||
| else { | ||
| return []; | ||
| } | ||
| } | ||
| } | ||
| // 是否是真二叉树 | ||
| // 每个节点的出度是 0 或 2. | ||
| // to test | ||
| isProper() { | ||
| if (!this.root) { | ||
| return true; | ||
| } | ||
| let stack = new Stack(); | ||
| stack.push(this.root); | ||
| let res = true; | ||
| while (!stack.isEmpty()) { | ||
| let n = stack.pop(); | ||
| if ((n.left && n.right) || (!n.left && !n.right)) { | ||
| n.left && stack.push(n.left); | ||
| n.right && stack.push(n.right); | ||
| } | ||
| else { | ||
| res = false; | ||
| break; | ||
| } | ||
| } | ||
| return res; | ||
| } | ||
| // 树中节点总数 | ||
| vertexCount() { | ||
| let res = 0; | ||
| this._preOrderTraverse(() => { | ||
| res++; | ||
| }, this.root); | ||
| return res; | ||
| } | ||
| // 是否是满二叉树 | ||
| // 叶子节点在最后一层上的真二叉树。 | ||
| // to test | ||
| isFull() { | ||
| let p = this.height(); | ||
| return this.vertexCount() === (Math.pow(2, p) - 1); | ||
| } | ||
| // 是否是完全二叉树 | ||
| // 非最后一层为满二叉树，最后一层从左到右分布。 | ||
| // to test | ||
| isComplete() { | ||
| let h = this.height(); | ||
| let fullCount = Math.pow(2, h) - 1; | ||
| let treeCount = this.vertexCount(); | ||
| if (treeCount === fullCount) { | ||
| return true; | ||
| } | ||
| else { | ||
| let lastLevelCount = this.getLevelNode(-1).length; | ||
| let lastLevelFullCount = Math.pow(2, h - 1); | ||
| if (lastLevelFullCount - lastLevelCount != fullCount - treeCount) { | ||
| return false; | ||
| } | ||
| else { | ||
| let lastSecondLevelNodeList = this.getLevelNode(-2); | ||
| let i = 0; | ||
| let flag = 0; | ||
| // 找到第一个不是2度的节点 | ||
| while (i < lastSecondLevelNodeList.length) { | ||
| if (lastSecondLevelNodeList[i].left && lastSecondLevelNodeList[i].right) { | ||
| flag++; | ||
| i++; | ||
| } | ||
| else { | ||
| break; | ||
| } | ||
| } | ||
| // 该节点只有左节点或无节点 | ||
| if (lastSecondLevelNodeList[i].right) { | ||
| return false; | ||
| } | ||
| i++; | ||
| // 剩下的节点都是0度 | ||
| while (i < lastSecondLevelNodeList.length) { | ||
| if (lastSecondLevelNodeList[i].left || lastSecondLevelNodeList[i].right) { | ||
| return false; | ||
| } | ||
| i++; | ||
| } | ||
| return true; | ||
| } | ||
| } | ||
| } | ||
| } | ||
| class BinarySearchTree extends BinaryTree { | ||
| constructor() { | ||
| super(); | ||
| } | ||
| _insertNode(node, newNode) { | ||
| if (newNode.value < node.value) { | ||
| // if (!node.left) { | ||
| // node.left = newNode | ||
| // } else { | ||
| // this._insertNode(node.left, newNode) | ||
| // } | ||
| node.left ? this._insertNode(node.left, newNode) : (node.left = newNode); | ||
| // node.left ? this._insertNode(node.left, newNode) : (node.left = newNode) | ||
| // let oldLeft = node.left | ||
| if (node.left) { | ||
| this._insertNode(node.left, newNode); | ||
| } | ||
| else { | ||
| node.left = newNode; | ||
| newNode.parent = node; | ||
| } | ||
| } | ||
| else { | ||
| node.right | ||
| ? this._insertNode(node.right, newNode) | ||
| : (node.right = newNode); | ||
| // if (!node.right) { | ||
| // node.right = newNode | ||
| // } else { | ||
| // this._insertNode(node.right, newNode) | ||
| // } | ||
| // node.right | ||
| // ? this._insertNode(node.right, newNode) | ||
| // : (node.right = newNode) | ||
| if (node.right) { | ||
| this._insertNode(node.right, newNode); | ||
| } | ||
| else { | ||
| node.right = newNode; | ||
| newNode.parent = node; | ||
| } | ||
| } | ||
@@ -149,2 +304,3 @@ } | ||
| } | ||
| // 可能后期会删除此方法 | ||
| // 是否存在 | ||
@@ -168,34 +324,64 @@ search(v) { | ||
| } | ||
| _preOrderTraverse(cb, node) { | ||
| if (node) { | ||
| cb(node.value); | ||
| this._preOrderTraverse(cb, node.left); | ||
| this._preOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _inOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._inOrderTraverse(cb, node.left); | ||
| cb(node.value); | ||
| this._inOrderTraverse(cb, node.right); | ||
| } | ||
| } | ||
| _postOrderTraverse(cb, node) { | ||
| if (node) { | ||
| this._postOrderTraverse(cb, node.left); | ||
| this._postOrderTraverse(cb, node.right); | ||
| cb(node.value); | ||
| } | ||
| } | ||
| // for del 2023/02/15 | ||
| // T<n> = O(1) + T(a) + T(n-a-1) = O(n) | ||
| // _preOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // cb(node.value) | ||
| // this._preOrderTraverse(cb, node.left) | ||
| // this._preOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // 递归 =》 迭代 | ||
| // _preOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // let stack = new Stack<BinarySearchTreeNode<T>>() | ||
| // stack.push(node) | ||
| // while (!stack.isEmpty()) { | ||
| // let n = stack.pop() | ||
| // cb(n.value) | ||
| // n.right && stack.push(n.right) | ||
| // n.left && stack.push(n.left) | ||
| // } | ||
| // } | ||
| // } | ||
| // _inOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // this._inOrderTraverse(cb, node.left) | ||
| // cb(node.value) | ||
| // this._inOrderTraverse(cb, node.right) | ||
| // } | ||
| // } | ||
| // _postOrderTraverse(cb: F, node: BinarySearchTreeNodeOrNull<T>) { | ||
| // if (node) { | ||
| // this._postOrderTraverse(cb, node.left) | ||
| // this._postOrderTraverse(cb, node.right) | ||
| // cb(node.value) | ||
| // } | ||
| // } | ||
| traverse(cb, order = 'inOrder') { | ||
| switch (order) { | ||
| case 'preOrder': | ||
| this._preOrderTraverse(cb, this.root); | ||
| // this._preOrderTraverse(cb, this.root) | ||
| this._preOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'inOrder': | ||
| this._inOrderTraverse(cb, this.root); | ||
| // this._inOrderTraverse(cb, this.root) | ||
| this._inOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'postOrder': | ||
| this._postOrderTraverse(cb, this.root); | ||
| // this._postOrderTraverse(cb, this.root) | ||
| this._postOrderTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| case 'level': | ||
| // this._levelTraverse(cb, this.root) | ||
| this._levelTraverse((node) => { | ||
| cb(node.value); | ||
| }, this.root); | ||
| break; | ||
| } | ||
@@ -350,5 +536,6 @@ } | ||
| // BaseTree, | ||
| BinarySearchTree, | ||
| // BinaryTreeNode, | ||
| BinaryTree, BinarySearchTree, | ||
| // AVLTree, | ||
| // RedBackTree, | ||
| }; |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
No alert changes
Improved metrics
- Total package byte prevSize
- increased by12.93%
407854
- Lines of code
- increased by9.97%
6395
No dependency changes