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

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

想想下面这个算法：求链表所有数据的平均值(我也没试过)，不许偷懒，用递归试试哦!

　　递归程序员考试题目类型：1)就是链表的某些操作(比如上面的求平均值)

　　　　　　　　　　　　　　2)二叉树(遍历等) 

　　例2.判断数组元素是否递增

　　　　　int jidge(int a[],int n) {

　　　　　　if(n==1) return 1;

　　　　　　else

　　　　　　　if(a[0]>a[1]) return 0;

　　　　　　　else return jidge(a+1,n-1);

　　　　　}

　　例3.求二叉树的高度(根据二叉树的递归性质:(左子树)根(右子树))

　　　　　int depth(nodetype *root) {

　　　　　　if(root==NULL) 

　　　　　　　return 0;

　　　　　　else {

　　　　　　　h1=depth(root->lch);

　　　　　　　h2=depth(root->rch);

　　　　　　　return max(h1,h2)+1;

　　　　　　}

　　　　　 }

　　自己想想求二叉树结点个数(与上例类似)

　　例4.已知中序遍历和后序遍历,求二叉树.

　　　设一二叉树的:

　　　中序 S:E D F B A G J H C I

　　　　　　^start1 ^j ^end1

　　　后序 T:E F D B J H G I C A

　　　　　　^start2 ^end2

　　　　node *create(char *s,char *t, int start1,int start2,int end1,int end2) 

　　　　{ if (start1>end1) return NULL; //回归条件

　　　　　root=(node *)malloc(sizeof(node));

　　　　　root->data=t[end2];

　　　　　找到S中T[end2]的位置为 j

　　　　　root->lch=create(S,T,s1,j-1,start1,j+start2-start1-1);

　　　　　root->rch=create(S,T,j+1,end1,j+start2-start1,end2-1);

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

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