資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學JavaScript 中反轉二叉樹
題目要求使用者給定一棵二叉樹，找到這棵二叉樹的映象影像，使得樹枝的對應和並列的兄弟節點反轉。簡而言之，就是將給定的原始二叉樹作為輸入，反轉整棵二叉樹。
題目的輸出看起來像是輸入二叉樹的反轉函式的總結。
什麼是 JavaScript 中的樹？
樹指的是一種最佳化後的資料結構，用於儲存資料，樹中存在的資料點被稱為節點。樹形資料結構會自動像現實世界中的樹一樣視覺化。樹的頂部資料點稱為根節點，從樹中伸出的分支就像現實世界中的樹一樣，稱為子節點，子節點也可以有遞迴分支，這些分支可能有或沒有子節點。
樹形資料結構對從單個節點伸出的分支（稱為子節點）沒有限制，但在資料結構樹本身中存在許多型別的樹。
什麼是 JavaScript 中的二叉樹？
二叉樹是 JavaScript 中的一種樹，其中樹的每個分支最多包含兩個子節點。它也是按時間順序排列的，其中樹的左側的值小於根節點，樹的右側的值大於根節點，從而完全平衡樹。
什麼是 JavaScript 中的反轉二叉樹？
反轉二叉樹意味著根據特定規則反轉樹，其中二叉樹的左子節點變成二叉樹的右子節點。此特定條件適用於樹的遞迴子分支。
演算法 - 建立節點
在二叉搜尋樹中建立節點的演算法如下：
步驟 1：宣告一個名為 Node 的類，該類採用一個帶 value 引數的建構函式，即其中的實際資料點。
步驟 2：建構函式將使用 JavaScript 中的 this 初始化實際資料點到當前上下文和引用，同時將左右指標初始化為 null，以便在樹中插入資料點。c 程式碼演算法 -
演算法程式碼 - 建立節點
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
演算法 - 列印樹
使用 createNode 函式建立節點後，顯示節點給使用者的演算法返回給定節點中存在的所有值。
步驟 1：宣告一個函式 printTree，該函式將使用者提供的根值作為其引數。
步驟 2：宣告一個樹元素列表和佇列，使得列表初始化為空陣列，佇列初始化為傳遞給函式的引數根。
步驟 3：只要佇列的長度不小於 0，就需要將第 0 個索引處的第一個元素移出，並使用 JavaScript 中的 push 方法將其推回到元素列表中。
步驟 4：這是演算法的遞迴步驟，用於檢查樹的左子分支是否不為空，然後將左子分支的元素推入列表。
步驟 5：這是演算法的遞迴步驟，用於檢查樹的右子分支是否不為空，然後將右子分支的元素推入列表。
演算法程式碼 - 列印樹
const printTree = (root) => {
let listOfTreeElements = [];
let queueOfTreeElements = [root];
while (queueOfTreeElements.length) {
let currentNode = queueOfTreeElements.shift();
listOfTreeElements.push(currentNode.value);
if(currentNode.left) queueOfTreeElements.push(currentNode.left);
if(currentNode.right) queueOfTreeElements.push(currentNode.right);
}
return listOfTreeElements;
}
現在是時候呼叫函式來執行一些特定任務，例如建立節點和使用 printTree 演算法以二叉樹的形式顯示節點了。
將從宣告為 Node 的類建立一個新物件，並將值插入到左右子分支。
示例
let originalTree = new Node(4); originalTree.left = new Node(2); originalTree.right = new Node(7); originalTree.left.left = new Node(1); originalTree.left.right = new Node(3); originalTree.right.left = new Node(9); originalTree.right.right = new Node(0); console.log(printTree(originalTree));
插入資料點後，二叉搜尋樹的輸出如下所示：
輸出
Binary Search Tree after insertion : [ 4, 2, 7, 1, 3, 9, 0 ]
演算法 - findInvertedBinaryTree 方法
步驟 1：宣告一個名為 findInvertedBinaryTree 的函式，該函式將根值作為引數。
步驟 2：由於步驟 1 中宣告的函式是遞迴函式，它為自己選擇一個基本情況，即如果根值等於 null，則它簡單地返回，表明輸出中沒有可用的樹。
步驟 3：遍歷左右子分支，直到獲得等於 null 的葉子節點，使用同一函式的遞迴呼叫，但使用其左右分支。
步驟 4：對使用者透過臨時變數 temporaryHold 生成的二叉樹執行交換子演算法，該變數有助於透過自下而上的方法將左子分支資料點與右子分支資料點交換，從底部到根值交換樹中存在的子分支中的所有左子節點和子元素，直到到達根，根將只由自身交換。
演算法程式碼 - findInvertedBinaryTree 方法
function findInvertedBinaryTree (root) {
if (root === null) return;
let temporaryHold;
findInvertedBinaryTree(root.left);
findInvertedBinaryTree(root.right);
temporaryHold = root.left;
root.left = root.right;
root.right = temporaryHold;
return root
};
console.log(printTree(originalTree));
這就是問題陳述如何向我們展示從建立節點到在 BST 中列印節點，然後找到反轉二叉樹的演算法的模組化程式設計。
示例
以上演算法的組合主程式碼如下所示：
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
const printTree = (root) => {
let listOfTreeElements = [];
let queueOfTreeElements = [root];
while (queueOfTreeElements.length) {
let currentNode = queueOfTreeElements.shift();
listOfTreeElements.push(currentNode.value);
if(currentNode.left) queueOfTreeElements.push(currentNode.left);
if(currentNode.right) queueOfTreeElements.push(currentNode.right);
}
return listOfTreeElements;
}
function findInvertedBinaryTree (root) {
if (root === null) return;
let temporaryHold;
findInvertedBinaryTree(root.left);
findInvertedBinaryTree(root.right);
temporaryHold = root.left;
root.left = root.right;
root.right = temporaryHold;
return root
};
let originalTree = new Node(4);
originalTree.left = new Node(2);
originalTree.right = new Node(7);
originalTree.left.left = new Node(1);
originalTree.left.right = new Node(3);
originalTree.right.left = new Node(9);
originalTree.right.right = new Node(0);
console.log(printTree(originalTree));
console.log(' Inverted Binary Tree :');
console.log(printTree(findInvertedBinaryTree(originalTree)));
輸出
輸出如下所示：
[ 4, 2, 7, 1, 3, 9, 0 ] Inverted Binary Tree : [ 4, 7, 2, 0, 9, 3, 1 ]
時間和空間複雜度
使用遞迴方法，每個元素或節點只遍歷一次進行樹反轉，這樣時間複雜度就降低到 O(n)，而空間複雜度與二叉樹的高度成正比，或者與函式的遞迴呼叫次數（等於樹的高度）成正比，即 O(h)，其中 h 是樹的高度。
結論
這就是我們透過模組化和邏輯地思考查詢二叉搜尋樹映象影像的不同子演算法來解決上述問題陳述的方法。
609 次瀏覽
