• 自顶向下搜索：常用先序遍历；
• 自底向上搜索：常用后序遍历；
• 从左到右搜索：常用中序遍历；

9.6 day29 一棵顺序存储二叉树，求编号i和j两个结点的最近公共祖先结点编号(从1开始）

int same_parents(SqTree T,int i,int j){
	int i_par = i/2;
	int j_par = j/2;
	while(i_par != 1 && j_par != 1){
			if(i_par == j_par)
				return i_par;
			else if(i_par < j_par)
				i_par = i_par/2;
			else
				j_par = j_par /2
	}
	return 1;
}

9.8 day30 二叉树的遍历

typedef struct BiTNode{
	int data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
//递归先序
void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}		
}
//非递归中序
	//树不空：则结点入栈，p向其左子树遍历；
	//树空栈不空，出一个，p向其（出栈结点）右孩子遍历；
	//树空栈空，遍历结束；
	//口诀：“入栈一直想左走，出栈访问右子树”。
void InOrder(BiTree T){
	InitStack(S);//栈初始化
	BiTree p = T;
	while(p!=NULL || !IsEmpty(S)){//二叉树和栈有一个不空就继续循环
		if(p){
			push(S,p);
			p = p->lchild;
		}
		else{//s不空,p空（树空栈不空）
			pop(S,p);
			visit(p);//第二次遇到该结点时才访问
			p = p->rchild;
		}
	}//while end
	return ;
}

9.10 day31 先序遍历非递归

void PreOrder(BiTree T){
	InitStack(S);
	BiTree p = T;
	while(p!=NULL || !IsEmpty(S)){
		if(p){
			visit(p);//第一次遇到该结点时就访问
			push(S,p);
			p = p->lchild;
		}
		else{
			pop(S,p);
			p = p->rchild;
		}
	}//while end
	return ;
}

9.12 day32 后序遍历非递归

复习的时候画个树自己模拟一遍；

• p为空的两种情况
  • p有右孩子且未访问，则右孩子入栈，p指向其左孩子（此时一定为空？）
  • p没有右孩子，则p出栈并反问，r指向p，p重置为NULL进入下一次循环；

bool GetTop(SqStack S,BiTree &x){
	if(S.top == -1)
		return false;
	x = S.data[S.Top];//x记录栈顶元素
	return true;
}

void PostOrder(BiTree T){
	InitStack(S);
	BiTree p = T;
	BiTree r = NULL;//r指向最近访问的结点
	while(p || !isEmpty(S)){
		if(p){
			push(S,p);
			p = p->lchild;//和中序一样的
		}
		else{
			GetTop(S,p);
			if(p->rchild!=NULL && p->rchild!=r){//p有右孩子且未访问
				p = p->rchild;
				push(S,p);//右孩子入栈
				p = p->lchild;
			}
			else{//p没有右孩子或右孩子已被访问（这条不太可能因为后序一定先访问他的右孩子）
				pop(S,p);
				visit(p);
				r = p;
				p = NULL;
			}
		}//else(!p) end
	}//while end
	return ;
}

9.14 day33 层序遍历

• 根结点入队；
• 若队列非空，则队头出队访问；
• 若其有左孩子，则左孩子入队；
• 若其有右孩子，则右孩子入队；

void levelOrder(BiTree T){
	InitQueue(Q);
	BiTree p;
	inQueue(Q,T);//根结点入队
	while(!isEmpty(Q)){
		outQueue(Q,p);
		visit(p);
		if(p->lchild)
			inQueue(p->lchild);
		if(p->rchild)
			inQueue(p->rchild);
	}//while end
	return ;
}

9.18 day34 二叉树从下往上，从右到左的层次遍历算法