每日一题(四) 8.3

每日一题（四） 8.3

二叉树的中序遍历

给定一个二叉树，返回他的中序遍历

示例：

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

代码：

一.递归实现 
    void InOrder(BiTree bt){
    if(bt==NULL) return; 
    InOrder(bt->lchild); 
    visit(bt->data); 
    InOrder(bt->rchild); 
} 
二.中序遍历非递归实现(利用栈来辅助储存，先出栈，在访问) 
void NRInOrder(BiTree bt){ 
	BiTree Stack[maxsize];//初始化辅助栈 
    int top = -1;//栈的下标 
    BiTree p = bt;//用p遍历二叉树 
    while(p!=NULL||p!=-1){ //p不为空或栈不为空 
       if(p!=NULL){//左孩子不为空 
           Stack[++top] = p;//入栈 
           p = p -> lchild;//往左走 
        }else{ 
            p = tack[top--];//出栈 
            visit(p);//访问节点 
            P->rchild;//往右走 
        } 
    } 
}