任意一棵二叉树
结点个数＝总度数＋1
任意一棵二叉树中，度为0的结点总比度为2的结点多一个。
7*2+10*1+1=25
树的度——也即是宽度,简单地说,就是结点的分支数.以组成该树各结点中最大的度作为该树的度;树中度为零的结点称为叶结点或终端结点.树中度不为零的结点称为分枝结点或非终端结点.除根结点外的分枝结点统称为内部结点.
首先，在一颗二叉树中，有以下性质：
1、结点的数目=所有结点度数之和+1
2、叶子结点数目=度为2的结点数+1
度为2的结点数n2=7，所以叶子结点数n0=8
度为1的n1=10
故结点总数N=n0+n1+n2=25
任何一棵二叉树
度为零的节点总比度为2的节点多一个
结点=边+1=10+7*2+1=25
总度数+1=节点个数
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
京ICP备号-4
扫一扫，把题目装进口袋JAVA树节点的一个问题
[问题点数：40分，结帖人yangzj1992]
本版专家分：0
结帖率 100%
CSDN今日推荐
本版专家分：951
本版专家分：951
本版专家分：0
结帖率 100%
本版专家分：951
本版专家分：0
结帖率 100%
本版专家分：2743
本版专家分：253
本版专家分：0
结帖率 100%
本版专家分：0
结帖率 100%
本版专家分：2743
匿名用户不能发表回复！|
CSDN今日推荐求二叉树结点与叶子结点个的问题 - 知乎有问题，上知乎。知乎作为中文互联网最大的知识分享平台，以「知识连接一切」为愿景，致力于构建一个人人都可以便捷接入的知识分享网络，让人们便捷地与世界分享知识、经验和见解，发现更大的世界。6被浏览<strong class="NumberBoard-itemValue" title="分享邀请回答添加评论分享收藏感谢收起添加评论分享收藏感谢收起写回答豆丁微信公众号
君，已阅读到文档的结尾了呢~~
用C语言实现树重建问题课程设计论文
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于C语言的树重建问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口数据结构中你需要知道的关于树的一切 - 技术翻译 - 开源中国社区
数据结构中你需要知道的关于树的一切
【已翻译100%】
英文原文：
推荐于 8个月前 (共 20 段, 翻译完成于 11-13)
参与翻译&(5人)&: ,
当你刚开始学习编程的时候，将数组作为“主要数据结构”来学习是很常见的。
最终，你也会学习到哈希表。如果你正在攻读计算机科学学位，你肯定需要参加一门数据结构的课程。在课上你将会学到邻接链表、队列和栈。这些数据结构都被称作是“线性”的，因为他们都有逻辑上的起点和终点。
当我们开始学习树和图的时候，这两个数据结构确实会让人困惑，因为它们存储数据不是线性方式了。这两种数据结构都用特定的方式存储数据。
这篇文章帮助你更好的理解树形数据结构并帮你弄清楚你对它的疑问。
本篇文章我们将会学习到：
树是什么？
树的术语及其工作原理
如何用代码实现树形结构
让我们开始学习之旅吧。:）
&翻译得不错哦！
当开始编程时，人们更容易理解线性数据结构，而不是像树和图这样的数据结构。
树是众所周知的非线性数据结构。它们不以线性方式存储数据，而是按层次组织数据。
让我们举个现实生活中的例子
当我说层次方式意味着什么？
想象一个有所有辈分关系的家谱：祖父母、父母、子女、兄弟姐妹们等等。我们通常按层次结构组织家谱。
上面的图是我的家谱。Tossico 、Akikazu 、Hitomi 和 Takemi 是我的祖父母。
Toshiaki 和 Juliana 是我的父母。
TK 、Yuji 、Bruno 和 Kaio 是我父母的孩子（我和我的兄弟们）。
另一个层次结构的例子是企业的组织结构。
在 HTML 中，文档对象模型（DOM）是树形结构的。
HTML 标签包含其他的标签。我们有一个 head 标签和 body 标签。这些标签包含特点的元素。head 标签中有 meta 和 title 标签。body 标签中有在用户界面展示的标签，如 h1 、a 、li 等等。
&翻译得不错哦！
术语的定义
树是被称为结点的实体的集合。结点由边连接。每个结点包含值或数据，并且每个结点可能有也可能没有子结点。
树的首结点叫根结点。如果这个根结点被其他结点所连接，那么根结点是父结点，与根结点连接的是子结点。
所有的结点由边连接。这是树形结构的重要部分，因为它管理结点间的关系。
没有子节点的叶子节点是树的最后一个节点。像真正的大树一样，我们可以看到树上有根、枝干和树叶。
其他需要理解的重要概念是高度和深度。
树的高度是到叶子结点的长度。
结点的深度是它到根结点的长度。
根是树的最顶端结点。
边是两个结点之间的连接。
子结点是具有父节点的结点。
父结点是与子节点有连接的结点。
叶子结点是树中没有子结点的结点。
高度是树到叶子结点的长度。
深度是结点到根结点的长度。
&翻译得不错哦！
现在我们来讨论一个特殊的树类型。我们把它叫作二叉树。
“在计算机科学领域，二叉树是一种树形数据结构，它的每个节点最多有两个孩子，被叫作左孩子和右孩”
我们来看一个二叉树的例子。
我们来写一个二叉树
在实现一个二叉树时，我们首先要注意的是，二叉树是节点的集合。每一个节点有三个属性：值(value)，左孩子(left_child)，以及右孩子(right_child)。
那么我们怎么才能实现一个有这三个属性的简单二叉树呢？
class&BinaryTree:
&&&&def&__init__(self,&value):
&&&&&&&&self.value&=&value
&&&&&&&&self.left_child&=&None
&&&&&&&&self.right_child&=&None
好，这就是我们的二叉树类。
当我们实例化一个对象时，我们把值（节点的相关数据）作为参数传递给类。看上面类的左孩子和右孩子。两个都被赋值为None。
因为当我们创建节点时，它还没有孩子，只有节点数据。
&翻译得不错哦！
测试下代码。
tree&=&BinaryTree('a')
print(tree.value)&#&a
print(tree.left_child)&#&None
print(tree.right_child)&#&None
我们可以将字符串'a'作为值传给二叉树节点。如果将值、左孩子、右孩子输出的话，我们就可以看到这个值了。
下面开始插入部分的操作。那么我们需要做些什么工作呢？
有两个要求：
如果当前的节点没有左孩子，我们就创建一个新节点，然后将其设置为当前节点的左孩子。
如果已经有了左孩子，我们就创建一个新节点，并将其放在当前左孩子节点的位置。然后再将左孩子节点置为新节点的左孩子。
画出来就像下面这样。:)
&翻译得不错哦！
下面是插入操作的代码：
def&insert_left(self,&value):
&&&&if&self.left_child&==&None:
&&&&&&&&self.left_child&=&BinaryTree(value)
&&&&&&&&new_node&=&BinaryTree(value)
&&&&&&&&new_node.left_child&=&self.left_child
&&&&&&&&self.left_child&=&new_node
再次强调，如果当前节点没有左孩子，我们就创建一个新节点，并将其置为当前节点的左孩子。否则，就将新节点放在左孩子的位置，再将原左孩子置为新节点的左孩子。
同样，我们编写插入右孩子的代码。
def&insert_right(self,&value):
&&&&if&self.right_child&==&None:
&&&&&&&&self.right_child&=&BinaryTree(value)
&&&&&&&&new_node&=&BinaryTree(value)
&&&&&&&&new_node.right_child&=&self.right_child
&&&&&&&&self.right_child&=&new_node
但是这还不算完成。我们得测试一下。
我们来构造一个像下面这样的树：
总结分析下这棵树：
有一个根节点
b的右孩子是d（b没有左孩子）
c的左孩子是e
c的右孩子是f
e和f都没有孩子
&翻译得不错哦！
下面是整棵树的实现代码：
a_node&=&BinaryTree('a')
a_node.insert_left('b')
a_node.insert_right('c')
b_node&=&a_node.left_child
b_node.insert_right('d')
c_node&=&a_node.right_child
c_node.insert_left('e')
c_node.insert_right('f')
d_node&=&b_node.right_child
e_node&=&c_node.left_child
f_node&=&c_node.right_child
print(a_node.value)&#&a
print(b_node.value)&#&b
print(c_node.value)&#&c
print(d_node.value)&#&d
print(e_node.value)&#&e
print(f_node.value)&#&f
好，插入结束。
现在，我们来思考一下树的遍历。
遍历树有两种选择：深度优先搜索（DFS）和广度优先搜索（BFS）。
DFS是用来遍历或搜索树数据结构的算法。从根节点开始，在回溯之前沿着每一个分支尽可能远的探索。&
BFS是用来遍历或搜索树数据结构的算法。从根节点开始，在探索下一层邻居节点前，首先探索同一层的邻居节点。
下面，我们来深入了解每一种遍历算法。
&翻译得不错哦！
深度优先搜索（Depth-First Search，DFS）
DFS&在回溯和搜索其他路径之前找到一条到叶节点的路径。让我们看看这种类型的遍历的示例。
此算法的结果是 1–2–3–4–5–6–7 。
让我们分解下。
从根节点（1）开始。输出之。
进入左孩子（2）。输出之。
然后进入左孩子（3）。输出之。（此节点无子孩子）
回溯，并进入右孩子（4）。输出之。（此节点无子孩子）
回溯到根节点，然后进入其右孩子（5）。输出之。
进入左孩子（6）。输出之。（此节点无子孩子）
回溯，并进入右孩子（7）。输出之。（此节点无子孩子）
当我们深入到叶节点时回溯，这就被称为&DFS&算法。
既然我们对这种遍历算法已经熟悉了，我们将讨论下&DFS&的类型：前序、中序和后序。
&翻译得不错哦！
这和我们在上述示例中的作法基本类似。
输出节点的值。
进入其左孩子并输出之。当且仅当它拥有左孩子。
进入右孩子并输出之。当且仅当它拥有右孩子。
def&pre_order(self):
&&&&print(self.value)
&&&&if&self.left_child:
&&&&&&&&self.left_child.pre_order()
&&&&if&self.right_child:
&&&&&&&&self.right_child.pre_order()
示例中此树的中序算法的结果是3–2–4–1–6–5–7。
左孩子优先，之后是中间，最后是右孩子。
现在让我们编码实现之。
def&in_order(self):
&&&&if&self.left_child:
&&&&&&&&self.left_child.in_order()
&&&&print(self.value)
&&&&if&self.right_child:
&&&&&&&&self.right_child.in_order()
进入左孩子并输出之。当且仅当它有左孩子。
输出节点的值。
进入右孩子并输出之。当且仅当它有右孩子。
&翻译得不错哦！
以此树为例的后序算法的结果为 3–4–2–6–7–5–1 。
左孩子优先，之后是右孩子，中间的最后。
让我们编码实现吧。
def&post_order(self):
&&&&if&self.left_child:
&&&&&&&&self.left_child.post_order()
&&&&if&self.right_child:
&&&&&&&&self.right_child.post_order()
&&&&print(self.value)
进入左孩子并输出之。这当且仅当它拥有左孩子。
进入右孩子并输出之。这当且仅当它拥有右孩子。
输出节点的值。
&翻译得不错哦！
我们的翻译工作遵照 ，如果我们的工作有侵犯到您的权益，请及时联系我们