#include<stdio.h>
#include<stdlib.h>
//树与二叉树
//31已知一颗二叉树按顺序存储结构进行存储，设计一个算法，
//求编号分别为i和j的两个结点的最近公共祖先结点的值
/*算法思想：
顺序存储结构的适用范围：完全二叉树和满二叉树；
对于普通二叉树，可用空指针结点补充转换为完全二叉树；
顺序存储二叉树，数组从1开始标号；
不断的将较大的取一半，比较i和j的大小，直到i=j，表明找到了公共祖先结点
*/
elemtype Com_Ancestor(SqTree T,int i,int j)
{
if(T[i]!=null&&T[j]!=null)
{
while(i!=j)
{
if(i>j)
i=i/2;
else
j=j/2;
}
}
return T[i];
}
//32二叉树的遍历，先序、中序、后序
/*算法思想：
visit的位置；
递归：在函数体内调用自身
无论采用哪种遍历算法，所有结点都访问一次且仅访问一次，时间复杂度为O(n)，
最坏的空间复杂度为退化成单分支树，为O(n)
*/
//二叉树的链式存储结构
typedef struct BiTNode{
elemtype data;
struct BiTNode *lchild,*rchild；
}BiTNode,*BiTree;
//先序遍历
void preorder(BiTree T)
{
if(T!=null)
{
visit(T);
preorder(T->lchild);
preorder(T->rchild);
}
}
//中序
void inorder(BiTree T)
{
if(T!=null)
{
inorder(T->lchild);
visit(T);
inorder(T->rchild);
}
}
//后序
void postorder(BiTree T)
{
if(T!=null)
{
postorder(T->lchild);
postorder(T->rchild);
visit(T);
}
}
//总结
void Funorder(BiTree T)
{
if(T!=null)
{
//操作
Funorder(T->lchild);
//操作
Funorder(T->rchild);
//操作
}
}
