今日核心任务是攻克数据结构中的二叉树,整个学习过程更像一场逻辑拆解与规律验证的实践,而非单纯的知识记忆。
从定义入手,明确二叉树“每个节点最多拥有两个子树”的核心规则,这一约束让它区别于普通树,也为后续的遍历和操作埋下了逻辑伏笔。先在草稿纸上手绘了满二叉树、完全二叉树的结构,对比两者在节点填充顺序上的差异——完全二叉树“从左到右、自上而下”的填充规则,后来才明白是为了适配数组存储,减少空间浪费,这是结构与应用场景绑定的典型体现。
下午重点突破遍历算法,这是二叉树操作的核心。我用同一棵示例树(根节点为A,左子树B、右子树C,B的左子树D)分别演练了三种深度优先遍历:前序(A-B-D-C)、中序(D-B-A-C)、后序(D-B-C-A)。最初靠“根的位置”死记顺序,但手动推导三次后发现规律:前序是“先拿根,再左再右”,中序是“左完拿根,再处理右”,后序则是“左右处理完,最后拿根”。这种从“死记”到“理解逻辑顺序”的转变,让遍历效率明显提升。
最有收获的是发现二叉树的“递归本质”。无论是求深度、找节点,还是遍历,递归解法都异常简洁——因为每棵子树本身就是一棵二叉树,符合“大问题拆解为小问题”的递归思想。我尝试用递归写了中序遍历的代码,仅需几行就实现,对比迭代解法的栈操作,更直观地感受到了数据结构特性与算法思想的适配性。
不过仍有遗留问题:完全二叉树的节点数计算(当深度为k时,节点数在2(k-1)到2k -1之间),虽然记住了公式,但对推导过程的理解还不够透彻;迭代法遍历中,栈的进出时机仍需多练才能形成条件反射。