数据结构 --- 树

[coderliush]

二叉树的定义

二叉树的作用

二叉树的遍历

前中后序 tree 结构

const orderTree = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 3,
            left: {
                value: 5,
                left: null,
                right: null
            },
            right: {
                value: 6,
                left: null,
                right: null
            }
        },
        right: {
            value: 4,
            left: {
                value: 7,
                left: null,
                right: {
                    value: 9,
                    left: null,
                    right: null
                }
            },
            right: {
                value: 8,
                left: null,
                right: null
            }
        }        
    },
    right: {
        value: 10,
        left: null,
        right: null
    } 
}

前序遍历

遍历顺序：根节点 ---> 左子树 ---> 右子树

1. 先访问根节点
2. 对左子树进行前序遍历
3. 对右子树进行前序遍历 输出： 1 2 3 5 6 4 7 9 8 10 递归遍历

   function preOrder(node) {
   if (node === null) return
   console.log(node.value)
   preOrder(node.left)
   preOrder(node.right)
   }

   非递归遍历 在栈中，打印出根节点值，push 进去右子树，左子树。先进后出弹出的左子树，右子树遍历。

   function preOrder(node) {
   if (!node) return
   const stack = [node]
   while (stack.length) {
       const n = stack.pop()
       console.log(n.value)
       if (node.right) stack.push(n.right) 
       if (node.left) stack.push(n.left)  
   }
   }

   中序遍历

   遍历顺序：左子树 ---> 根节点 ---> 右子树

4. 对左子树中序遍历
5. 访问根节点
6. 对右子树中序遍历 输出：5 3 6 2 7 9 4 8 1 10 递归遍历

   function inOrder(node) {
   if (!node) return
   preOrder(node.left)
   console.log(node.value)
   preOrder(node.right)
   }

   非递归遍历

   function inOrder = (node) => {
   if (!node) return
   const stack = []
   let p = node
   while (stack.length || p) {
       while (p) {
           stack.push(p)
           p = p.left
       }
       const n = stack.pop()
       console.log(n.value)
       p = n.right
   }
   }

   后序遍历

   遍历顺序：左子树 ---> 右子树 ---> 根

7. 对左子树后序遍历
8. 对右子树后序遍历
9. 访问根节点 输出： 5 6 3 9 7 8 4 2 10 1 递归遍历

   function postOrder(node) {
   if (!node) return
   postOrder(node.left)
   postOrder(node.right)
   console.log(node.value)
   }

   非递归遍历 前序遍历根左右，将左右调换 push到新的栈 根右左，弹出即左右根

   function postOrder = (node) => {
   if (!node) return
   const stack = [root]
   const outputStack = []
   while (stack.length) {
       const n = stack.pop()
       outputStack.push(n)
       if (node.left) stack.push(n.left) 
       if (node.right) stack.push(n.right) 
   }
   while (outputStack.length) {
       const n = outputStack.pop()
       console.log(n.value)
   }
   }

   深度广度 tree 结构

   const tree = {
   value: 1,
   children: [
       {
           value: 2,
           children: [
               {
                   value: 3, 
                   children: [
                       {
                           value: 5,
                           children: []
                       },
                       {
                           value: 6,
                           children: []
                       }
                   ]
               },
               {
                   value: 4,
                   children: [
                       {
                           value: 7,
                           children: [
                               {
                                   value: 9,
                                   children: []
                               }
                           ]
                       },
                       {
                           value: 8,
                           children: []
                       }
                   ]
               }
           ]
       },
       {
           value: 10,
           children: []
       }
   ]
   }

   广度遍历

   按层级一层层的遍历 输出：1 2 10 3 4 5 6 7 8 9

   function bfs (node) {
     let queue = [tree]
   for (let i = 0; i < queue.length; i++) {
     const item = queue[i];
     console.log(item.name)
     if (Array.isArray(item.children) && item.children.length > 0) {
       queue.push(...item.children)
     }
   }
   }

   深度遍历

   对每一个子节点深度遍历

   function dfs (node) {
   console.log(node.value)
   node.children.forEach( dfs )
   }