2022年全国计算机等级考试四级复习纲要：树
型结构
四、树型构造
2021江苏省公务员考试报名时间
线性表、栈和队列等数据构造所表达和处理的数据以线性构造为组织形式。然而，在计算机科学和计算机应用的各个领域中，存在着大量需要用更简单的规律构造加以表示的问题。因此必需讨论更简单的规律构造及相应的数据构造。树形构造就是这些更简单的构造中最重要的一类。
1.树的根本概念
树是一类重要的树形构造，其定义如下：树是n（n>0）个结点的有穷集合，满意:
（1）有且仅有一个称为根的结点;
（2）其余结点分为m（m≥0）个互不相交的非空集合，T 1 ，T 2 ，…，T m ，这些集合中的每一个都是一棵树，称为根的子树。
在树上，根结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的直接前趋。为
浙江公务员考试报名网了争论便利，我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支点。一棵树中全部结点的度的值称为该树的度。若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子（即“子女”）或子
结点。易知任何结点A的孩子B也就是A的一棵子树的根结点，父结点一样的结点互称为兄弟。一棵树上的任何结点（不包括根本身）称为根的子孙。反之若B是A的子孙，则称A是B的祖先，结点的层数（或深度）从根开头算起：根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中全部结点层数的值称为该树的高度或深度。
树（及一切树形构造）是一种“分支层次”构造。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”；所谓“层次”是指树上全部结点可以按它们的层数划分不同的“层次”。在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的规律关系（即父结点与子结点之间的邻接关系）往往用来表示数据元素之间的某种重要的、必需加以表达的关系。
用图示法表示任何树形构造时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简洁地用连线代替箭头。
2.树的根本运算包括:
①求根ROOT（T），引用型运算，其结果是结点X在树T的根结点。
②求双亲PARENT（T，X），引用型运算，其结果是结点X在树T 上的双亲结点；若X是树T的根或X不在T上，则结果为一特别标志。
山东省招生考试院电话查询
③求孩子CHILD（T，X，i），引用型运算，其结果是树T上的结
点X的第i个孩子；若X不在T上或X没有第i个孩子，则结果为一特别标志。
④建树CREATE（X，T 1 ，…，T k ）k≥1，加工型运算，其作用是建立一棵以X为根，以T 1 ，…，T k 为第1，…k棵子树的树。
⑤剪枝DELETE（T，X，i），加工型运算，其作用是删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作。
（1）二叉树的根本概念
青骄第二课堂学生登录入口
二叉树是结点的有穷集合，它或者是空集，或者同时满意下述两个条件:（1）有且仅有一个称为根的结点:
（2）其余结点分为两个互不相交的集合T 1 、T 2 ，T 1 与T 2 都是二叉树，并且T 1 与T 2 有挨次关系（T 1 在T 2 之前），它们分别称为根的左子树和右子树。
二叉树是一类与树不同的树形构造。它们的区分是：第一，二叉树可以是空集，这种二叉树称为空二叉树。其次，二叉树的任一结点都有两棵子树（固然，它们中的任何一个可以是空子树），并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。相应地，二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外，二叉树上任一结点的度定义为该结点的孩子数（即非空子树数）。除这个几个术语之外，树的其它术语也适用于二叉树。
特殊值得留意的是，由于二叉树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区分它是该结点的左子树还是右子树，这是与树不同的。
（2）二叉树的性质
在某些状况下，了解二叉树的以下性质是有帮忙的。
4.二叉树的存储构造
二叉树通常有两类存储构造，挨次存储构造和链式存储构造。
（1）二叉树的链式存储构造
二叉树有不同的链式存储构造，其中最常用的是二叉树链表与三叉链表。
其中，data域称为数据域，用于存储二叉树结点中的数据元素;lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针（这个指针及指针域有时简称为左指针）。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针（简称右指针）。二叉链表中的全部存储结点**它们的左、右指针的链接而形成一个整体。此外，每个二叉链表还必需有一个指向根结点的指针，该指针称为根指针。根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开头。值得留意的是，二叉链表中每个存储结点的每个指针域必需有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。
2023年事业单位招聘网若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则六安人事考试信息网
相应的指针为空。具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。
二叉树的链式存储构造操作便利，表达简明（二叉树的规律关系———结点间的父子关系———在二
叉链表和三叉链表中被直接表达成对应存储结点之间的指针），因而成为二叉树最常用的存储构造。然而在某些状况下，二叉树的挨次存储构造也很有用。
（2）二叉树的挨次存储构造
二叉树的挨次存储构造由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。明显，这里的关键在于结点的存储次序，这种次序应能反映结点之间的规律关系（父子关系），否则二叉树的根本运算就难以实现。
由二叉树的性质5可知，若对任一完全二叉树上的全部结点按层编号，则结点编号之间的数值关系可以精确地反映结点之间的规律关系。因此，对于任何完全二叉树来说，可以采纳“以编号为地址”的策略将结点存入作为挨次存储构造的一维数组。详细地说就是：将编号为i的结点存入一维数组的第i个单元。
在这一存储构造中，由于一结点的存储位置（即下标）也就是它的编号，故结点间的规律关系可**它们下标间的数值关系确定。来源：.examda
5.二叉树的遍历