数据结构（5）二叉树

今天系统学习了二叉树相关内容线性结构顺序表、链表的数据排列只有前后单一关系而二叉树属于树形结构元素之间存在一对多的关联这也是它和链表最大的区别。基础定义一棵树包含若干节点。没有前驱的顶层节点称为根节点没有后继的节点是叶子节点同时拥有前驱与后继的节点为分支节点。根节点处于第1层每向下访问一个节点层数递增。一棵二叉树规定任意节点最多只能拥有两个后继节点分为左孩子、右孩子左右顺序不能随意调换。在此基础上延伸出两种特殊二叉树满二叉树要求每一层全部填满节点所有叶子节点位于同一层完全二叉树可以理解为满二叉树按顺序从右至左、自底层向上删减节点得到节点编号连续。二叉树的性质二叉树第k层最多存在 2^{k-1} 个节点一棵满二叉树前k层节点总数为 2^k-1二叉树最核心的操作是遍历分为两大思路深度优先遍历DFS、广度优先遍历BFS。深度优先依靠递归实现根据根节点的访问顺序分为三类前序遍历根节点 → 左子树 → 右子树根左右中序遍历左子树 → 根节点 → 右子树左根右后序遍历左子树 → 右子树 → 根节点左右根广度优先遍历也叫层序遍历不再使用递归。按照从上至下、同一层从左向右的顺序依次访问节点一般依靠队列完成实现。今天动手完成了代码功能实现绝大多数函数依托递归编写构建二叉树分别实现了完全二叉树、普通非完全二叉树的创建逻辑四种遍历方式前序、中序、后序递归遍历以及借助队列实现的层序遍历统计二叉树高度递归分别求出左子树高度、右子树高度取较大值再加一二叉树销毁遵循后序遍历的思路优先释放左右子节点空间最后释放根节点避免内存泄漏。递归是学习二叉树绕不开的思路。处理任意一棵子树的逻辑和处理整棵树的逻辑完全一致。我们只需要专注单个节点需要完成的操作剩下的工作交给递归递推到下层节点。这也是二叉树大量接口选择递归实现的原因。同时也要区分两种创建方式的差异。完全二叉树可以借助数组存储数据依靠下标关系快速建立父子节点联系对于形态不规则的普通二叉树需要手动逐个建立节点之间的指向关系。在代码书写过程中需要留意边界条件。比如访问空节点时要及时终止递归否则代码会持续向下调用引发异常销毁树的时候释放内存的顺序不能颠倒一旦提前释放父节点将无法找到子节点地址。线性结构适合处理有序连续的数据而树形结构可以高效实现查找、排序相关场景。熟练掌握遍历与递归思路才能继续往后深入学习。