JS二元樹的先序中序及後序遍歷實作方法
- php中世界最好的语言原創
- 2018-04-16 15:23:302107瀏覽
這次帶給大家JS二元樹的先序中序及後序遍歷實現方法，JS二元樹先序中序及後序遍歷實現方法的注意事項有哪些，下面就是實戰案例，一起來看一下。
之前學資料結構的時候，學了二元樹的先序、中序、後序遍歷的方法，並用C語言實現了，下文是用js實現二叉樹的3種遍歷，並以動畫的形式展現遍歷的過程。
整個遍歷過程還是採用遞歸的思想，原理很粗暴也很簡單
# 先序遍歷的函數：
function preOrder(node){
if(!(node==null)){
pList.push(node);
preOrder(node.firstElementChild);
preOrder(node.lastElementChild);
}
}
# 中序遍歷的函數：
function inOrder(node) {
if (!(node == null)) {
inOrder(node.firstElementChild);
pList.push(node);
inOrder(node.lastElementChild);
}
}
後序遍歷的函數：
function postOrder(node) {
if (!(node == null)) {
postOrder(node.firstElementChild);
postOrder(node.lastElementChild);
pList.push(node);
}
}
顏色變化函數：
function changeColor(){
var i=0;
pList[i].style.backgroundColor = 'blue';
timer=setInterval(function(argument){
i++;
if(i<pList.length){
pList[i-1].style.backgroundColor="#fff";
pList[i].style.backgroundColor="blue";
}
else{
pList[pList.length-1].style.backgroundColor="#fff";
}
},500)
}核心程式碼如上，本來想寫深度優先遍歷和廣度優先遍歷。後來發現二元樹深度優先遍歷和先序遍歷相同。改日總結樹的BFS和DFS。
全部程式碼如下：
<!DOCTYPE html>
<html>
<head lang="en">
<meta charset="UTF-8">
<title></title>
<style>
.root{
display: flex;
padding: 20px;
width: 1000px;
height: 300px;border: 1px solid #000000;
margin: 100px auto;
margin-bottom: 10px;
justify-content: space-between;
}
.child_1{
display: flex;
padding: 20px;
width: 450px;
height: 260px;border: 1px solid red;
justify-content: space-between;
}
.child_2{
display: flex;
padding: 20px;
width: 170px;
height: 220px;border: 1px solid green;
justify-content: space-between;
}
.child_3{
display: flex;
padding: 20px;
width: 35px;
height: 180px;border: 1px solid blue;
justify-content: space-between;
}
input{
margin-left: 100px;
width: 60px;
height: 40px;
font:20px italic;
}
</style>
</head>
<body>
<p class="root">
<p class="child_1">
<p class="child_2">
<p class="child_3"></p>
<p class="child_3"></p>
</p>
<p class="child_2">
<p class="child_3"></p>
<p class="child_3"></p>
</p>
</p>
<p class="child_1">
<p class="child_2">
<p class="child_3"></p>
<p class="child_3"></p>
</p>
<p class="child_2">
<p class="child_3"></p>
<p class="child_3"></p>
</p>
</p>
</p>
<input type="button" value="先序">
<input type="button" value="中序">
<input type="button" value="后序">
<script type="text/javascript" src="遍历.js"></script>
</body>
</html>
js:
/**
* Created by hp on 2016/12/22.
*/
var btn = document.getElementsByTagName('input'),
preBtn = btn[0],
inBtn = btn[1],
postBtn = btn[2],
treeRoot = document.getElementsByClassName('root')[0],
pList = [],
timer = null;
window.onload=function(){
preBtn.onclick = function () {
reset();
preOrder(treeRoot);
changeColor();
}
inBtn.onclick = function () {
reset();
inOrder(treeRoot);
changeColor();
}
postBtn.onclick = function () {
reset();
postOrder(treeRoot);
changeColor();
}
}
/*先序遍历*/
function preOrder(node){
if(!(node==null)){
pList.push(node);
preOrder(node.firstElementChild);
preOrder(node.lastElementChild);
}
}
/*中序遍历*/
function inOrder(node) {
if (!(node == null)) {
inOrder(node.firstElementChild);
pList.push(node);
inOrder(node.lastElementChild);
}
}
/*后序遍历*/
function postOrder(node) {
if (!(node == null)) {
postOrder(node.firstElementChild);
postOrder(node.lastElementChild);
pList.push(node);
}
}
/*颜色变化函数*/
function changeColor(){
var i=0;
pList[i].style.backgroundColor = 'blue';
timer=setInterval(function(argument){
i++;
if(i<pList.length){
pList[i-1].style.backgroundColor="#fff";
pList[i].style.backgroundColor="blue";
}
else{
pList[pList.length-1].style.backgroundColor="#fff";
}
},500)
}
function reset(){
pList=[];
clearInterval(timer);
var ps=document.getElementsByTagName("p");
for(var i=0;i<ps.length;i++){
ps[i].style.backgroundColor="#fff";
}
}
由此可見，二元樹的遍歷思想是一樣的。之前一直把JS看做是寫各種特效的語言，現在向來是too naive了。
相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！
推薦閱讀：
以上是JS二元樹的先序中序及後序遍歷實作方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn