[数据结构与算法]JS版数据结构—树（学习一篇足矣）

树的深度与广度优先遍历

深度优先遍历：尽可能的搜索树的分支。
广度优先遍历：先访问离根节点最近的节点。

深度优先遍历

第一步：访问根节点
第二部：对根节点的children挨个进行深度优先遍历

const dfs=(root)=>{
    console.log(root.val);
    //递归
    root.children.forEach(dfs);
};
dfs(tree);//调用

广度优先遍历

第一步：新建一个队列，把根节点入队
第二部：把队头出队并访问
第三步：把队头的children挨个入队
第四步：重复第二，三步，直到队列为空

const bfs=(root)=>{
    //根节点入队
    const 1=[root];
    while(q.lenght>0){
        //队头出队并访问
        const n=q.shift();
        console.log(n.val)
        //把队头的children挨个入队
        n.children.forEach(child=>{
             q.push(child);
        })
     }
}
bfs(tree)

二叉树的先中后序遍历

二叉树是什么？

1.书中?每个节点?最多只能有两个子节点。
2.在JS中通常用Object来模拟二叉树。

先序遍历算法口诀

第一步：访问根节点
第二步：对根节点的?左?子树进行先序遍历。
第三步：对根节点的?右?子树进行先序遍历

• 递归版

//导入二叉树
const bt=require('./bt')

const preorder=(root)=>{
   //如果根节点为空，直接返回
   if(!root){return;}
   //访问根节点
    console.log(root.val)
   //访问左子树
    preorder(root.left)
   //访问右子树
    preorder(root.right)
}

• 非递归版

  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); 
     }
  }

中序遍历算法口诀

第一步：对根节点的?左?子树进行中序遍历
第二部：访问根节点
第三步：对根节点的?右?子树进行中序遍历。

• 递归版

  //导入二叉树
  const bt=require('./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;//指针指向右节点遍历
   }
}

后序遍历算法口诀

第一步：对根节点的?左?子树进行后序遍历
第二步：对根节点的?右?子树进行后序遍历
第三步：访问根节点

• 递归版

//导入二叉树
const bt=require('./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 stack=[root];//帮组我们实现先序遍历
      const outputStack=[];//实现倒序的
      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)
      }
  }