JavaScript實作資料結構 -- 樹

樹

樹是一種抽象的分層資料模型，例如前端常見的DOM樹：

JavaScript中沒有樹，但是可以用數組和對象來模拟樹。

以虛拟DOM為例：vdom就是JS用數組和對象來模拟的樹。

vdom = {
    type: 'div',  
    props: {     
        'id': 'content'
    },
    children: [   
        {
            type: 'ul',
            props: {
                'class': 'list'
            },
            children: {
                {
                    type: 'li',
                    props: '',
                    children: ['選項一']
                }
            }
        }
    ]
}
           

樹的常用操作

定義樹

const tree = {
	    val: 'a',
	    children:[
	        {
	            val: 'b',
	            children:[
	                {
	                    val: 'c',
	                    children:[
	                        {
	                            val: 'd',
	                            children:[]
	                        }
	                    ]
	                },
	                {
	                    val: 'e',
	                    children:[]
	                }
	            ]
	        },
	        {
	            val: 'f',
	            children:[
	                {
	                    val: 'g',
	                    children:[]
	                }
	            ]
	        }
	    ]
	}
           

深度優先周遊

深度優先周遊就是盡可能深的搜尋樹的分支。

深度優先周遊就像我們看書一樣，一頁一頁的往後翻看。

深度優先周遊過程

• 通路根節點；
• 再把每個子節點當作根節點進行深度周遊；

代碼實作

//深度優先周遊
	const dfs = (root) => {
	    //console.log(root.val);
	    root.children.forEach(dfs);
	}
	//調用深度優先周遊
	dfs(tree);
           

廣度優先周遊

廣度優先周遊就是盡可能通路離根節點（樹最頂端的節點）近的節點。

廣度優先周遊也像我們看書一樣，不過他先看目錄和各個章節是什麼内容，然後再一頁一頁的翻看。

廣度優先周遊過程

• 建立隊列，把根節點入隊；
• 把對頭出隊并通路；
• 把對頭的子節點挨個入隊；
• 重複前兩步；

代碼實作

// 廣度優先周遊
	const bfs = (root) => {
	    const q = [root];
	    while(q.length > 0){
	        const n = q.shift();
	        //console.log(n.val);
	        n.children.forEach( child => {
	            q.push(child);
	        } )
	    }
	}
	bfs(tree);
           

二叉樹

每個節點最多有兩個子節點的樹叫二叉樹。

二叉樹的常用操作

定義二叉樹

//定義二叉樹
	const bt = {
	    val: 1,
	    left:{
	        val: 2,
	        left:{
	            val: 4,
	            left:null,
	            right:null
	        },
	        right:{
	            val: 5,
	            left:null,
	            right:null
	        }
	    },
	    right:{
	        val: 3,
	        left:{
	            val: 6,
	            left:null,
	            right:null
	        },
	        right:{
	            val: 7,
	            left:null,
	            right:null
	        }
	    }
	}
           

前序周遊

前序周遊過程

根 => 左 => 右

• 通路根節點；
• 對根節點的左子樹進行前序周遊；
• 對根節點的右子樹進行前序周遊；

代碼實作

用遞歸實作前序周遊：

//前序周遊
	const preorder = (root) => {
	    if(!root){
	        return ;
	    }
	    console.log(root.val);
	    preorder(root.left);
	    preorder(root.right);
	}
	
	preorder(bt);
           

用棧實作前序周遊：

const preorder = (root) => {
    if(!root)return ;
    const stack = [root];
    while(stack.length){
        const n = stack.pop();
        console.log(n.val);
        if(n.right)stack.push(n.right);
        if(n.left)stack.push(n.left);
    }
}

preorder(bt);
           

中序周遊

中序周遊過程

左 =>根 => 右

• 對根節點的左子樹進行前序周遊；
• 通路根節點；
• 對根節點的右子樹進行前序周遊；

代碼實作

用遞歸實作中序周遊：

const inorder = (root) => {
    if(!root){
        return ;
    }
    inorder(root.left);
    console.log(root.val);
    inorder(root.right);
}

inorder(bt);
           

用棧實作中序周遊：

const inorder = (root) => {
	    if(!root){
	        return ;
	    }
	    const stack = [];
	    let p = root;
	    while(stack.length || p){
	        while(p){
	            stack.push(p);
	            p = p.left;
	        }
	        const n = stack.pop();
	        console.log(n.val);
	        p = n.right;
	    }
	}
	
	inorder(bt);
           

後序周遊

後序周遊過程

左 => 右 => 根

• 對根節點的左子樹進行前序周遊；
• 對根節點的右子樹進行前序周遊；
• 通路根節點；

代碼實作

const postorder = (root) => {
    if(!root){
        return ;
    }
    postorder(root.left);
    postorder(root.right);
    console.log(root.val);
}

postorder(bt);
           

const postorder = (root) => {
	    if(!root){
	        return ;
	    }
	    const outputstack = [];
	    const stack = [root];
	    while(stack.length){
	        const n = stack.pop();
	        outputstack.push(n);
	        if(n.left) stack.push(n.left);
	        if(n.right) stack.push(n.right);
	    }
	    while(outputstack.length){
	        const n = outputstack.pop();
	        console.log(n.val);
	    }
	}
	
	postorder(bt);