更新时间：2018-11-22 16:04作者：王华老师
1. 输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
A: 递归方法逆序输出，栈方法逆序输出。
(任意实现一种既可)
void PrintListUsingRecursicve(pListNode head)
{
if(head!=NULL)
{
PrintListUsingRecursicve(head->m_pNext);
printf("%d/n",head->m_nKey);
}
}
void PrintListUsingStack(pListNode head)
{
Stack s;
s.top=0;
pListNode p=head;
do{
push(&s,p->m_nKey);
p=p->m_pNext;
}while(p!=NULL);
while(!IsEmpty(&s))
{
printf("%d/n",pop(&s));
}
}
2. 二元树的深度
题目：输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径，最长路径的长度为树的深度。
#include
#include
#include
#include
#define MAXLEN 100
#define MAXNUM 10
typedef int Tree[MAXLEN];
Tree bt;
int GetDeep(int i)
{
int l=0,r=0;
if(bt[i*2]!=-1)
{
l=GetDeep(i*2)+1;
}
if(bt[i*2+1]!=-1)
{
r= GetDeep(i*2+1)+1;
}
return l>r?l:r;
}
int main()
{
int i=0;
memset(bt,-1,sizeof(bt));
for(i=1;i<=MAXNUM;i++)
bt[i]=i;
bt[(i-1)*2]=i*2;
printf("%d /n",GetDeep(1));
return 0;
}
3. 整数的二进制表示中1的个数
题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
(关键是能不能想到后面的那个方法，只要想到这个方法既可)
int Bit1inInt(int i)
{
int result=0;
do{
result+=i&1;
}while(i=i>>1);
return result;
}
4. 从上往下遍历二元树
题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
(先序，中序，后序三种方式实现)
如果从上往下，从左到右的话只有一种遍历的方式：广度优先遍历。
#include
#include
#include
#include
#define MAXLEN 100
#define MAXNUM 10
typedef int Tree[MAXLEN];
Tree bt;
typedef struct queue
{
int begin,end;
int space[MAXLEN];
}Queue;
int main()
{
int i=0;
memset(bt,-1,sizeof(bt));
for(i=1;i<=MAXNUM;i++)
bt[i]=i;
Queue qe;
qe.begin=0;qe.end =0;
qe.space[qe.end++]=bt[1];
while(qe.begin!=qe.end)
{
if(bt[2*qe.space[qe.begin]]!=-1)//lchild
{
qe.space[qe.end++]=bt[2*qe.space[qe.begin]];
}
if(bt[2*qe.space[qe.begin]+1]!=-1)//rchild
{
qe.space[qe.end++]=bt[2*qe.space[qe.begin]+1];
}
qe.begin++;
}
printf("--------------------/n");
for(i=0;i
printf("%d ",qe.space[i]);
return 0;
}
先序，中序，后序三种方式的只是遍历二元树
typedef int Tree[MAXLEN];
Tree bt;
void PreOrderTraverse(int i)
{
if(bt[i]==-1) {return ;}
printf("%d ",bt[i]);
PreOrderTraverse(i*2);//lchild
PreOrderTraverse(i*2+1);//rchild
}
void InOrderTraverse(int i)
{
if(bt[i]==-1) {return ;}
InOrderTraverse(i*2);//lchild
printf("%d ",bt[i]);
InOrderTraverse(i*2+1);//rchild
}
void PostOrderTraverse(int i)
{
if(bt[i]==-1) {return ;}
PostOrderTraverse(i*2);//lchild
PostOrderTraverse(i*2+1);//rchild
printf("%d ",bt[i]);
}
int main()
{
int i=0;
memset(bt,-1,sizeof(bt));
for(i=1;i<=MAXNUM;i++)
bt[i]=i;
printf("/n---------------/n");
PreOrderTraverse(1);
printf("/n---------------/n");
InOrderTraverse(1);
printf("/n---------------/n");
PostOrderTraverse(1);
return 0;
}
5. 查找链表中倒数第k个结点
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
(最快的方法，只遍历一遍)
int FindCoundDownInList(pListNode head,int num)
{
pListNode p1,p2;
p1=p2=head;
while(num-->0 && p1!=NULL) p1=p1->m_pNext;
if(p1==NULL) return 0;
else{
while(p1!=NULL)
{
p1=p1->m_pNext;
p2=p2->m_pNext;
}
return p2->m_nKey;
}
}