树的递归算法与非递归（迭代）的转化重点理解代码（上篇）
- 已知一颗二叉树按顺序存储的方式存储，求编号i和j两个结点的最近公共祖先结点。
算法思想：比较i和j，不断的将较大的取一半，直到i=j找到了最近公共祖先结点。
Elemtype Isert(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(i);
}
树的结构体定义：
typedet struct BiTNode{
ElemType data;//数据域
struct BiTNode *lchild,*rchild;//定义左孩子，右孩子指针
}BiTNode,*BiTree;
树的递归代码与非递归的转化问题
先序遍历：
void PreOrde(BiTree T){
if(T!=NULL){
visit(T);//访问根结点
PreOrde(T->lchild);//遍历左子树
PreOrde(T->rchild);//遍历右子树
}
}
中序遍历：
void InOrde(BiTree T){
if(T!=NULL){
InOrde(T->lchild);//遍历左子树
visit(T);//访问根结点
InOrde(T->rchild);//遍历右子树
}
}
后序遍历：
void PostOrde(BiTree T){
if(T!=NULL){
PostOrde(T->lchild);//遍历左子树
PostOrde(T->rchild);//遍历右子树
visit(T);//访问根结点
}
}
递归向非递归的转化
前序遍历非递归(迭代)算法
二叉树前序遍历的关键：先序遍历完某结点的左子树如何找到其右子树，解决问题的关键在于用一个栈，保存当前结点指针，以方便找到该结点的右子树。
算法步骤主要有两步走：
- 首先设置一个指向根结点的指针遍历左子树，边访问边入栈的操作。
- 当访问到空结点时，栈顶元素出栈，此时指针回溯访问出栈结点的右子树。
两步走的详细流程
前期准备：初始化一个栈S.
循环直到栈为空且指针为空（此时表明遍历结束，即是整个循环结束）
第一步：当p不空时循环 访问p->data 将指针p的值保存到栈中 继续遍历左子树
第二步:如果栈S不空则，将栈顶元素弹出至p（解决找到当前结点右子树问题的关键） 准备遍历p的右子树。
具体代码：
void PreOrder(BiTree T){
InitStack(S);//初始化一个栈
BiTree p=T;//p是个遍历指针初始指向根结点
while(p!=NULL||!S.isEmpty){//当p为空并且，S为空时跳出循环
if(p!=NULL){
visit(p);//先访问p结点
S.push(p);//将指针p的结点压入栈中
p=p->lchild;//继续遍历左子树直到为空跳出循环
}
if(!S.isEmpty)//如果此时栈非空
{
p=S.pop();//根结点出栈，指针回溯
//(找到右子树的关键，没有这句无法继续进行遍历可结合作图来理解)
p->rchild;//遍历右子树
}
}
}