算法题目整理分析--二叉树

参考js数据结构-二叉树(二叉搜索树)

参考Javascript实现二叉树算法

二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。

  • 根节点:二叉树最顶层的节点
  • 分支节点:除了根节点以外且拥有叶子节点
  • 叶子节点:除了自身,没有其他子节点

二叉树的三个性质

  • 在二叉树的第i层上,至多有2^i-1个节点
  • 深度为k的二叉树至多有2^k-1个节点
  • 对任何一棵二叉树T,如果总结点数为n0,度为2(子树数目为2)的节点数为n2,则n0=n2+1

二叉树分类

  • 满二叉树:一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树
  • 完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

二叉搜索树

    二叉搜索树满足以下的几个性质:
    若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
    任意节点的左、右子树也需要满足左边小右边大的性质

二叉搜索树,创建,遍历,搜索 方法整合

    class BinaryTree {
        constructor () {
            this.root = null
        }
        // 创建node
        createNode (key) {
            return {
                key: key,
                left: null,
                right: null
            }
        }

        // 插入
        insertNode (node, newNode) {
            if (newNode.key < node.key) {
                if (node.left) {
                    this.insertNode(node.left, newNode)
                } else {
                    node.left = newNode
                }
            } else {
                if (node.right) {
                    this.insertNode(node.right, newNode)
                } else {
                    node.right = newNode
                }
            }
        }
        insert (key) {
            let node = this.createNode(key)
            if (!this.root) {
                this.root = node
            } else {
                this.insertNode(this.root, node)
            }
        }
        // 中序遍历
        inOrderNode (node, callBack) {
            if (node !== null) {
                this.inOrderNode(node.left, callBack)
                callBack(node.key)
                this.inOrderNode(node.right, callBack)
            }
        }
        inOrder (callBack) {
            this.inOrderNode(this.root, callBack)
        }

        // 前序遍历
        preOrderNode (node, callBack) {
            if (node !== null) {
                callBack(node.key)
                this.preOrderNode(node.left, callBack)
                this.preOrderNode(node.right, callBack)
            }
        }
        preOrder (callBack) {
            this.preOrderNode(this.root, callBack)
        }
        // 后续遍历
        postOrderNode (node, callBack) {
            if (node !== null) {
                this.postOrderNode(node.left, callBack)
                this.postOrderNode(node.right, callBack)
                callBack(node.key)
            }
        }
        postOrder (callBack) {
            this.postOrderNode(this.root, callBack)
        }

        // 最大值
        maxNode (node) {
            while (node && node.right) {
                node = node.right
            }
            return node.key
        }
        max () {
            return this.maxNode(this.root)
        }

        // 最小值
        minNode (node) {
            while (node && node.left) {
                node = node.left
            }
            return node.key
        }
        min () {
            return this.minNode(this.root)
        }

        // 搜索
        searchNode (node, key) {
            if (!node) {
                return null
            }
            if (key < node.key) {
                return this.searchNode(node.left, key)
            } else if (key > node.key) {
                return this.searchNode(node.right, key)
            } else {
                return node.key
            }
        }
        search (key) {
            return this.searchNode(this.root, key)
        }
        // 移除

        removeNode (node, key) {
            if (node === null) {
                return null
            }
            if (key < node.key) {
                node.left = this.removeNode(node.left)
                return node
            } else if (key > node.key) {
                node.right = this.removeNode(node.right)
                return node
            } else {
                if (node.left === null && node.right === null) {
                    node = null
                    return node
                }
                if (node.left === null) {
                    node = node.right
                    return node
                } else if (node.right === null) {
                    node = node.left
                    return node
                }
                var aux = this.findMinNode(node.right)
                node.key = aux.key
                node.right = this.removeNode(node.right, aux.key)
            }
        }
        findMinNode (node) {
            if (!node) {
                return null
            }
            while (node && node.left) {
                node = node.left
            }
            return node

        }
        remove (key) {
            this.removeNode(this.root, key)
            return this.root
        }

    }



    let arr = [8,3,2,6,11,44,23]
    let binaryTree = new BinaryTree()

    arr.forEach(key => {
        binaryTree.insert(key)
    })


    console.log(binaryTree.root)


    binaryTree.inOrder(function (i) {
        console.log(i)
    })
    binaryTree.preOrder(function (i) {
        console.log(i)
    })
    binaryTree.postOrder(function (i) {
        console.log(i)
    })

    console.log(binaryTree.max())
    console.log(binaryTree.min())
    console.log(binaryTree.search(111))

二叉树的相关题目

二叉树中序遍历


inOrderNode (node, callBack) {
    if (node !== null) {
        this.inOrderNode(node.left, callBack)
        callBack(node.key)
        this.inOrderNode(node.right, callBack)
    }
}
inOrder (callBack) {
    this.inOrderNode(this.root, callBack)
}

二叉树路径总和(leetcode 112)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if (root === null) {
        return false
    }

    sum -= root.val

    if (!root.left && !root.right) {
        return sum === 0
    }
    return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)

};

二叉树搜寻算法

function searchNode(node, key) {
    if (!node) {
        return null
    }
    if (key < node.key) {
        return searchNode(node.left, key)
    } else if (key > node.key) {
        return searchNode(node.right, key)
    } else {
        return node
    }
}

随机浏览