什么是父结点 根结点

父结点在数据库管理中的数据模型中，早期阶段的层次模型和网状模型中，一个属性如果有上一级，则称这个上一级是它的父结点，如果没有上一级，则这个属性则无父结点。

根结点（root）是树的一个组成部分，也叫树根。所有非空的二叉树中，都有且仅有一个根结点。它是同一棵树中除本身外所有结点的祖先，没有父结点。

树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。

扩展资料：

树（tree）是包含n（n>=0）个结点的有穷集，其中：

（1）每个元素称为结点（node）；

（2）有一个特定的结点被称为根结点或树根（root）。

（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

用括号先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如前文树形表示法可以表示为：（1（2（5（9，10）），3（6，7），4（8）））

参考资料：

百度百科---父结点

参考资料：

百度百科---根结点

首先，我们假设n和N都是内存可容纳的，也就是说N个数可以一次load到内存里存放在数组里（如果非要存在链表估计又是另一个challenging的问题了）。从最简单的情况开始，如果n=1，那么没有任何疑惑，必须要进行N-1次的比较才能得到最大的那个数，直接遍历N个数就可以了。如果n=2呢？当然，可以直接遍历2遍N数组，第一遍得到最大数max1，但是在遍历第二遍求第二大数max2的时候，每次都要判断从N所取的元素的下标不等于max1的下标，这样会大大增加比较次数。对此有一个解决办法，可以以max1为分割点将N数组分成前后两部分，然后分别遍历这两部分得到两个最大数，然后二者取一得到max2。 也可以遍历一遍就解决此问题，首先维护两个元素max1，max2（max1=max2），取到N中的一个数以后，先和max1比，如果比max1大（则肯定比max2大），直接替换max1，否则再和max2比较确定是否替换max2。采用类似的方法，对于n=2，3，4一样可以处理。这样的算法时间复杂度为O（nN）。当n越来越大的时候（不可能超过N/2，否则可以变成是找N-n个最小的数的对偶问题），这个算法的效率会越来越差。但是在n比较小的时候（具体多小不好说），这个算法由于简单，不存在递归调用等系统损耗，实际效率应该很不错 堆：当n较大的时候采用什么算法呢？首先我们分析上面的算法，当从N中取出一个新的数m的时候，它需要依次和max1，max2，max3max n比较，一直找到一个比m小的max x，就用m来替换max x，平均比较次数是n/2。可不可以用更少的比较次数来实现替换呢？最直观的方法是，也就是网上文章比较推崇的堆。堆有这么一些好处：1它是一个完全二叉树，树的深度是相同节点的二叉树中最少的，维护效率较高；2它可以通过数组来实现，而且父节点p与左右子节l，r点的数组下标的关系是s[l] = 2s[p]+1和s[r] = 2s[p]+2。在计算机中2s[p]这样的运算可以用一个左移1位 *** 作来实现，十分高效。再加上数组可以随机存取，效率也很高。3堆的Extract *** 作，也就是将堆顶拿走并重新维护堆的时间复杂度是O（logn），这里n是堆的大小。 具体到我们的问题，如何具体实现呢？首先开辟一个大小为n的数组区A，从N中读入n个数填入到A中，然后将A维护成一个小顶堆（即堆顶A[0]中存放的是A中最小的数）。然后从N中取出下一个数，即第n+1个数m，将m与堆顶A[0]比较，如果m<=A[0]，直接丢弃m。否则应该用m替换A[0]。但此时A的堆特性可能已被破坏，应该重新维护堆：从A[0]开始，将A[0]与左右子节点分别比较（特别注意，这里需要比较两次才能确定最大数，在后面我会根据这个来和败者树比较），如果A[0]比左右子节点都小，则堆特性能够保证，勿需继续，否则如左（右）节点最大，则将A[0]与左（右）节点交换，并继续维护左（右）子树。依次执行，直到遍历完N，堆中保留的n个数就是N中最大的n个数。 这都是堆排序的基本知识，唯一的trick就是维护一个小顶堆，而不是大顶堆。不明白的稍微想一下。维护一次堆的时间复杂度为O（logn），总体的复杂度是O（Nlogn）这样一来，比起上面的O（nN），当n足够大时，堆的效率肯定是要高一些的。当然，直接对N数组建堆，然后提取n次堆顶就能得到结果，而且其复杂度是O（nlogN）,当n不是特别小的时候这样会快很多。但是对于online数据就没办法了，比如N不能一次load进内存，甚至是一个流，根本不知道N是多少。 败者树：有没有别的算法呢？我先来说一说败者树（loser tree）。也许有些人对loser tree不是很了解，其实它是一个比较经典的外部排序方法，也就是有x个已经排序好的文件，将其归并为一个有序序列。败者树的思想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树：败者树的叶子节点是数据节点，然后两两分组（如果节点总数不是2的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树的优胜者中的败者（注意记录的是输的那一方），而优胜者则往上传递继续比较，一直到根节点。如果我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的败者，也就是所有叶子节点中第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数值，还要记录对应的叶子节点。如果是用链表构成的树，则内部节点需要有指针指向叶子节点。这里可以有一个trick，就是内部节点只记录败者对应的叶子节点，具体的数值可以在需要的时候间接访问（这一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对应的叶子节点需要变成一个新的数（或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败者树，从更新的叶子节点网上，依次与内部节点比较，将败者更新，胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径与之前的最小值的路径是完全相同的。内部节点记录的败者虽然称为败者，但却是其所在子树中最小的数。也就是说，只要与败者比较得到的胜者，就是该子树中最小的那个数（这里讲得有点绕了，看不明白的还是找本书看吧，对照着图比较容易理解）。 注：也可以直接对N构建败者树，但是败者树用数组实现时不能像堆一样进行增量维护，当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能，后面的分析都是对n个数构建的堆和败者树来分析的。 总而言之，败者树在进行维护的时候，比较次数是logn+1。与堆不同的是，败者树是从下往上维护，每上一层，只需要和败者节点比较一次即可。而堆在维护的时候是从上往下，每下一层，需要和左右子节点都比较，需要比较两次。从这个角度，败者树比堆更优一些。但是，请注意但是，败者树每一次维护必定需要从叶子节点一直走到根节点，不可能中间停止；而堆维护时，有可能会在中间的某个层停止，不需要继续往下。这样一来，虽然每一层败者树需要的比较次数比堆少一倍，但是走的层数堆会比败者树少。具体少多少，从平均意义上到底哪一个的效率会更好一些？那我就不知道了，这个分析起来有点麻烦。感兴趣的人可以尝试一下，讨论讨论。但是至少说明了，也许堆并非是最优的。 具体到我们的问题。类似的方法，先构建一棵有n个叶子节点的败者树，胜出者w是n个中最小的那一个。从N中读入一个新的数m后，和w比较，如果比w小，直接丢弃，否则用m替换w所在的叶子节点的值，然后维护该败者树。依次执行，直到遍历完N，败者树中保留的n个数就是N中最大的n个数。时间复杂度也是O（Nlogn） 类快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一个轴节点，将数列交换变成两部分，一部分全都小于等于轴，另一部分全都大于等于轴，然后对两部分递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的较大那一部分的数的个数j正好是n，不也就完成了在N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果jn，则最大的n个数肯定在这j个数中，则问题变成在这j个数中找出n个最大的数；否则如果j<n，则这j个数肯定是n个最大的数的一部分，而剩下的j-n个数在小于等于轴的那一部分中，同样可递归处理。 需要注意的是，这里的时间复杂度是平均意义上的，在最坏情况下，每次分割都分割成1：N-2，这种情况下的时间复杂度为O（n）。但是我们还有杀手锏，可以有一个在最坏情况下时间复杂度为O（N）的算法，这个算法是在分割数列的时候保证会按照比较均匀的比例分割，at least 3n/10-6。具体细节我就不再说了，感兴趣的人参考算法导论（Introduction to Algorithms 第二版第九章 Medians and Orders Statistics）。 还是那个结论，堆不见得会是最优的。 本文快要结束了，但是还有一个问题：如果N非常大，存放在磁盘上，不能一次装载进内存呢？怎么办？对于介绍的Naive方法，堆，败者树等等，依然适用，需要注意的就是每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。而对于类快速排序方法，稍微要麻烦一些：分批读入，假设是M个数，然后从这M个数中选出n个最大的数缓存起来，直到所有的N个数都分批处理完之后，再将各批次缓存的n个数合并起来再进行一次类快速排序得到最终的n个最大的数就可以了。在运行过程中，如果缓存数太多，可以不断地将多个缓存合并，保留这些缓存中最大的n个数即可。由于类快速排序的时间复杂度是O（N），这样分批处理再合并的办法，依然有极大的可能会比堆和败者树更优。当然，在空间上会占用较多的内存。 总结：对于这个问题，我想了很多，但是觉得还有一些地方可以继续深挖：1 堆和败者树到底哪一个更优？可以通过理论分析，也可以通过实验来比较。也许会有人觉得这个很无聊；2 有没有近似的算法或者概率算法来解决这个问题？我对这方面实在不熟悉，如果有人有想法的话可以一块交流。如果有分析错误或遗漏的地方，请告知，我不怕丢人，呵呵！最后请时刻谨记，时间复杂度不等于实际的运行时间，一个常数因子很大的O（logN）算法也许会比常数因子小的O（N）算法慢很多。所以说，n和N的具体值，以及编程实现的质量，都会影响到实际效率。

