javascript 代码实现二叉查找树遍历

二叉查找树

class Node{
    constructor(key) {
        var self = this;
        self.key = key;
        self.left = null;
        self.right = null;
    }
}

class Tree{
    constructor(){
        var self = this;
        self.root = null;
    }

   insert(key) {
       var self = this;
       var newNode = new Node(key);

       if (self.root == null) {
           self.root = newNode;
       } else {
           self.insertNode(self.root, newNode);
       }
   }

   insertNode(node, newNode) {
       var self = this;

       if (newNode.key < node.key) {
           if (node.left == null) {
               node.left = newNode;
           } else {
               self.insertNode(node.left, newNode);
           }
       } else {
           if (node.right == null) {
               node.right = newNode;
           } else {
               self.insertNode(node.right, newNode);
           }
       }
   }

   preOrderTraverse(callback){  // 前序遍历  根节点 左 右
       var self = this;
       self.preOrderTraverseNode(self.root, callback);
   }; 

   preOrderTraverseNode(node, callback) {
       var self = this;
        if (node !== null) {
            callback(node.key); 
            self.preOrderTraverseNode(node.left, callback); 
            self.preOrderTraverseNode(node.right, callback); 
        } 
    };

    inOrderTraverse(callback){   // 中序遍历  左 根节点  右
        var self = this;
        self.inOrderTraverseNode(self.root, callback); 
    };

    inOrderTraverseNode(node, callback) {
        var self = this;
        if (node !== null) { 
            self.inOrderTraverseNode(node.left, callback);  
            callback(node.key);                       
            self.inOrderTraverseNode(node.right, callback); 
        } 
    };

    postOrderTraverse(callback){   // 后序遍历  左 右 根节点
        var self = this;
        self.postOrderTraverseNode(self.root, callback); 
    };

    postOrderTraverseNode(node, callback) {
        var self = this;
        if (node !== null) { 
            self.postOrderTraverseNode(node.left, callback);  
            self.postOrderTraverseNode(node.right, callback); 
            callback(node.key);                       

        } 
    };
}


let tree = new Tree();
tree.insert(100);
tree.insert(101);
tree.insert(10);
tree.insert(20);

tree.preOrderTraverse(function(data){
    console.log(data)
})

tree.inOrderTraverse(function(data){
    console.log(data)
})

tree.postOrderTraverse(function(data){
    console.log(data)
})

遍历

  1. 前序遍历:根结点 ---> 左子树 ---> 右子树

  2. 中序遍历:左子树---> 根结点 ---> 右子树

  3. 后序遍历:左子树 ---> 右子树 ---> 根结点

2018-3-22 15:18:15 浏览(144)
Copyright ©leiwei | 京ICP备18013719号