{数据结构}二进制与十进制转换与二叉树关系
/************************************
算法描述:假设二叉树中的左分支的标号为0,右分支的标号为1,并对二叉树增设一个头结点
,令根节点为其右孩子,则从头结点到树中任意节点所经分支的序列为一个二进制序列,可认
作是某个十进制数的二进制表示.已知一棵非空二叉树以顺序存储结构表示,试写一尽可能
简单的算法,求出与在树的顺序存储结构中下标值为i的结点对应的十进制整数
**************************************/
/**************************************************************************
实际上就是一个圈套.因为下标值i就是结点对应的十进制整数
@
/(1)
/
1
(0)/ /(1)
/ /
2 3
(0)/ / //(1)
/ / / /
4 5 6 7
如示意图所示,其实利用的就是层次与二进制的关系.也就是说,向下一层,则必定多一位
1或者0,相应的增加的就是二进制的一位,也就是相当于将原来的数进行X2(二进制特点).
而根据父母结点与孩子结点的关系,可以知道也是符合这种特性的.所以,树的顺序存储结构
中下标值i就是走过路径组成的二进制序列代表的十进制数
*******************************************************************************/
