[理工] 资料结构书本上的定义请益

楼主: APE36 (PT乡民)   2014-03-17 15:43:42
在二元树的章节中
有提到如下的问题
若2i <= n 索引值i之左子节点被存放在索引值为2i之处。如果2i > n,则索引值i所
在节点并没有左子节点存在。
若(2i+1) <= n 索引值i之右子节点被存放在索引值为2i+1之处。如果2i+1 >n,
则索引值i所在节点并没有右子节点存在。
请问这段话的意思是说 左右子树摆放位置吗??还是??
另外一题请益 ex.如果是完全二元树,1000各节点,试问共有多少个叶节点? 分支度为1
的节点有多少个?
这题的算法好像跟算叶节点数的公式有些出入!!!希望有神人帮分析一下,感谢!!
作者: A4P8T6X9 (残废的名侦探)   2014-03-17 15:46:00
那个代表编号 i 这个点,其左右子点的编号。叶子500个,因为最后一个父点是1000/2。http://ppt.cc/ULng
作者: john35452 (小杰)   2014-03-18 23:18:00
leaf有500个,因为n0=n2+1,所以n2有499个,又因为n=n0+n1+n2,所以n1=1000-500-499=1ps. n为node总个数,而ni为分支度为i的node个数而第一个问题我觉得i应该是parent的编号,2i为其左子点的index,2i+1则为右子点,所以当编号为2i或是2i+1大于n时,因为n为总共的点数,所以代表此点不存在

Links booklink

Contact Us: admin [ a t ] ucptt.com