考试网 >> IT认证 >> 水平 >> 软件指导 >> 程序员数据结构笔记(二)

发布时间：2006-06-28 04:46     点击：

　　●H(点)=E(边)+1

　　●个数为N的完全二叉树高度为|_LOG2n_|

　　●完全二叉树结点编号:从上到下,从左到右. 

i结点的双亲: |_i/2_| |_i-1/2_|    1    

i结点的左孩子: 2i 2i+1  2    3  

i结点的右孩子: 2i+1 2i+2 4  5  6  7 

(根) 1为起点 0为起点        

　　二叉树的存储结构:

　　　　1) 扩展成为完全二叉树,以一维数组存储。 

     A     

  B      C  

 D      E  F 

G  H    I    

数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12 

元素 A B C D E F G H 　 　 　 　 I 

　　　　2) 双亲表示法  

数组下标 0 1 2 3 4 5 6 7 8 

元素 A B C D E F G H I 

双亲 -1 0 0 1 2 2 3 3 4 

　　　　3) 双亲孩子表示法 

数组下标 0 1 2 3 4 5 … 

元素 A B C D E F … 

双亲 -1 0 0 1 2 2 … 

左子 1 3 4 　 　 　 … 

右子 2 -1 5 　 　 　 … 

结构:

　　　　typedef struct {

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。