数据结构：二叉树以及它的遍历

 var  root={
        id:1,
        left:{
            id:3,
            left:{
                id:5,
                left:{
                      id:9
                }
            },
            right:{
                  id:6
            }
              
        },
        right:{
            id:4,
            left:{
                id:7

            },
            right:{
                  id:8,
                  right:{
                       id:10
                  }
            }

        }
  };
/**
   *  递归前序
   *  对于二叉树中的任意一个节点，先打印该节点，
   *  然后是它的左子树，最后右子树
   */
  let arrId=[];

   function DLR(root){
       if(typeof root!='object' || typeof root ===null)
       {
           return;
       }
       arrId.push(root.id);
       DLR(root.left);
       DLR(root.right);
   }

   /**
    * 递归中序
    * 对于二叉树中的任意一个节点，
    * 先打印它的左子树，然后是该节点，最后右子树
    */

    function LDR(root){
        if(typeof root!='object' || typeof root ===null)
        {
            return;
        }
        LDR(root.left);
        arrId.push(root.id);
        LDR(root.right);
    }

    /**
     * 递归后序
     * 对于二叉树中的任意一个节点，
     * 先打印它的左子树，然后是右子树，最后该节点
     */

     function LRD(root){

        if(typeof root!='object' || typeof root ===null)
        {
            return;
        }
   
        LRD(root.left);
        LRD(root.right);
        arrId.push(root.id);
     }


     function DLR2(roots){
          
        let arrId=[],stack=[roots];
        while(root.length>0)
        {
            //出栈
             let root=stack.pop();
             arrId.push(root.id);
             //左侧入栈
             if(root.left)
             {
                 stack.unshift(root.left);
             }
             //右节点入栈 插入到左节点前面
             if(root.right)
             {
                 stack.unshift(root.right);
             }
        }
        return arrId;

     }

     function LDR2(roots){
          
        let arrId=[],stack=[],cur=roots;
        while(stack.length>0 || cur)
        {
            while(cur)
            {   
                stack.push(cur);
                 //不断将左侧树入栈
                 cur=cur.left?cur.left:null;
            }
            //取最后一个出栈
             let root=stack.pop();
             arrId.push(root.id);
        
             //将右节点 赋值 下一次遍历右节点的左侧树入栈
            //  left 
            //       \
            //       right
            //
             //如果没有右节点 当前 root 已经出栈  会继续上轮取值
             // left 
             cur=root.right?root.right:null;
        }
        return arrId;

     }
    /**
     * 利用栈实现后序遍历
     * 后序遍历： 左-》右=》中
     * 可以修改 先序
     * 我们可以将 先实现 中=》右=》左 然后 将数组反序就能实现
     * @param {*} roots 
     */
     function LRD2(roots){
          
        let arrId=[],stack=[roots];
        while(stack.length>0)
        {
            //取最后一个节点出栈
             let root=stack.pop();
             arrId.push(root.id);
             //左侧入栈
             if(root.left)
             {
                 stack.push(root.left);
             }
             //右节点入栈
             if(root.right)
             {
                 stack.push(root.right);
             }
        }
        return arrId.reverse();

     }