Binary Tree and BST 二叉树与二叉搜索树
本文整理一般二叉树、二叉搜索树（BST）与平衡树的概念；BST 的插入、查找、删除与中序遍历的 Go 实现见我的 leetcode 仓库 下的 tree/（bst.go、bst_test.go）。 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含 n 个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n7((7)) n10((10)) n11((11)) n14((14)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n7 n5 --> n10 n5 --> n11 n7 --> n14 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n6((6)) n7((7)) n8((8)) n9((9)) n10((10)) n11((11)) n12((12)) n13((13)) n14((14)) n15((15)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n6 n3 --> n7 n4 --> n8 n4 --> n9 n5 --> n10 n5 --> n11 n6 --> n12 n6 --> n13 n7 --> n14 n7 --> n15 完全二叉树 Complete Binary Tree 对于一棵具有 n 个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。 ...