1、已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号为i和j的两个节点的最近的公共祖先结点的值。
#include <stdio.h>
/*
* 二叉树按顺序存储
* 我们应该明白一点。二叉树的顺序存储是按照完全二叉树进行存储的！！
* 对完全二叉树按从上到下，从左到右的顺序依次编码1，2...n：它是有以下关系的：
* 当i>1时，结点的双亲编号为i/2（向下取整），即当i为偶数时，其双亲的编号为i/2，它是双亲的左孩子；它是奇数时，其双亲的编号为(i-1)/2，它是双亲的右孩子
* 当2i<=n时，结点i的左孩子编号为2i，否则无左孩子；
* 当2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子；
* 结点i所在的层次（深度）为log2i+1
*
* 解题思路：
* （1）若i>j，则结点i所在层次大于等于结点j，那么若结点i的双亲结点=j，那么便是其最近公共祖先结点，否则令i=i/2，即以结点i的双亲结点为起点，继续查找
* （2） 若j>i，则结点i所在层次大于等于结点j，那么若结点j的双亲结点=i，那么便是其最近公共祖先结点，否则令j=i/2，即以结点j的双亲结点为起点，继续查找
*/
int common_ancestor(int* T,int i,int j){
if(i==j)
return i;
else if(i>j)
common_ancestor(T,i/2,j);//这里除以2就是它的双亲节点（上面提到的完全二叉树顺序存储关系）
else
common_ancestor(T,i,j/2);
}
int main(){
int T[]={0,1,2,3,0,4,0,5,0,0,6,0};
printf("%d",common_ancestor(T,2,10));
}
非递归解法：
int common_ancestor2(int* T,int i,int j){
if(T[i]!='#'&&T[j]!='#'){
while(i!=j){
if(i>j)
i=i/2;
else
j=j/2;
}
}
}
2、试给出二叉树的自下而上，从右向左的层次遍历算法。
#include <stdio.h>
/*
* 我们首先想到的层次序列都是自上而下，从左到右。欸，刚好相反，那么相反我们想到的是什么？没错，就是栈
* 首先就是利用原有的层次遍历算法，然后再出队的同时把各结点压入栈中。在所有结点都入栈之后，我们再从栈顶开始依次访问。
* 具体实现步骤：
* （1）首先把根结点入队列
* （2）把一个元素出队，接着把该结点入栈
* （3）如果该结点的左孩子不为空，那么把左孩子入队列； 如果该结点的右孩子不为空，那么把右孩子入队列；
* （4）若队列不为空。跳转到（2）继续执行
* （5）队列为空，跳出循环。对栈进行一次遍历。
*/
void InverLevel(BiTree bt){
Stack s,Queue Q;//创建栈和队列
BitNode* p;
if(bt!=NULL){
InitStack(s);//初始化栈
InitQueue(Q);//初始化队列
EnQueue(Q,bt);//根节点入队
while(!QueueEmpty(Q)){
DeQueue(Q,p);//出队列
Push(s,p);//并且入栈
if(p->lchild)
EnQueue(Q,p->lchild);//如果该结点的左孩子不为空，那么把左孩子入队列
if(p->rchild)
EnQueue(Q,p->rchild);//如果该结点的右孩子不为空，那么把右孩子入队列；
}
//跳出循环后，对栈进行一次遍历
while(!StackEmpty(s)){
Pop(s,p);
visit(p->data);
}
}
}
3、假设二叉树采用二叉链表存储结构，设计一个算法求二叉树的高度
（1）递归版
#include <stdio.h>
/*
* 递归嘛，考虑两个条件：递归体和递归出口
递归出口：
（1）如果树为空，那么返回0；
（2）如果树不为空，返回子树最大高度+1
递归体：
（1）递归该结点的左子树
（1）递归该结点的右子树
*/
int BtDepth(BiTree T){
if(T==NULL)
return 0;
int ldep=BtDepth(T->lchild);
int rdep=BtDepth(T->rchild);
if(ldep>rdep)
return ldep+1;
else
return rdep+1;
}
|