算法笔记-树

树经常涉及遍历的算法和性质，很多题目都是遍历的变体，或者说需要借用遍历的逻辑去解题，所以首先应该掌握的是几种遍历的方法（递归和非递归），然后就是需要对一些树相关的概念了解，比如说平衡二叉树（子树的高度绝对值相差不超过1），树的子结构（然后就是要会借用一些额外的数据结构进行解题，常用的是栈。有些题目也会涉及到递归和回溯。

一.遍历

最重要的还是遍历。先看一下基础的遍历算法。递归的就不说了，说一说非递归的吧。

# 引用：https://blog.csdn.net/z_ryan/article/details/80854233
//中序遍历
void InOrderWithoutRecursion1(BTNode* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p)
        {
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
            p = p->rchild;
        }
    }
}

就是要让代码跟着自己的逻辑走，然后精简代码。非递归版本的遍历需要额外使用一个栈，用来存储根节点，来进入到右边的节点。

# 引用：https://blog.csdn.net/z_ryan/article/details/80854233
void PreOrderWithoutRecursion1(BTNode* root)
{
    if (root == NULL)
        return;
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        //边遍历边打印，并存入栈中，以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
        while (p)
        {
            cout << setw(4) << p->data;
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明根和左子树都遍历完了，该进入右子树了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    cout << endl;
}

循环主体和中序遍历是一样的，只不过打印的操作放在了前面一个寻找最左边的节点的循环前面了。