本文實例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹遍歷算法。分享給大家供大家參考，具體如下：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹遍歷（先序）
先序遍歷先訪問根節(jié)點， 然后以同樣方式訪問左子樹和右子樹
代碼如下：
/* *二叉樹中，相對較小的值保存在左節(jié)點上，較大的值保存在右節(jié)點中 * * * *//*用來生成一個節(jié)點*/function Node(data, left, right) { this.data = data;//節(jié)點存儲的數(shù)據(jù) this.left = left; this.right = right; this.show = show;}function show() { return this.data;}/*用來生成一個二叉樹*/function BST() { this.root = null; this.insert = insert;}/*將數(shù)據(jù)插入二叉樹 （1）設(shè)根節(jié)點為當(dāng)前節(jié)點。 （2）如果待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點；反 之，執(zhí)行第4步。 （3）如果當(dāng)前節(jié)點的左節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 （4）設(shè)新的當(dāng)前節(jié)點為原節(jié)點的右節(jié)點。 （5）如果當(dāng)前節(jié)點的右節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 * */function insert(data) { var n = new Node(data, null, null); if (this.root == null) { this.root = n; } else { var current = this.root; var parent; while (true) { parent = current; if (data < current.data) { current = current.left;//待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點 if (current == null) {//如果當(dāng)前節(jié)點的左節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。 parent.left = n; break; } } else { current = current.right;//待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點 if (current == null) { parent.right = n; break; } } } }}/*先序遍歷 *用遞歸的方法 */function preOrder(node) { if (!(node == null)) { console.log(node.show() + " "); preOrder(node.left); preOrder(node.right); }}/* 測試代碼 */var nums = new BST();nums.insert(23);nums.insert(45);nums.insert(16);nums.insert(37);nums.insert(3);nums.insert(99);nums.insert(22);console.log("先序遍歷: ");preOrder(nums.root);運行結(jié)果：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹遍歷（中序）
中序遍歷按照節(jié)點上的鍵值，以升序訪問BST上的所有節(jié)點
代碼如下：
/* *二叉樹中，相對較小的值保存在左節(jié)點上，較大的值保存在右節(jié)點中 * * * *//*用來生成一個節(jié)點*/function Node(data, left, right) { this.data = data;//節(jié)點存儲的數(shù)據(jù) this.left = left; this.right = right; this.show = show;}function show() { return this.data;}/*用來生成一個二叉樹*/function BST() { this.root = null; this.insert = insert;}/*將數(shù)據(jù)插入二叉樹 （1）設(shè)根節(jié)點為當(dāng)前節(jié)點。 （2）如果待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點；反 之，執(zhí)行第4步。 （3）如果當(dāng)前節(jié)點的左節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 （4）設(shè)新的當(dāng)前節(jié)點為原節(jié)點的右節(jié)點。 （5）如果當(dāng)前節(jié)點的右節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 * */function insert(data) { var n = new Node(data, null, null); if (this.root == null) { this.root = n; } else { var current = this.root; var parent; while (true) { parent = current; if (data < current.data) { current = current.left;//待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點 if (current == null) {//如果當(dāng)前節(jié)點的左節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。 parent.left = n; break; } } else { current = current.right;//待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點 if (current == null) { parent.right = n; break; } } } }}/*中序遍歷*用遞歸的方法*/function inOrder(node) { if (!(node == null)) { inOrder(node.left); console.log(node.show() + " "); inOrder(node.right); }}/* 測試代碼 */var nums = new BST();nums.insert(23);nums.insert(45);nums.insert(16);nums.insert(37);nums.insert(3);nums.insert(99);nums.insert(22);console.log("中序遍歷: ");inOrder(nums.root);運行結(jié)果：
javascript數(shù)據(jù)結(jié)構(gòu)與算法--二叉樹遍歷（后序）
后序遍歷先訪問葉子節(jié)點，從左子樹到右子樹，再到根節(jié)點。
/* *二叉樹中，相對較小的值保存在左節(jié)點上，較大的值保存在右節(jié)點中 * * * *//*用來生成一個節(jié)點*/function Node(data, left, right) { this.data = data;//節(jié)點存儲的數(shù)據(jù) this.left = left; this.right = right; this.show = show;}function show() { return this.data;}/*用來生成一個二叉樹*/function BST() { this.root = null; this.insert = insert;}/*將數(shù)據(jù)插入二叉樹 （1）設(shè)根節(jié)點為當(dāng)前節(jié)點。 （2）如果待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點；反 之，執(zhí)行第4步。 （3）如果當(dāng)前節(jié)點的左節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 （4）設(shè)新的當(dāng)前節(jié)點為原節(jié)點的右節(jié)點。 （5）如果當(dāng)前節(jié)點的右節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù) 執(zhí)行下一次循環(huán)。 * */function insert(data) { var n = new Node(data, null, null); if (this.root == null) { this.root = n; } else { var current = this.root; var parent; while (true) { parent = current; if (data < current.data) { current = current.left;//待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點 if (current == null) {//如果當(dāng)前節(jié)點的左節(jié)點為null，就將新的節(jié)點插入這個位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次while循環(huán)。 parent.left = n; break; } } else { current = current.right;//待插入節(jié)點保存的數(shù)據(jù)小于當(dāng)前節(jié)點，則設(shè)新的當(dāng)前節(jié)點為原節(jié)點的左節(jié)點 if (current == null) { parent.right = n; break; } } } }}/*后序遍歷 *用遞歸的方法 */function postOrder(node) { if (!(node == null)) { postOrder(node.left); postOrder(node.right); console.log(node.show() + " "); }}/* 測試代碼 */var nums = new BST();nums.insert(23);nums.insert(45);nums.insert(16);nums.insert(37);nums.insert(3);nums.insert(99);nums.insert(22);console.log("后序遍歷: ");postOrder(nums.root);運行結(jié)果：
希望本文所述對大家JavaScript程序設(shè)計有所幫助。
新聞熱點
疑難解答