//下边的是具体的代码，不过先要添加using SystemXml;我用的是05没有这个命名空间，还有要注意你的xml文件的路径，我放在了App_Data下边，名字为Baiduxml，你要进行修改。还有问题可以加我QQ304631331

XmlDocument doc = new XmlDocument();

string XmlFilePath = ServerMapPath("App_Data/Baiduxml");

docLoad(XmlFilePath);

string str = "";

XmlNode rootnode = docSelectSingleNode("Menu");

foreach (XmlNode node in rootnodeChildNodes)

{

str += nodeAttributes["name"]Value+"<br/>";

}

ResponseWrite(str);

    名词解释

        节点: 每个元素

        父子关系: 用来连线相邻节点之间的关系

        父节点: A节点就是B节点的父节点

        子节点:  B节点就是A节点的子节点

        兄弟节点: B、C、D这三个节点的父节点是同一个节点

        根结点: 没有父节点的节点

        叶子结点: 没有子节点的节点

        节点的高度: 节点到叶子结点到最长路径(边数)  (计数起点为0, 从下往上)

        节点的深度: 根节点到这个节点经历过的边个数  (计数起点为0, 从上往下)

        节点的层数:     节点到深度 + 1  (计数起点为1)

        树的高度: 根节点的高度

    特点

        最常用的树数据结构

        每个节点最多有两个子节点(左子节点、右子节点)

         满二叉树: 叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点

         完全二叉树:  叶子节点都在最底下两层，最后一层的叶子节点都 靠左排列 ，并且除了最后一层，其他层的节点个数都要达到最大

        二叉树存储方式

            数组顺序存储法

                通过数组下标来顺序存储数据 (i表示当前节点深度,从0开始)

                根节点: i = 1，左节点:2 i，右节点: 2 i + 1，父节点: i / 2

                完全二叉树采用此方式节省内存空间

            链式存储法

                每个节点需要存储三分数据:当前节点数据、左节点指针、右节点指针,比较占用空间                

            遍历

                常用方式

                前序遍历: 树任意节点，先打印当前节点，再打印它的左子树，最后打印它的右子树

                中序遍历: 树任意节点，先打印它的左子树，再打印当前节点，最后打印它的右子树

                后序遍历: 树任意节点，先打印它的左子树，再打印它的右子树，最后打印当前节点

                二叉树的前、中、后序遍历就是一个递归的过程

                时间复杂度是O(n)

                    每个节点最多被访问两次，遍历 *** 作的时间复杂度跟节点的个数n成正比

