-1.数据结构

typedef struct BNode{
	int data;
	struct BNode *lchild,*rchild;
}BNode,*BiTree;

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

0.操作型和计算型

• 操作型：利用函数参数传递，返回值是void，第一步写递归出口；
• 计算型：利用函数返回值，返回值是int；

1.顺序存储二叉树，求结点i和结点j的最近公共祖先结点（编号从1开始）

• 先找到其直系祖先i0和j0
• 之后大的那一个向上找祖先即可，直到i0 == j0

int func(int A[],int i,int j){
	int i0 = i / 2;
	int j0 = j / 2;
	while(i0!=1 && j0!=1){
		if(i0 == j0)
			return i0;
		else if(i0 < j0)
			j0 = j0 / 2;
		else 
			i0 = i0 / 2;
	}
	return 1;
}

2.中序非递归

• 入栈一直向左走，出栈指向右子树

void InOrder(BiTree T){
	InitStack(S);
	BiTree p = T;
	while(p!=NULL || !IsEmpty(S){
		if(p){//当前结点不空
			push(S,p);
			p = p->lchild;//当前结点入栈，p指向其左孩子
		}
		else{//当前结点为空，则栈顶出栈，p指向出栈元素的右孩子
			pop(S,p);
			visit(p);
			p = p->rchild;
		}
	}
	return ;
}

3.先序非递归

void PreOrder(BiTree T){
	BiTree p = T;
	InitStack(S);
	while(p!=NULL || IsEmpty(S)){
		if(p){
			visit(p);
			push(S,p);//访问完结点也要将结点入栈，方便后续找其右孩子
			p = p->lchild;
		}
		else{
			pop(S,p);
			p = p->rchild;
		}
	}
	return ;
}

4.后序非递归

• 左子树为空时（p=NULL），检查右子树
  • 若右子树存在且未被访问过，则当前结点指向右子树继续遍历；
  • else：右子树不存在或已被访问过，则访问当前结点，置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){
	BiTree p = T;
	BiTree r = NULL;//r指向最近访问的结点
	InitStack(S);
	while(p!=NULL || 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{
				pop(S,p);
				visit(p);
				r = p;
				p = NULL;//p重置为null进入下一次循环
			}
		}
	}
	return ;
}

5.层序遍历

1. 根节点入队；