当前位置：首页 > news >正文

软考-软件设计师中级备考 5、数据结构树和二叉树

news 来源：原创 2025/5/25 21:01:32

1、树的基本概念

节点的度：节点拥有的子树数目。例如，若一个节点有 3 棵子树，其度为 3。
树的度：树中节点的最大度数。如树中所有节点的度最大为 4，则树的度是 4。
叶子节点：度为 0 的节点，也叫终端节点，它没有子节点。
分支节点：度不为 0 的节点，也称为非终端节点。
内部节点：除根节点和叶子节点外的分支节点。
父节点：若节点 A 有子节点 B，则 A 是 B 的父节点。
子节点：节点的下属节点，如 B 是 A 的子节点。
兄弟节点：具有相同父节点的节点互为兄弟节点。
层次：根节点在第 1 层，根的子节点在第 2 层，以此类推，节点的层次是从根到该节点的路径长度加 1。

2、二叉树的概念与分类

二叉树：每个节点最多有两个子树的树结构，分别称为左子树和右子树。
满二叉树：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。
完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。
非完全二叉树：不满足完全二叉树条件的二叉树。

3、二叉树的重要特性

性质 1：在二叉树的第 i 层上至多有个节点（i≥1）。
性质 2：深度为 k 的二叉树至多有个节点（k≥1）。
性质 3：对任何一棵二叉树 T，如果其终端节点数为，度为 2 的节点数为，则。

4、二叉树的遍历

前序遍历：先访问根节点，然后前序遍历左子树，最后前序遍历右子树。例如，对于二叉树root->left->right，前序遍历顺序是root、left、right。
中序遍历：先中序遍历左子树，然后访问根节点，最后中序遍历右子树。如对于二叉树root->left->right，中序遍历顺序是left、root、right。
后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点。例如，对于二叉树root->left->right，后序遍历顺序是left、right、root。
层次遍历：从根节点开始，按层次从左到右依次访问节点。

5、反向构造二叉树

根据给定的遍历序列（如前序、中序或后序遍历序列）来构造二叉树。通常利用前序遍历确定根节点，中序遍历确定左右子树的节点，然后递归地构建二叉树。例如，已知前序遍历序列为ABDECF，中序遍历序列为DBEAFC，可以确定 A 是根节点，然后根据中序序列可知DBE是左子树节点，FC是右子树节点，再继续递归构建左右子树。

6、树转二叉树

将普通树转换为二叉树的方法是：先把树中每个节点的第一个子节点作为二叉树中该节点的左子节点，然后把该节点的兄弟节点作为二叉树中该节点的右子节点。例如，对于一棵树，将根节点的最左边子节点作为二叉树根节点的左子节点，根节点的其他子节点依次作为左子节点的右子节点，以此类推。

7、查找二叉树（二叉排序树）

定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉排序树。
查找：从根节点开始比较，若查找值小于根节点值，则在左子树中继续查找；若大于根节点值，则在右子树中继续查找，直到找到或确定不存在。

8、构造霍夫曼树（最优）

霍夫曼树是带权路径长度最短的二叉树。
构造方法：根据给定的权值集合，将权值最小的两个节点合并成一个新节点，新节点的权值为这两个节点权值之和，然后将新节点加入集合，重复上述步骤，直到集合中只剩下一个节点，该节点就是霍夫曼树的根节点。例如，给定权值集合{3, 5, 2, 7}，先选择 2 和 3 合并成 5，然后选择 5 和 5 合并成 10，最后 10 和 7 合并成 17，得到霍夫曼树。

9、线索二叉树

线索二叉树是对二叉树的一种改进，通过利用二叉树中的空指针域来存放节点的前驱和后继信息。
若节点的左指针为空，则将其指向该节点的前驱节点；若节点的右指针为空，则将其指向该节点的后继节点。这样可以方便在遍历二叉树时快速找到节点的前驱和后继，提高遍历效率。

10平衡二叉树

平衡二叉树是一种特殊的二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。
插入和删除节点时，可能会破坏平衡二叉树的平衡性质，需要通过旋转操作来调整树的结构，以保持平衡。例如，常见的旋转操作有左旋、右旋、先左旋后右旋、先右旋后左旋等。