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

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

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

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

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

2x + y = N – 1;

x   + y + z = N;

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

完毕。

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

二叉树(二)——二叉搜索树及C++实现

什么是二叉搜索树

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

二叉树节点类

本类是构成二叉树的节点类。包括三个指针,分别指向双亲节点、左孩子节点和右孩子节点,还有一个变量存储数据。如果二叉树插入和删除操作很少,可以存储高度变量,因为插入操作和删除操作需要更新一系列节点的高度值。红黑颜色是在红黑树中使用的。本类同时重载了比较、赋值和输出运算符。 Read more

二叉树(一)——基础

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

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

从图论的角度看,树等价与连通无环图。沿每个节点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

2.Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

该题的算法就是实现大数相加,不过数是低位在前,高位在后存储的。例题是:342 + 465 = 807。

Read more