C++ 数据结构专题 - 树

Question

如题所述

Answer 1

树与二叉树

树的概念在数据结构中用来概括传递关系的一种数据结构。树由结点和边组成，结点抽象为根、子结点、叶子结点，边抽象为连接结点的连线。在树中，根结点置于最上方，向下延伸出子结点，形成子树。叶子结点为度为 0 的结点，且树可以为空树。树的层次从根结点开始计算，结点的度表示子树的棵数，树的最大度为树的度。边数等于结点数减一，且树中不存在环。

树的性质包括：可以没有结点，称为空树；结点的层次从根结点开始计算；结点的深度是指从根结点开始自顶向下逐层累加至该结点的深度值；结点的高度是从最底层叶子结点开始自底向上逐层累加至该结点的高度值；树的深度和高度在树中相等；多棵树组合在一起称为森林。

二叉树的递归定义包括：要么二叉树为空树，要么由根结点、左子树和右子树组成，其中左子树和右子树都是二叉树。递归定义是自身定义自身，通过递归式将大问题分解为与原问题性质相同的小问题，递归边界是停止递归的条件。二叉树中每个结点的子结点个数不超过2，但左右子树严格区分，不能随意交换位置。二叉树的递归定义在二叉树算法实现中非常重要。

层次概念：在二叉树中，如果将树看作家谱，那么层次就是辈分。根结点为第一层，其子结点为第二层，以此类推。结点的孩子结点、父亲结点、兄弟结点、祖先结点和子孙结点分别定义为孩子结点为结点的子树的根结点，父亲结点为孩子的父亲结点；与该结点同父亲的结点为兄弟结点；如果存在一条从结点 X 到结点 Y 的从上至下的路径，那么 X 是 Y 的祖先结点，Y 是 X 的子孙结点。

二叉树的存储结构使用链表定义，每个结点有两个指针域，分别指向左子树和右子树的根结点，不存在的子树指向 NULL。二叉树的常用操作包括建立、查找、修改、插入和删除。查找操作是在给定数据域的条件下，在二叉树中找到所有数据域为给定数据域的结点，并将它们的数据域修改为给定数据域。查找操作使用递归完成，递归式是对当前结点的左子树和右子树分别递归，递归边界是当前结点为空时到达死胡同。二叉树结点的插入位置是数据域在二叉树中查找失败的位置，通过递归查找确定插入位置。二叉树结点的插入和查找操作的代码需要使用引用，以修改原变量。

二叉树的创建过程与结点的插入过程类似。创建二叉树时，通常将需要插入的数据存储在数组中，然后使用插入函数将它们一一插入二叉树中，并返回根结点的指针。在建立二叉树的过程中，可以直接边输入数据边插入结点。

完全二叉树的存储结构可以使用数组来实现。对一棵完全二叉树，按照从上到下、从左到右的顺序编号（从1开始），可以得到每个结点的编号顺序。对于结点x，其左孩子的编号为2x，右孩子的编号为2x+1。完全二叉树可以通过一个大小为2k的数组存放所有结点信息，其中k为完全二叉树的最大高度，根结点位于数组的1号位。通过数组下标表示结点编号，左右孩子的编号可以直接计算得到。数组的元素顺序为该完全二叉树的层序遍历序列。判断某个结点是否为叶子结点的标志是其左子结点编号大于结点总数，判断空结点的标志是结点下标大于结点总数。