二叉树二度节点和叶子节点的数量关系

二叉树二度节点和叶子节点的数量关系:

假设共有节点 N 个, 二度几点 x 个,一度节点y个, 则叶子节点个数(设为z)?

N个节点,那么共有树枝N – 1个

1个二度节点有2个树枝,叶子没有,一度节点有1个,那么推导出一共有 2x + y 个

2x + y = N – 1;

x   + y + z = N;

由以上两式得出,z = x + 1;

完毕。

叶子节点的个数=二度节点的个数+1

二叉树(一)——基础

数据结构可基于数组或链表实现,就其效率而言,二者各有长短。具体来说,前一实现方式允许我们通过下标或者秩,在常数的时间内找到目标对象;然而,一旦需要对这类结构进行修改,那么无论是插入还是删除,都需要耗费线性的时间。反之,后一实现方式允许我们借助引用或位置对象,在常数的时间内插入或删除元素;但是为了找到居于特定次序的元素,我们却不得不花费线性的时间,对整个结构进行便利查找。能够将这两个结构的有点结合起来,并回避其不足呢?本系列所要讨论的树结构,将正面回答这一问题。

有趣的是,作为树的特例,二叉树实际上并不失一般性。无论就逻辑结构还是算法功能而言,任何有根有序的多叉树,都可等价地转化并实现为二叉树。

从图论的角度看,树等价与连通无环图。沿每个节点v到根root的唯一路径所经过的数目,称作v的深度。依据深度排序,可对所有节点做分层归类。特别地,约定根节点的深度为0,故属于第0层。

任一节点v在通往根节点所经过的每个节点都是祖先(ancestor),v是它们的后代(descendant)。特别的,v的祖先/后代包括其本身,而v本身以外的祖先/后代称作真祖先(proper ancestor)/真后代(proper descendant)。

无孩子的节点称作叶节点(leaf),包括根在内的其余节点皆为内部节点(internal node)。

树T中所有节点深度的最大值为该树的高度。特别地,仅含单个节点的树的高度为0,空树高度为-1。

剑指Offer: 面试题3:数组中重复的数字

题目1

找出数组中重复的数字。

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. Read more

C语言和汇编语言的混合编程

线性汇编语言基本格式与汇编语言相同,它必须是ASCII码文件,扩展名必须是“.sa”,用作汇编优化器的输入文件。C语言中的低效率段可用线性汇编代码重写,再用汇编优化器优化,提高代码效率。(尤其是大循环中需要重复执行的函数,使用线性汇编编写可提高效率)。

c和线性汇编混合编程最重要的问题是如何让线性汇编语言产生的代码满足C语言的调用约定,所谓C语言的调用约定是指如何将传递参数放在寄存器中,如何保存和恢复寄存器之类的C编译器生成代码的规则。