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

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

　　　　　datatype data;

　　　　　int parent;

　　　　　int lchild;

　　　　　int rchild;

　　　　}NODE;

　　　　NODE tree[N]; // 生成N个结点的树

　　　　4) 二叉链表

　　　　5) 三叉链表

　　　　6) 哈夫曼树

　　5.二叉树的遍历

　　　先根 \

　　　中根 栈 中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树.

　　　后根 /

　　　先,中序已知求树:先序找根,中序找确定左右子树.

　　　层次遍历(队列实现)

　　6.线索二叉树(穿线树)

　　　中序线索二树树目的:利用空指针直接得到中序遍历的结果.

　　　手段(方法):左指针为空,指向前趋,右指针为空,指向后继.

　　结点结构: 

ltag Lch Data rch rtag 

　　Ltag=0,lch指向左孩子,ltag=1,指向前趋结点

　　Rtag=0,rch指向右孩子;rtag=1,指向后继结点

　　中序遍历: 1) 找最左结点(其左指针为空)

　　　　2) 当该结点的rtag=1,该结点的rch指向的就为后继

　　　　3) 当rtag=0,后继元素为右子树中最左边那个

　　N个结点的二树有空指针N+1个

　　排序查找是笔者觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!

查找 

一、 知识点　　　　/静态查找->数组　　

　　1、 什么是查找

　　　　　　　　　　\动态查找->链树

　　●顺序查找，时间复杂度 O(n)

　　●折半查找：条件：有序；时间复杂度 O(nlog2n) (时间复杂度实际上是查找树的高度)

　　●索引查找：条件：第I+1块的所有元素都大于第Ｉ块的所有元素。

　　　算法：根据index来确定X所在的块（i） 时间复杂度：m/2　　　　

　　　　　　在第Ｉ块里顺序查找X　　　　 　时间复杂度：n/2 

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

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