您好,登錄后才能下訂單哦!
二叉查找樹是由節(jié)點和邊組成的。
我們可以定義一個節(jié)點類Node,里面存放節(jié)點的數(shù)據(jù),及左右子節(jié)點,再定義一個用來顯示數(shù)據(jù)的方法:
//以下定義一個節(jié)點類 function Node(data,left,right){ // 節(jié)點的鍵值 this.data = data; // 左節(jié)點 this.left = left; // 右節(jié)點 this.right = left; // 顯示該節(jié)點的鍵值 this.show = show; } // 實現(xiàn)show方法 function show(){ return this.data; }
再定義一個二叉查找樹類BST,該類中有定義樹的根節(jié)點,初始化為null,然后定義插入節(jié)點的方法,還有一邊遍歷的方法:
// 二叉查找樹BST // 有一個節(jié)點屬性,還有一些其他的方法,以下定義一個二叉查找樹BST類 function BST(){ // 根節(jié)點初始化為空 this.root = null; // 方法 // 插入 this.insert = insert; // 中序遍歷 this.inorder = inorder; // 先序遍歷 this.preorder = preorder; // 后序遍歷 this.postorder = postorder; } //實現(xiàn)insert插入方法 function insert(data){ // 創(chuàng)建一個節(jié)點保存數(shù)據(jù) var node = new Node(data,null,null); // 下面將節(jié)點node插入到樹中 // 如果樹是空的,就將節(jié)點設(shè)為根節(jié)點 if(!this.root){ this.root = node; }else{ //樹不為空 // 判斷插在父節(jié)點的左邊還是右邊 // 所以先要保存一下父節(jié)點 // var parent = this.root; var current = this.root; var parent; // 如果要插入的節(jié)點鍵值小于父節(jié)點鍵值,則插在父節(jié)點左邊, // 前提是父節(jié)點的左邊為空,否則要將父節(jié)點往下移一層, // 然后再做判斷 while(true){ // data小于父節(jié)點的鍵值 parent = current; if(data < parent.data){ // 將父節(jié)點往左下移(插入左邊) // parent = parent.left; current = current.left; // 如果節(jié)點為空,則直接插入 if(!current){ // ?。?!此處特別注意,如果就這樣把parent賦值為node,也僅僅只是parent指向node, // 而并沒有加到父元素的左邊?。?!根本沒有加到樹中去。所以要先記住父元素,再把當(dāng)前元素加入進(jìn)去 parent.left = node; break; } }else{ // 將父節(jié)點往右下移(插入右邊) current = current.right; if(!current){ parent.right = node; break; } } } } } //實現(xiàn)inorder遍歷方法(左中右) function inorder(node){ if(node){ inorder(node.left); console.log(node.show()); inorder(node.right); } } // 先序遍歷(中左右) function preorder(node){ if(node){ console.log(node.show()); preorder(node.left); preorder(node.right); } } // 后序遍歷(左右中) function postorder(node){ if(node){ preorder(node.left); preorder(node.right); console.log(node.show()); } }
測試:
// 后序遍歷(左右中) function postorder(node){ if(node){ postorder(node.left); postorder(node.right); console.log(node.show()); } } // 實例化一個BST樹 var tree = new BST(); // 添加節(jié)點 tree.insert(30); tree.insert(14); tree.insert(35); tree.insert(12); tree.insert(17); // 中序遍歷 tree.inorder(tree.root); // 先序遍歷 tree.preorder(tree.root); // 后序遍歷 tree.postorder(tree.root);
結(jié)果:
中序遍歷:
先序遍歷:
后序遍歷:
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。