JS-数据结构-二叉树-1

二叉树的基本操作

插入

/* 创建结点 */
function Node(data,left,right){
    this.data = data;
    this.left = left;
    this.right = right;
}
Node.prototype.show = function(){
    console.log(this.data);
}
function Tree(){
    this.root = null;//构造空树
}
Tree.prototype = {
    insert(data){
        let node = new Node(data,null,null);
        if(!this.root){
            /* 如果是一颗空树 */
            this.root = node;
            return;
        }
        let curNode = this.root;
        let parent;/* 暂存父级结点，回退时使用 */
        while(curNode){
            parent = curNode;
            if(data<parent.data){
                /* 构建一棵搜索二叉树左小右大 */
                curNode = curNode.left;/* 继续搜索左子树 */
                if(!curNode){
                    /* 到达叶 */
                    parent.left = node;
                    return;
                }
            }
            else{/* 继续搜索右子树 */
                curNode = curNode.right;
                if(!curNode){
                    parent.right = node;
                    return;
                }
            }

        }
    },
}

遍历,深度计算

Tree.prototype = {
    ......
    preOrder(root){
        if(!root){
            return null;
        }
        root.show();
        this.preOrder(root.left);
        this.preOrder(root.right);
    },
    middleOrder(root){
        if(!root){
            return null;
        }
        
        this.middleOrder(root.left);
        root.show();
        this.middleOrder(root.right);
    },
    laterOrder(root){
        if(!root){
            return null;
        }
        
        this.laterOrder(root.left);
        this.laterOrder(root.right);
        root.show();
    },
    getMin(root){
        let cur = root;
        while(cur){
            if(!cur.left){
                return cur;
            }
            cur = cur.left;
        }
    },
    getMax(root){
        let cur = root;
        while(cur){
            if(!cur.right){
                return cur;
            }
            cur = cur.right;
        }
    },
    getDeep(root,deep){//返回深度
        let deep = deep||0;/* 使用递归计算深度，如何获取到上一层的deep？添加参数deep并使用短路或判断，若deep为undefined则为0 */
        if(root){
            deep++;
            let leftDeep=this.getDeep(root.left,deep);
            let rightDeep = this.getDeep(root.right,deep);
            return Math.max(leftDeep,rightDeep);
        }
        return deep;

    }
}

树查找

function get(data,root){
    if(!root){
        return "未找到匹配的结点";
    }
    if(data < root.data){
        /* 在左子树 */
        this.get(data,root.left);
    }
    else if(data > root.data){
        /* 在右子树 */
        this.get(data,root.right);
    }
    else{
        return root;
    }
}

遍历非递归写法

中序遍历

function middleOrder(root){
    let result = [];
    let stack = [];
    let cur = root;
    while(cur||stack.length>0){
        while(cur){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        result.push(cur.data);
        cur = cur.right;
    }
    return result;
}

前序遍历

function preOrder(root){
    let result = [];
    let stack = [];
    let cur = root;
    while(cur||stack.length>0){
        while(cur){
            result.push(cur.data);
            stack.push(cur);
        }
        cur = stack.pop();
        cur = cur.right;
    }
    return result;
}

后序遍历

function preOrder(root){
    let result = [];
    let stack = [];
    let cur = root;
    while(cur||stack.length>0){
        while(cur){
            result.push(cur.data);
            stack.push(cur);
        }
        cur = stack.pop();
        cur = cur.right;
    }
    return result;
}

赏

谢谢你请我吃糖果