树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把他叫做树是因为它看起来像一棵倒挂的树,也就说它的根朝上,而叶朝下的。它具有以下的特点:
节点的度:一个节点含有的子树的个数称为该节点的度,如上图:A的为6
树的度:一棵树中,最大的节点的度称为树的度,如上图:树的度为6
叶子节点或终端节点:度为0的节点称为叶节点,如上图:B,C,H,I...等节点为叶节点
双亲节点或父亲节点:若一个节点含有子节点,则这个节点称为其子节点的父节点,如上图:A是B的父节点
孩子节点或子节点:一个节点若含有的子树的根节点称为该节点的子节点,如上图:B是A的孩子节点
根结点:一棵树中没有双亲结点的结点
节点的层次:从根开始定义起,根为第一层,根的子节点为第二层,以此类推
树的高度或深度:树中节点的最大层次,如上图:树的高度为4
非终端节点或分支节点:度不为0的节点,如上图:D,E,F,G...等节点为分支节点
兄弟节点:具有相同父亲节点的节点互为兄弟节点,如上图:B,C互为兄弟节点
堂兄弟节点:双亲在同一层的节点互为堂兄弟,如上图:H,I互为堂兄弟节点
节点祖先:从根到该节点所经分支上的所有节点,如上图:A是所有节点的祖先
子孙:以某节点为根的子树中任一节点都称为该节点的子孙,如上图:所有节点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林
树的结构相对于线性表就比较复杂了,要储存表示起来就比较麻烦了,实际中树有很多表示方式,如:双亲表示法,孩子兄弟表示法等等。这里我们了解一下最常用的孩子兄弟表示法。
class Node { ? ? ? ? int value;? ? ? ? ? ? ? ? ? ? ? ? //树中存储的数据 ? ? ? ? Node firstChild;? ? ? ? ? ? ? //第一个孩子引用 ? ? ? ? Node nextBrother;? ? ? ? ?//下一个兄弟引用 }
文件系统是操作系统中负责管理文件存储和访问的组成部分,而树结构在这一领域中扮演着至关重要的角色。以下是树在文件系统管理中的几个关键应用:
总的来说,树结构在文件系统的设计和管理中发挥着多方面的作用,从基本的目录管理到高级的数据索引和存储优化,都离不开这种灵活而强大的数据结构。
Linux的文件系统管理:
一棵二叉树是节点的一个有限集合,或者是由一个根节点加上两棵树被为左子树和右子树的二叉树组成。
二叉树的特点:
上图给出了几种特殊的二叉树形态,从左往右依次是:空树,只有根节点的二叉树,节点只有左子树,节点只有右子树,节点的左右子树均存在,一般二叉树都是由上述基本形态结合而形成的。
上取整
比如:假设一棵完全二叉树中共有1000个节点,则该二叉树中__个叶子节点,__个非叶子节点,__个节点只有左孩子,__个节点只有右孩子。
完全二叉树的性质是:除了最后一层外,其他各层的节点数都达到最大个数,并且最后一层的节点都集中在该层最左边的若干位置上。
首先,对于一棵完全二叉树,如果其节点总数为n,则它的层数k(从根节点开始计数)满足: 2k?1≤n<2k,对于本题,n=1000,则:29=512≤1000<210=1024,所以,k=10。
接下来,我们分析各部分的节点数:
综上,该完全二叉树有489个叶子节点,511个非叶子节点,233个节点只有左孩子,256个节点只有右孩子。
二叉树的存储结构分为:顺序存储和类似于链表的链式存储。我们先来看下链式存储,二叉树的链式存储是通过一个个的节点引用起来的,最常见的表示方式有二叉和三叉表示方式,具体如下:
//孩子表示法 class Node { ????????int val;????????????????//数据域 ? ? ? ? Node left;???????????//左孩子的引用,常常代表左孩子为根的整棵左子树 ? ? ? ? Node right;????????//右孩子的引用,常常代表右孩子为根的整棵右子树 } //孩子双亲表示法 class Node { ? ? ? ? int val;????????????????//数据域 ? ? ? ?Node left;? ? ? ? ? ?//左孩子的引用,常常代表左孩子为根的整棵左子树 ? ? ? ? Node right; ???????//右孩子的引用,常常代表右孩子为根的整棵右子树 ? ? ? ? Node parent;????//当前节点的根节点 }
所谓的遍历是指沿着某条搜索路线,依次对树中的每个结点均做一次且做一次访问。访问结点所做的操作就依赖于具体的应用问题(比如:打印节点内容,节点内容加一)。遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算的基础。而二叉树的遍历是指按照某种规则访问树中每个节点的过程,确保每个节点被访问一次且仅一次。通常有四种基本的遍历方法:
DLR
,其中D
代表访问根节点,L
和R
分别代表遍历左、右子树。LDR
。对于二叉搜索树(BST),这种遍历方式可以得到节点的升序排列。LRD
。值得一提的是,在编程实践中,递归是实现这些遍历方法的常见方式,但也可以使用栈或队列等数据结构以非递归的方式实现。不同的遍历策略适用于不同的场景,例如,在二叉搜索树中查找特定值时常用中序遍历,而在执行某些类型的树操作时可能会选择其他类型的遍历。
根据以上的概念,我们可以得到以下二叉树的四种遍历方式的结果:
前序遍历:ABDEHCFG
中序遍历:DBEHAFCG
后序遍历:DEHBFGCA
层序遍历:ABCDEFGH