数据结构-二叉搜索树-javascript

深度非递归遍历(前序/中序/后序)
层序遍历

class Node{
    constructor(element, parent){
        this.element = element;
        this.parent = parent;
        this.left = null;
        this.right = null;
    }
}

class Tree{
    constructor(){
        this.root = null;
        this.size = 0;
    }

    insert(index, element){
        if(element === undefined){
            element = index;
            index = this.size;
        }
        if(index < 0 || index > this.size) throw new Error('index is out of boundary');
        if(this.root === null){
            this.root = new Node(element, null);
            this.size++;
            return;
        }
        let current = this.root;
        
        while(current){
            let compare = current.element - element;
            if(compare > 0){
                if(!current.left){
                    this.size ++;
                    current.left = new Node(element, current);
                    return;
                }else{
                    current = current.left;
                }
                
            }else if(compare < 0){
                if(!current.right){
                    this.size ++;
                    current.right = new Node(element, current);
                    return;
                }else{
                    current = current.right;
                }
            } else if(compare === 0){
                return;
            }
        }
    }

    preorder(){
        // 根节点入栈
        // 根节点出栈
        // 根节点的右节点入栈
        // 根节点的左节点入栈
        // 左节点出栈
        let stack = [this.root];
        let current;
        while(stack && (current=stack.pop())) {
            console.log(current.element);
            if(current.right){
                stack.push(current.right);
            }
            if(current.left){
                stack.push(current.left);
            }
        }
    }

    inorder(){
        // 根节点入栈
        // 根节点的左节点入栈
        // 如果左节点还有左子节点,继续入栈;没有左子节点,出栈,右子节点入栈
        let stack = [this.root];
        let current = this.root;
        while(current && stack.length > 0){
            if(current.left){
                stack.push(current = current.left);
            }else{ //没有左子节点,那么要出栈,当前节点的右子节点入栈
                current = stack.pop();
                console.log(current.element);
                if(current.right){
                    stack.push(current = current.right);
                }
            }
        }
    }

    postorder(){
        // 入栈 
        // 指针指向入栈节点的左节点
        // 取栈 出栈
        let stack=[];
        let stackCount=[];
        let index = -1;
        let current = this.root;
        while(current || index > -1){
            if(current){// 入栈
                stack[++index] = current;
                stackCount[index] = 1;
                current = stack[index].left;
            }else{ // 指针指向节点为null,看栈顶元素是否可以取栈
                if(stackCount[index] === 1){
                    // 取栈
                    stackCount[index] = 2;
                    // 取出栈顶元素的右子节点
                    current = stack[index].right;
                }else{ // 指针指向null,栈顶元素已经读取过,符合出栈条件
                    // 出栈
                    let temp = stack[index--];
                    console.log(temp.element);
                    current = null; // 指针置为null,下一个循环取栈或者出栈
                }
            }
        }  
    }

    levelTraverse(){
        if(!this.root) return;
        let stack = [this.root];
        let index = 0;
        let current;
        while(current = stack[index++]){
            console.log(current.element);
            if(current.left){
                stack.push(current.left);
            }
            if(current.right){
                stack.push(current.right);
            }
        }

    }
}

let arr = [10,8,19,6,15,22,20];
let tree = new Tree();
arr.forEach(item => {
    tree.insert(item);
});

// console.dir(tree,{depth:100});
console.log('pre',10,8,6,19,15,22,20);
tree.preorder();
console.log('in',6,8,10,15,19,20,22);
tree.inorder();
console.log('post',6,8,15,20,22,19,10);
tree.postorder();
console.log('level',10,8,19,6,15,22,20);
tree.levelTraverse();