山西大学数据结构课程复习代码（本人自用）
本代码多为伪代码，未提供完整的可运行代码

一、二叉树的深度遍历

二叉树DFS的递归实现

template<class T>
void BinaryTree<T>::DepthOrder(BinaryTreeNode<T>* root)
{
    if(root!=NULL)
    {
        Visit(root->value());//前序遍历
        DepthOrder(root->leftchild());
        Visti(root->value());//中序遍历
        Depthorder(root->rightchild());
        Visit(root->value);//后序遍历
    }
}

非递归中序遍历二叉树

1.遇到一个结点，并将其压栈，遍历其左子树

2.遍历完左子树后，从栈顶弹出该节点并访问之

3.如何按其右链指示的地址再去遍历其右子树

入栈序列为先序遍历序列，出栈序列为中序遍历序列

template<class T>
void BinaryTree::InOrder(BInaryTreeNode<T> *root)
{
    using std::stack;
    stack<BinaryTreeNode<T>*> aStack;
    BinaryTreeNode<T> *pointer=root;
    while(pointer||!aSTack.empty())//当指针不空或者栈不空时
    {
        if(pointer)
        {
            aSTack.push(pointer);
            pointer=pointer->left;//前序方式遍历左子树
        }
        else
        {
            pointer=aStack.top();
            aStack.pop();
            Visit(pointer->value);
            a.Stack.push(pointer->right);
        }
    }
}

非递归前序遍历二叉树

1.遇到一个结点，访问之，并将其压栈

2.前序方式遍历左子树

3.按前序方式遍历完左子树后，从栈顶弹出一个结点，并按其右子地址再去前序遍历右子树

优化版：

1.遇到一个结点，访问之，并将其右子结点压栈

2.前序方式遍历左子树

3.按前序方式遍历完左子树后，从栈顶弹出一个结点，访问之，并按前序方式继续遍历其子树

template<class T>
void BinaryTree::InOrder(BInaryTreeNode<T> *root)
{
    using std::stack;
    stack<BinaryTreeNode<T>*> aStack;
    BinaryTreeNode<T> *pointer=root;
    aStack.push(NULL);//栈底监视哨（与pointer||!aStack.empty等价）
    while(pointer)//当指针不空或者栈不空时
    {
        Visit(pointer->value);//访问当前结点
        if(pointer->right) 
            aStack.push(pointer->right);//如果右子节点不空，则右子结点入栈
        if(pointer->left)//沿左路下降
            pointer=pointer->left;
        else//如果左路下降到底了，则访问栈顶
        {
            pointer=aStack.top();
            aStack.pop();
        }
    }
}