特点

    二叉查找树为实现快速查找而生，支持快速查找一个数据、快速插入、快速删除一个数据

    特殊结构: 其左子树每个节点的值 < 树的任意一个节点的值 < 其右子树每个节点的值

            先取根节点，如果它等于要查找的数据，那就返回。

            如果要查找的数据比根节点的值小，那就在左子树中递归查找；

            如果要查找的数据比根节点的值大，那就在右子树中递归查找

            一般插入的数据在叶子节点上，从根节点开始依次比较要插入的数据和节点的大小关系

            如果插入数据比节点的数值大，并且节点的右子树为空，将新数据插到右子节点位置；

            如果不为空，就再递归遍历右子树，查找插入位置。

            如果插入数据比节点的数值小，并且节点的左子树为空，将新数据插到左子节点位置；

            如果不为空，就再递归遍历左子树，查找插入位置。

        针对要删除节点的子节点个数的不同，需分三种情况来处理

        1如果要删除的节点没有子节点，步骤如下: (如图中的删除节点55)

            只需将父节点中指向要删除节点的指针置为null

        2如果要删除的节点只有一个子节点，步骤如下: (如图中删除节点13)

            只需将父节点中指向要删除节点的指针，让它指向要删除节点的子节点即可

        3如果要删除的节点有两个子节点，步骤如下: (如图中的删除节点18)

            首先，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上；

            然后，再删除掉这个最小节点，因为最小节点肯定没有左子节点        

            删除 *** 作，有个优化方案: 就是单纯将要删除的节点标记为“已删除”，

            这种方案删除 *** 作就变简单很多，但是比较浪费内存空间

        支持快速地查找最大节点和最小节点、前驱节点和后继节点

        另外一种重要特性: 

            中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)

            因此，二叉查找树也叫作二叉排序树

        以上几种 *** 作都默认树中节点存储的都是数字，而且都是不存在键值相同的情况

        实际应用场景中采用对象的某个字段作为键值来构建二叉查找树，其他字段称为卫星数据

        如果存储的两个对象键值相同，两种解决方案

        1把值相同的数据都存储在同一个节点(采用链表或支持动态扩容的数组等数据结构)   

        2每个节点只存储一个数据，把这个新插入的数据当作大于这个节点的值来处理，如下图:

        查找 *** 作

            当查找数据时遇到值相同的节点，继续在右子树中查找，直到遇到叶子节点才停止。

            这样就把键值等于要查找值的所有节点都查找出来        

            删除 *** 作

                先查找到每个要删除的节点，然后再按前面讲的删除 *** 作的方法，依次删除

        对于同一组数据可构造不同二叉查找树。查找、插入、删除 *** 作的执行效率都不一样

        图最左边树，根节点的左右子树极度不平衡，退化成链表，查找时间复杂度为O(n)

        最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）

        时间复杂度都跟树的高度成正比，也就是O(height)

        树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示

        满二叉树: 下一层节点个数是上一层的2倍，第K层包含节点个数就是2^(K-1)

        完全二叉树: 假设最大层数是L，总的节点个数n，它包含的节点个数在1个到2^(L-1)个之间

            L的范围是[ , +1]，完全二叉树的高度小于等于

            极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求

        平衡二叉查找树: 树的高度接近logn，时间复杂度较稳定为O(logn)

    1排序对比

        散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序

        二叉查找树只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列

    2性能稳定性对比

        散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定

        最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)

    3时间复杂度对比

        散列表查找等 *** 作时间复杂度是常量级，因存在哈希冲突，这个常量不一定比logn小

        另外加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高

    4结构设计对比

        散列表构造比较复杂，需要考虑:散列函数设计、冲突解决办法、扩容、缩容等

        平衡二叉查找树只需要考虑平衡性，而且目前这个的解决方案较成熟、固定

    5空间复杂度

        散列表: 避免过多散列冲突，装载因子不能太大，特别基于开放寻址法，否则浪费太多空间

            

        

