树的介绍
1. 树的定义
树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。
把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
(01) 每个节点有零个或多个子节点;
(02) 没有父节点的节点称为根节点;
(03) 每一个非根节点有且只有一个父节点;
(04) 除了根节点外,每个子节点可以分为多个不相交的子树。
2. 树的基本术语
若一个结点有子树,那么该结点称为子树根的"双亲",子树的根是该结点的"孩子"。有相同双亲的结点互为"兄弟"。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度:结点拥有的子树的数目。
叶子:度为零的结点。
分支结点:度不为零的结点。
树的度:树中结点的最大的度。
层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1。
树的高度:树中结点的最大层次。
无序树:如果树中结点的各子树之间的次序是不重要的,可以交换位置。
有序树:如果树中结点的各子树之间的次序是重要的, 不可以交换位置。
森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。
二叉树的介绍
1. 二叉树的定义
二叉树是每个节点最多有两个子树的树结构。它有五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。
2. 二叉树的性质
二叉树有以下几个性质:TODO(上标和下标)
性质1:二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2:深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3:包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1。
2.1 性质1:二叉树第i层上的结点数目最多为 2{i-1} (i≥1)
证明:下面用"数学归纳法"进行证明。
(01) 当i=1时,第i层的节点数目为2{i-1}=2{0}=1。因为第1层上只有一个根结点,所以命题成立。
(02) 假设当i>1,第i层的节点数目为2{i-1}。这个是根据(01)推断出来的!
下面根据这个假设,推断出"第(i+1)层的节点数目为2{i}"即可。
由于二叉树的每个结点至多有两个孩子,故"第(i+1)层上的结点数目" 最多是 "第i层的结点数目的2倍"。即,第(i+1)层上的结点数目最大值=2×2{i-1}=2{i}。
故假设成立,原命题得证!
2.2 性质2:深度为k的二叉树至多有2{k}-1个结点(k≥1)
证明:在具有相同深度的二叉树中,当每一层都含有最大结点数时,其树中结点数最多。利用"性质1"可知,深度为k的二叉树的结点数至多为:
20+21+…+2k-1=2k-1
故原命题得证!
2.3 性质3:包含n个结点的二叉树的高度至少为log2 (n+1)
证明:根据"性质2"可知,高度为h的二叉树最多有2{h}–1个结点。反之,对于包含n个节点的二叉树的高度至少为log2(n+1)。
2.4 性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1
证明:因为二叉树中所有结点的度数均不大于2,所以结点总数(记为n)="0度结点数(n0)" + "1度结点数(n1)" + "2度结点数(n2)"。由此,得到等式一。
(等式一) n=n0+n1+n2
另一方面,0度结点没有孩子,1度结点有一个孩子,2度结点有两个孩子,故二叉树中孩子结点总数是:n1+2n2。此外,只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到:n0=n2+1。原命题得证!
3. 满二叉树,完全二叉树和二叉查找树
3.1 满二叉树
定义:高度为h,并且由2{h} –1个结点的二叉树,被称为满二叉树。
3.2 完全二叉树
定义:一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。
3.3 二叉查找树
定义:二叉查找树(Binary Search Tree),又被称为二叉搜索树。设x为二叉查找树中的一个结点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个结点,则key[y] <= key[x];如果y是x的右子树的一个结点,则key[y] >= key[x]。
在二叉查找树中:
(01) 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(02) 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(03) 任意节点的左、右子树也分别为二叉查找树。
(04) 没有键值相等的节点(no duplicate nodes)。
相关推荐
在计算机科学中,二叉树是一种重要的数据结构,它由节点组成,其中每个节点都...在实际应用中,通过对二叉树性质的深入理解,可以更高效地实现树的遍历、插入和删除操作,优化存储空间,以及设计出更复杂的算法结构。
### 二叉树性质5证明 #### 性质5描述 在完全二叉树中,如果按照层次顺序(从上至下,从左至右)对所有结点进行编号(第1层到第\[log_2n\]层,其中\(n\)表示结点总数),则对于任意结点\(i\)(1≤\(i\)≤\(n\)),...
L二叉树的性质及其遍历PPT教案学习.pptx
本文将详细讨论二叉树的几个关键性质及其证明。 **性质1**:二叉树第i层上的结点数目最多为2i-1(i ≥1)。这个性质通过数学归纳法可以证明。基础情况是i=1时,一个二叉树的第一层只有一个根结点,满足2i-1=20=1。...
二叉树的性质和存储结构
树、二叉树的性质和存储结构
以下是几个关键的二叉树性质: 1. 在二叉树的第i层上,最多有2^(i-1)个节点。这意味着随着层次的增加,节点的数量以指数形式增长。 2. 深度为k的二叉树最多含有2^k - 1个节点。这是因为二叉树的最大节点数是所有层...
通过对二叉树性质的分析,我们不仅能够更深刻地理解二叉树的基本结构和特点,还能了解到如何通过数学关系式来推断和验证二叉树的一些重要性质。这对于学习计算机科学中的数据结构课程非常重要,同时也是解决实际问题...
以下是二叉树的一些重要性质: 1. **非空二叉树上叶结点数等于双分支结点数加1**: 这个性质是二叉树结构的一个关键特征。如果一个非空二叉树的叶节点(没有子节点的节点)数量为n0,单分支节点(只有一个子节点的...
这是一个基于生成树的算法,可以先用回溯、递推求出二叉树,再用二叉树求解,主要用于遍历问题!
下面将详细讨论二叉树的几个关键性质。 性质1涉及到二叉树的层次结构。对于任何二叉树,第i层的节点数量最多为2^(i-1),这是因为每一层的节点数都是上一层的两倍(除了第一层,即根节点,它有0个子节点)。例如,第...
1. 插入操作:在二叉树中插入一个新节点,通常按照二叉树的性质决定新节点的位置,如在二叉搜索树(BST)中,新节点必须小于父节点(左子树)或大于父节点(右子树)。 2. 删除操作:删除一个节点时要考虑其子节点...
二叉树的创建遍历以及求二叉树的高度程序源码 先序创建 前序遍历 树的层次
在计算机科学领域,二叉树是一种基础的数据结构,它由结点构成,每个结点最多有两个子节点,分别称为左子节点和右子节点。...通过深入理解二叉树的性质和后序遍历的规律,我们可以有效地解决类似的问题。
涵盖的知识点包括树和二叉树的定义、性质、操作和应用等。 一、树和二叉树的定义 树是一种数据结构,由一个根节点和零个或多个子树组成。二叉树是一种特殊的树,其中每个节点最多有两个子节点。树和二叉树都是...
这个压缩包“二叉树性质 遍历序列和互换.zip”内包含的“二叉树性质 遍历序列和互换.ppt”很可能是关于二叉树的性质、遍历方式以及如何通过遍历序列来交换节点的讨论。在这里,我们将深入探讨这些主题。 首先,我们...
由于二叉搜索树的性质,中序遍历的结果就是递增排序的序列。 在实际应用中,二叉树排序有以下优点: - 动态性:如果需要不断插入新元素或删除元素,二叉树排序可以高效地处理这些操作。 - 空间效率:相比于其他动态...
1. 插入:在适当的位置插入一个新的节点,保持二叉树的性质。 2. 删除:找到要删除的节点,然后根据情况调整其子节点来填补空缺。 3. 查找:从根节点开始,按照二叉树的性质遍历,寻找特定值的节点。 4. 遍历:主要...
删除节点后,需要调整树结构以保持二叉树的性质。 4. **遍历二叉树**:常见的遍历方法有前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根)。这些遍历方式可以用于打印树的所有节点、计算节点值的...