樹（Tree）

樹是一種非線性的數據結構，分層存儲

樹常被用來存儲具有層級關系的數據，也會被用來存儲有序列表等

樹和集合一樣，不允許相同的元素存在

樹由一組以邊連接的節點組成

一棵樹最上面的節點稱為根節點，如果一個節點下面連接多個節點，那么該節點稱為父節點，它下面的節點被稱為子節點。一個節點可以有0個、1個或多個子節點。沒有任何子節點的節點稱為葉子節點

二叉樹（Binary Tree）

二叉樹是一種特殊的樹，子節點個數不超過兩個，且分別稱為該結點的左子樹（left subtree）與右子樹（right subtree）

? ? ? ? ? ? ? ?

二叉查找樹（BST）

二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左節點，較大的值保存在右節點，這一特性使得查找效率很高

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

完全二叉樹

若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

滿二叉樹

除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹

平衡二叉樹(AVL樹)

它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

二叉樹遍歷

按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次，這個操作被稱為樹的遍歷，是對樹的一種最基本的運算。

按照根節點訪問的順序不同，樹的遍歷分為以下三種：前序遍歷，中序遍歷，后序遍歷；

前序遍歷：根節點->左子樹->右子樹

23->16->22->45->37->99

中序遍歷：左子樹->根節點->右子樹

16->22->23->37->45->99

后序遍歷：左子樹->右子樹->根節點

22->16->37->99->45->23

決定是先中后遍歷的根節點的遍歷位置，若根節點是第一個遍歷，便是先序遍歷；若根節點是第二個遍歷，便是中序遍歷；若根節點是最后一個遍歷，便是后序遍歷

js二叉查找樹（BST）

實現二叉樹的難點，是插入與刪除，需要注意，如果使用中序遍歷，便是排序了

/*** 一個簡單的二叉查找樹（BST）* @constructor*///節點定義function Node(data, left, right) {this.data = data; // 數據this.left = left; // 左節點this.right = right; // 右節點this.show = show; // 顯示節點數據}//二叉樹類function BST() {this.root = null; // 根節點this.insert = insert; // 插入節點this.preOrder = preOrder; // 先序遍歷this.inOrder = inOrder; // 中序遍歷this.postOrder = postOrder; // 后序遍歷this.find = find; // 查找節點this.getMin = getMin; // 查找最小值this.getMax = getMax; // 查找最大值this.remove = remove; // 刪除節點this.removeNode = removeNode; // 刪除節點}//顯示節點數據function show() {return this.data}//插入節點/*首先要添加新的節點，首先需要創建一個Node對象，將數據傳入該對象。其次要檢查當前的BST樹是否有根節點，如果沒有，那么表示是一棵新數，該節點就為該樹的根節點，那么插入這個過程就結束了；否則，就要繼續進行下一步了。如果待插入節點不是根節點，那么就必須對BST進行遍歷，找到合適的位置。該過程類似遍歷鏈表，用一個變量存儲當前節點，一層一層遍歷BST，算法如下：1.設值當前節點為根節點2.如果待插入節點保存的數據小于當前節點，則新節點為原節點的左節點，反之，執行第4步3.如果當前節點的左節點為null，就將新節點放到這個位置，退出循環；反之，繼續執行下一次循環4.設置新節點為原節點的右節點5.如果當前節點的右節點為null，就將新節點放到這個位置，退出循環；反之，繼續執行下一次循環 */function insert(data) {var n = new Node(data, null, null)if (this.root === null) {this.root = n} else {var current = this.rootvar parentwhile (true) {parent = currentif (data < current.data) {current = current.leftif (current === null) {parent.left = nbreak}} else {current = current.rightif (current === null) {parent.right = nbreak}}}}}//先序遍歷function preOrder(node) {if (node !== null) {console.log(node.show())preOrder(node.left)preOrder(node.right)}}//中序遍歷function inOrder(node) {if (node !== null) {inOrder(node.left)console.log(node.show())inOrder(node.right)}}//后序遍歷function postOrder(node) {if (node !== null) {postOrder(node.left)postOrder(node.right)console.log(node.show())}}//查找節點function find(data) {var current = this.rootwhile (current !== null) {if (current.data === data) {return current} else if (data < current.data) {current = current.left} else {current = current.right}}return null}//查找最小值function getMin(root) {var current = this.root || rootwhile (current.left !== null) {current = current.left}return current}//查找最大值function getMax(root) {var current = this.root || rootwhile (current.right !== null) {current = current.right}return current} /* 從BST中刪除節點的操作最為復雜，其復雜程度取決于刪除的節點位置。 如果待刪除的節點沒有子節點，那么非常簡單。 如果刪除包含左子節點或者右子節點，就變得稍微有些復雜。如果刪除包含兩個節點的節點最為復雜。 我們采用遞歸方法，來完成復雜的刪除操作，我們定義 remove() 和 removeNode() 兩個方法； 算法思想如下： 1.判斷當前節點是否包含待刪除的數據，如果包含，則刪除該節點； 2.如果不包含，則比較當前節點上的數據和待刪除樹的的大小關系。 3.如果待刪除的數據小于當前節點的數據，則移至當前節點的左子節點繼續比較； 4.如果大于，則移至當前節點的右子節點繼續比較。 5.如果待刪除節點是葉子節點（沒有子節點），那么只需要將從父節點指向它的鏈接指向變為null； 6.如果待刪除節點含有一個子節點，那么原本指向它的節點需要做調整，使其指向它的子節點； 7.最后，如果待刪除節點包含兩個子節點，可以選擇查找待刪除節點左子樹上的最大值或者查找其右子樹上的最小值， 這里我們選擇后一種。 因此，我們需要一個查找樹上最小值的方法，后面會用它找到最小值創建一個臨時節點， 將臨時節點上的值復制到待刪除節點，然后再刪除臨時節點； *///刪除操作function remove(data) {this.removeNode(this.root, data)}// 刪除節點function removeNode(node, data) {if (node === null) return nullif (data === node.data) {if (node.left === null && node.right === null) {return null}if (node.left === null) {return node.right}if (node.right === null) {return node.left}var tempNode = getMin(node.right)node.data = tempNode.datanode.right = removeNode(node.right, tempNode.data)return node} else if (data > node.data) {node.right = removeNode(node.right, data)return node} else {node.left = removeNode(node.left, data)return node}}var bst = new BST()bst.insert(23);bst.insert(45);bst.insert(16);bst.insert(37);bst.insert(99);bst.insert(22);console.log('=====先序======')bst.preOrder(bst.root)console.log('=====中序======')bst.inOrder(bst.root)console.log('=====后序======')bst.postOrder(bst.root)console.log('=====remove======')bst.remove(23)console.log(bst)console.log('最小值->' + bst.getMin(bst.root))console.log('最大值->' + bst.getMax(bst.root))復制代碼

總結

以上是生活随笔為你收集整理的js实现数据结构及算法之二叉树（Binary Tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。