【数据结构与算法】JS实现二叉树的非递归遍历

╰半夏微凉° 2022-11-09 14:09 18阅读 0赞

<!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <meta name="viewport" content="width=device-width, initial-scale=1.0">
        <title>Document</title>
    </head>
    </html>
    <script>
    
    function BinarySearchTree(){ 
        //节点内部类
        function Node(key){ 
            this.key = key
            this.left = null
            this.right = null
        }
        //属性
        this.root = null
    
        //方法
        //一.插入数据：insert方法:对外向用户暴露的方法
        BinarySearchTree.prototype.insert = function(key){ 
        //1.根据key创建节点
            let newNode = new Node(key)
                
            //2.判断根节点是否存在
            if (this.root == null) { 
                this.root = newNode
                //根节点存在时
            }else { 
                this.insertNode(this.root, newNode)
            }
        }
    
        //内部使用的insertNode方法:用于比较节点从左边插入还是右边插入
        BinarySearchTree.prototype.insertNode = function(node, newNode){ 
            //当newNode.key < node.key向左查找
            if(newNode.key < node.key){ 
              //情况1：node无左子节点，直接插入
              if (node.left == null) { 
                node.left = newNode
              //情况2：node有左子节点，递归调用insertNode(),直到遇到无左子节点成功插入newNode后，不再符合该情况，也就不再调用insertNode()，递归停止。
              }else{ 
                this.insertNode(node.left, newNode)
              }
            //当newNode.key >= node.key向右查找
            }else{ 
              //情况1：node无右子节点，直接插入
              if(node.right == null){ 
                node.right = newNode
              //情况2：node有右子节点，依然递归调用insertNode(),直到遇到无右子节点成功插入newNode为止
              }else{ 
                this.insertNode(node.right, newNode)
              }
            }
        }
    
    
        BinarySearchTree.prototype.preOrderTravel = function(){ 
            if(this.root){ 
              let stack = [this.root];
              while(stack.length > 0){ 
                  let node = stack.pop();
                  console.log(node.key)
                  node.right && stack.push(node.right)
                  node.left && stack.push(node.left);
              }
            } else { 
              console.log('空空如也.....')
            }
        }
        
    
        BinarySearchTree.prototype.midOrderTravel = function(){ 
          if(this.root){ 
            let stack = [this.root];
            let root = this.root.left;
            while(stack.length > 0 || root){ 
              // debugger
              while(root){ 
                stack.push(root);
                root = root.left;
              }
              root = stack.pop();
              console.log(root.key);
              root = root.right;
            }
          }
        }
    
        BinarySearchTree.prototype.postOrderTravel = function(){ 
    
          if(this.root){ 
            let stack = [this.root];
            const res = [];
            while(stack.length > 0){ 
              let node = stack.pop();
              res.push(node.key);
              if(node.left){ 
                stack.push(node.left);
              }
              if(node.right){ 
                stack.push(node.right)
              }
            }
            // 会改变原数组
            res.reverse()
          }
        }
    
        BinarySearchTree.prototype.levelTravel = function(){ 
          if(this.root){ 
            const queue = [this.root];
            const res = [];
            while(queue.length > 0){ 
              let node = queue.shift();
              console.log('xxxx', node.key);
              if(node.left){ 
                queue.push(node.left)
              }
              if(node.right){ 
                queue.push(node.right);
              }
            }
    
            console.log(res)
          }
        }
    
    }
    
    
    function isDuichen(root){ 
      if(root === null){ 
        return true;
      }
      return isDuichen2(root.left, root.right)
    }
    
    function isDuichen2(node1, node2){ 
      if(node1 === null && node2 === null){ 
        return true;
      }
      if(node1 === null || node2 === null){ 
        return false
      }
      if(node1.key !== node2.key){ 
        return false;
      }
      return isDuichen2(node1.left, node2.right) && isDuichen2(node1.right, node2.left)
    }
    
    let bst = new BinarySearchTree();
    
    // console.log(bst);
    // bst.preOrderTravel();
    // bst.preOrderTraversal(console.log)
    // bst.midOrderTravel();
    // bst.postOrderTravel()
    bst.levelTravel();
    
    
    // 非递归遍历二叉树
    // 前序
    
    
    
    </script>