节点至少拥有nodeType（节点类型），nodeName（节点名称），nodeValue（节点值）三个基础属性

（1）元素节点---nodeType为1

（2）属性节点---nodeName为2

（3）文本节点---nodeValue为3 （文本节点包含文字、空格、换行等）

2、节点的层级

DOM根据HTML中各节点的不同作用，可将其分别划分为标签节点（元素节点）、文本节点和属性节点

（1）根节点：<html>就是根节点，有且只有一个

（2）父节点：一个节点的上级节点

（3）子节点：一个节点的下级节点

（4）兄弟节点：具有相同父节点的节点

二、节点 *** 作

1、获取父节点

elementparentNode

2、获取子节点

（1）elementchildNodes：获得的是当前元素的所有子节点的集合（所有类型的子节点）

（2）elementchildren：是一个可读的属性，返回所有子元素节点

（3）firstChild：获取第一个子节点

（4）lastChild：获取最后一个子节点

（5）firstElementChild：获取第一个元素子节点

（6）lastElementChild：获取最后一个子元素节点

3、获取兄弟节点

（1）nextSibling：获取下一个兄弟节点

（2）previousSibling：获取上一个兄弟节点

（3）nextElementSibling：获取下一个兄弟元素(标签)节点

（4）previousElementSibling：获取前一个兄弟元素节点

<body>

<div class="demo">

<div class="box">

<h2>一二三四五</h2>

<span class="child">上山打老虎</span>

