在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。

二叉树的第i层至多拥有 2^(i-1) 个节点数;深度为k的二叉树至多总共有 2^(k+1) - 1 个节点数,而总计拥有节点数匹配的,称为“满二叉树”;深度为k有n个节点的二叉树,当且仅当其中的每一节点,都可以和同样深度k的满二叉树,序号为1到n的节点一对一对应时,称为“完全二叉树”。对任何一棵非空的二叉树T,如果其叶片(终端节点)数为n0,分支度为2的节点数为n2,则n0 = n2 + 1。

与普通树不同,普通树的节点个数至少为1,而二叉树的节点个数可以为0;普通树节点的最大分支度没有限制,而二叉树节点的最大分支度为2;普通树的节点无左、右次序之分,而二叉树的节点有左、右次序之分。

二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉查找树和二元堆积,并应用于高效率的搜索和排序。

Read More

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

Read More

摘要:随机函数可以说是用途很广。可是,系统提供的random函数,一般符合正态分布,所以说,这是伪随机函数。甚至在一些场合是非随机函数。为了满足项目需要,必须实现均匀分布。在此,分享博主实现均匀随机函数的实现过程与方法。

Read More

摘要:对于计算机科学而言,算法是一个非常重要的概念。它是程序设计的灵魂,是将实际问题同解决该问题的计算机程序建立起联系的桥梁。文章主要介绍一些常用的算法思想。

Read More

MD5的全称是Message-Digest Algorithm 5,在90年代初由MIT的计算机科学实验室和RSA Data Security Inc发明,经MD2、MD3和MD4发展而来。

MD5将任意长度的“字节串”变换成一个128bit的大整数,并且它是一个不可逆的字符串变换算法,换句话说就是,即使你看到源程序和算法描述,也无法将一个MD5的值变换回原始的字符串,从数学原理上说,是因为原始的字符串有无穷多个,这有点象不存在反函数的数学函数。

MD5的典型应用是对一段Message(字节串)产生fingerprint(指纹),以防止被“篡改”。举个例子,你将一段话写在一个叫 readme.txt文件中,并对这个readme.txt产生一个MD5的值并记录在案,然后你可以传播这个文件给别人,别人如果修改了文件中的任何内容,你对这个文件重新计算MD5时就会发现。如果再有一个第三方的认证机构,用MD5还可以防止文件作者的“抵赖”,这就是所谓的数字签名应用。

MD5还广泛用于加密和解密技术上,在很多操作系统中,用户的密码是以MD5值(或类似的其它算法)的方式保存的, 用户Login的时候,系统是把用户输入的密码计算成MD5值,然后再去和系统中保存的MD5值进行比较,而系统并不“知道”用户的密码是什么。

Read More
  • page 1 of 1
Author's picture

Chars

Currently engaged in iOS development, learning Unity, like to study all kinds of novelty


iOS developer @ZAKER


Guangzhou, China