输入数字构建二叉搜索树,演示插入、删除和查找路径;也可以粘贴 LeetCode 风格的层序数组(如 [3,9,20,null,null,15,7])直接画出二叉树。前序、中序、后序、层序遍历会按顺序逐个高亮节点。
按层从左到右列出节点,空节点写 null,与 LeetCode 题目中的输入格式相同。
每个节点左子树上的值都小于它,右子树上的值都大于它。查找、插入、删除的时间复杂度与树高成正比:平衡时为 O(log n),按顺序插入有序数据会退化成链表,变为 O(n),这也是 AVL 树、红黑树要做旋转保持平衡的原因。删除有两个子节点的节点时,用它的中序后继(右子树中最小的节点)替换它。
“二叉搜索树”模式下输入一个或多个数字,点“插入”“删除”或“查找”,查找时会标出比较路径;“层序数组建树”模式下粘贴层序数组点“画出二叉树”。点下方的遍历按钮,节点会按访问顺序逐个高亮,同时列出遍历序列。
前序是根、左、右;中序是左、根、右;后序是左、右、根。二叉搜索树的中序遍历结果是升序序列。
用队列:先把根节点入队,每次取出一个节点访问,再把它的左右子节点依次入队,直到队列为空。
切换到“层序数组建树”,粘贴如 [3,9,20,null,null,15,7] 的数组即可,null 表示空节点。
任意节点左右子树的高度差不超过 1 的二叉树,本页右侧会显示当前树是否平衡。
叶子节点直接删除;只有一个子节点的用子节点替代;有两个子节点的,用右子树中最小的节点(中序后继)替换后再删除该后继。
最多显示 255 个节点;二叉搜索树不插入重复值,删除有两个子节点的节点时用中序后继替换。层序数组中空节点写 null,与 LeetCode 的序列化格式一致。
所有计算在浏览器本地完成,不会上传。
层序数组提示无法识别时,检查是否用英文逗号分隔、空节点是否写成 null;树太宽时可以左右滚动画布查看。