遍历顺序：

规定从左到右

前序：
中序
后序
树的结构
定义如下：SS

struct BiTree{
    int data;
    struct BiTree *left,*right;
};
typedef BiTree BTNode;
typedef BiTree *BT;

递归算法

前序递归遍历

思路

若根节点为空，直接返回空，不为空则输出根节点后递归遍历根的左子结点，再递归遍历根的右子节点。

代码实现

void preOrderTravase(BT root)
{
    if(!root)   return;
    else{
        printf("%d",root->data);
        preOrderTravase(root->left);
        preOrderTravase(root->right);
    }
}

中序递归遍历

void inOrderTravase(BT root)
{
    if(!root)   return;
    else
    {
        inOrderTravase(root->left);
        printf("%d",root->data);
        inOrderTravase(root->right);
    }
}

后序递归遍历

void postOrderTravase(BT root)
{
    if(!root) return;
    else
    {
        postOrderTravase(root->left);
        postOrderTravase(root->right);
        printf("%d",BT->data);
    }
}

非递归遍历

前序

思路

栈实现：根结点非空则先入栈，循环结构中，当栈非空时栈顶出栈，且将出栈结点的右结点和左节点（如果存在）分别入栈

实现

void preOrderTravase(BT root)
{
    BT stack[MaxLeng],temp;
    int top=0;
    if(!root)   return;
    stack[top++]=root;
    while(top)
    {
        temp=stack[--top];
        printf("%d ",temp->data);
        if(temp->right)
            stack[top++]=temp->right;
        if(temp->left)
            stack[top++]=temp->left;
    }
}

中序

思路

栈实现：根结点非空则先入栈，循环体中，先将左子结点依次入栈至其无左节点;若栈非空，弹出栈顶结点并访问该结点，接着将其右子树作为根遍历

实现

void inOrderTravase(BT root)
{
    BT stack[MaxLeng];
    int top=0;
    if(root)
    {
        temp=root;
        do
        {
            while(temp)
            {
                stack[top++]=temp;
                temp=temp->left;
            }//终止循环时，temp=NULL，栈顶的下一个才指向栈顶结点;
            if(top)//栈非空
            {
                temp=stack[--top];
                printf("%d ",temp->data);
                temp=temp->right;
            }//if
        }while(top||temp)//do
    }
}

后序

思路

将根结点入栈，循环体中：将左子树依次入栈至无左子树,出栈，若有右兄弟结点同样出栈

二叉树高度

递归实现

返回1+左右子树中最高的高度

ZEROCATH

二叉树：遍历