<p>注意！（保护国家保护动物）</p>

</div>

</div>

<div>

<ul>

<li id="l1">红楼梦</li>

<li>水浒传</li>

<li>三国演义</li>

<li>西游记</li>

</ul>

</div>

<script>

var child = documentquerySelector('child')

consolelog(childparentNode);

var ul = documentquerySelector('ul');

var lis = ulquerySelectorAll('li');

consolelog(lis);

consolelog("通过childNodes获得的子节点",ulchildNodes);

consolelog("children",ulchildren);

consolelog("ul的子节点",ulchildNodes);

consolelog("ul第一个子节点的类型：",ulchildNodes[0]nodeType);

consolelog("ul的第二个字节点类型：",ulchildNodes[1]nodeType);//1是元素，也叫标签

consolelog("ul的第一个子节点",ulfirstChild);

consolelog("ul的最后一个子节点：",ullastChild);

consolelog("ul的第一个子元素节点",ulfirstElementChild)

consolelog("ul的最后一个子元素节点",ullastElementChild)

var span = documentquerySelector('child');

consolelog("span的兄弟节点",spannextSiblingnextSibling)

consolelog("span的前一个兄弟节点",spanpreviousElementSibling)

</script>

</body>

登录后复制



4、创建节点

（1）doumentwrite():若页面加载完毕,再次调用该方法导致页面重绘

（2）elementinnerHTML：将节点加入到元素中,导致页面部分重绘

（3）documentcreateElement()：创建节点结构清晰、效率不高

5、添加和删除节点

（1）appendChild()：将节点添加到指定父节点的已有子节点的末尾

（2）insertBefore()：将节点添加到指定父节点的已有子节点的前面

（3）removeChild(child)：删除一个指定的节点。返回值为删除的节点

6、克隆节点

cloneNode(true/false)：复制节点

（1）true：深拷贝,复制节点本身和所有子节点

（2）false(或空)：浅拷贝,只复制节点本身

1、叶子也就是leaf指在网络结构中某些计算机，它们从比较靠近中心的计算机处接收信号，而不把信号传送至较远的计算机。叶子节点就是树中最底段的节点，叶子节点没有子节点。格式化叶子节点的结构比中间节点的结构稍微复杂一点。

2、度为0的结点叫叶子结点。

3、处在树的最顶端(没有双亲)的结点叫根结点。

4、该题解答:

设该二叉树总结点数为N，叶子结点个数为n0，度为1的结点个数为n1。

下面可得两等式：

(1) N = n + n0 + n1；

依据:很显然，二叉树总结点数等于度分别为0，1，2的结点个数总和。

(2) N = 2n + n1 +1；

依据：二叉树的树杆(即左右斜线)数等于总结点数减1，这个隐含的条件很关键哦。

由(1)(2)两式即可求得: n0=n+1；

故答案为A。

扩展资料：

1、叶子节点的条目方式：

在 reiserfs 中，文件数据可以通过两种方式进行存取：直接条目（direct item）和间接条目（indirect item）。对于小文件来说，文件数据本身和 stat 数据可以一起存储到叶子节点中，这种条目就称为直接条目。

直接条目就采用图 4 所示的存储结构，不过每个条目数据体就是文件数据本身。对于大文件来说，单个叶子节点无法存储下所有数据，因此会将部分数据存储到未格式化数据块中，并通过间接条目中存储的指针来访问这些数据块。

未格式化数据块都是整块使用的，最后一个未格式化数据块中可能会遗留一部分剩余空间，大小是由对应条目头的 ih_free_space_reserved 字段指定的。图 6 给出了间接条目的存储结构。

2、叶子节点存储结构：

对于缺省的 4096字节的数据块来说，一个间接条目所能存储的数据最大可达 4048 KB（4096(4096-48)/4 字节），更大的文件需要使用多个间接条目进行存储，它们之间的顺序是通过关键字中的 offset 进行标识的。

另外，文件末尾不足一个数据块的部分也可以像小文件一样存储到直接条目中，这种技术就称为尾部封装（tail packing）。在这种情况下，存储一个文件至少需要使用一个间接条目和一个直接条目。

参考资料：

百度百科-叶子节点

以上就是关于什么是父结点 根结点全部的内容，包括:什么是父结点 根结点、如何从最大的N个数中选出最大或者最小的n个数、C# 得到xml 根节点属性等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！