二叉树的遍历

刷题的时候遇到关于二叉树的基础题目，发现很多基础知识都遗忘了，赶紧又看了一遍巩固一下。用博客记录一下，以后多看看。

二叉树的定义

二叉树是一种常见的数据结构，其中每个节点，除了根节点以外，都有唯一一个父节点，每个节点都至多有两个孩子节点。

二叉树常用链式存储，在C语言中用结构体定义二叉树节点：

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    TreeLinkNode(int x) :val(x)， left(NULL)， right(NULL) {
        
    }
};

定义的最后一行代码类似C++中构造函数的初始化列表的用法。可以看到每个二叉树节点都包含一个数据域和两个指向自己类型的指针域，存储了左右孩子节点的地址。

二叉树的构造

首先声明一点，任意序列构造二叉树是无法实现的，必须有一定约束。因为二叉树有两个分支，无法确定将新节点插在那个分支上。对于二叉搜索树和平衡二叉树都是特殊约束的二叉树，即插入元素的位置是确定的。

这里使用层序插入的方法构造二叉树，所谓层序插入，即从一组序列（向量）读取元素，按元素顺序依此插入的二叉树的每一层中，理论上构造出来的是一颗完全二叉树。

难点分析

考虑层序插入的场景，是不断取元素，不断填充每一层的叶子节点的过程，因此在第n+1层插入节点时，只从第n层的一个父节点插入，这个父节点插满了，需要找第n层的其他父节点。

因此：由于要把节点插入到每一层，因此需要保存之前插入到树中节点的指针，并且一个节点的左右孩子没有插满时，都要持有对该节点的访问权限，又是顺序读取元素，顺序插入，因此考虑队列的方法保存节点指针。

算法思路

1. 插入一个节点，就把这个节点放入队列尾部（push_back）
2. 每次插入节点时，从队列首部取一个元素（front），该元素是树中应该插入且未插满的元素，如果左孩子空，插左边，右孩子空，插右边
3. 插完右边之后，这个节点就插满了，从队列头部弹出（pop_front）

代码实现

/**
 * @brief 层序遍历构建二叉树
 * 
 * @param array 
 * @return TreeLinkNode* 
 */
TreeLinkNode* levelOrderConstructTree(vector<int> array)
{
    if(array.size()==0) return NULL;
    deque<TreeLinkNode *> q;
    //保存根节点
    TreeLinkNode * root = (TreeLinkNode *)malloc(sizeof(TreeLinkNode));
    root->left=NULL;
    root->right=NULL;
    root->val=array[0];
    q.push_back(root);

    for(int i = 1;i<array.size();i++)
    {
        //构建叶节点
        TreeLinkNode * node = (TreeLinkNode *)malloc(sizeof(TreeLinkNode));
        node->left=NULL;
        node->right=NULL;
        node->val=array[i];

        q.push_back(node);
        
        TreeLinkNode* father = q.front();

        if(father->left==NULL)
        {
            father->left=node;
        }
        else
        {
            father->right=node;
            q.pop_front();
        }
    }
    return root;
}

二叉树的遍历

接下来的内容才是标题相关的内容。但是二叉树要遍历前提是有一颗二叉树。总的来说，二叉树的遍历有两种方式，一种是层序遍历，按每一层的叶节点访问。另一种是先序、中序、后序，按一定顺序访问这个链式存储结构。

先序遍历

首先介绍先序遍历，先序遍历是在遍历一颗树时，先访问根节点，再遍历左子树，左子树遍历完，遍历右子树，遍历每颗子树时也按照根节点，左子树，右子树的顺序进行访问。

递归实现

从先序遍历的定义可以看出，用递归进行实现非常容易，代码

/**
 * @brief 二叉树的先序遍历
 * 
 * @param root 
 */
void preOrderTraversal(TreeNode *root)
{
    if(root==NULL) return ;
    else
    {
        cout<<root->val<<" ";
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

访问节点用打印实现

非递归实现

递归程序本质上使用递归栈实现的，因此手动构建栈也可以实现先序遍历。考虑先序遍历的过程，遇到一个节点，直接访问，然后向左子树延伸，直到左子树到头，这时候回到上一个节点，遍历右子树，因此需要一个栈保存节点的右孩子指针。先遇到的后访问，栈顶优先弹出的是最近的未访问过的右子树。

• 程序思路如下：

1. 遇到一个节点，不空就访问，并且把节点右指针压栈（push）
2. 根节点向左子树延伸，直到节点的左孩子为空
3. 从栈中弹出顶部元素（pop）作为访问节点

• 代码实现：

void preOrderTraversal2(TreeNode *root)
{
    if(root ==NULL) return;
    else
    {
        stack<TreeNode*> s;
        
        while(root || !s.empty())
        {
            while(root)
            {
                cout<<root->val<<" ";
                s.push(root->right);
                root = root->left;          
            }
            
            //左边到头
            if(!s.empty())
            {
                //根节点切到右子树
                root = s.top();
                s.pop()
            }
        }    
    }    
}

中序遍历

与先序遍历类似，中序访问时，先访问左子树，再访问根节点，再访问右子树。访问每棵子树时也按照左子树、根节点、右子树的顺序进行。

递归实现

直接给出代码

void InOrderTraversal(TreeNode* root)
{
    
    if(root==NULL) return ;
    else
    {
        InOrderTraversal(root->left);
        cout<<root->val<<" ";
        InOrderTraversal(root->right);
    }
}

非递归实现

• 思路：

1. 遇到一个节点，先不访问，因为先要访问该节点的左子树，所以先把这个节点压栈（push），等会在访问
2. 根节点向左子树延伸，直到左边空，沿路的左子树都被压入堆栈
3. 从堆栈弹出栈顶元素（pop）是最近遇到的节点，访问之，然后根节点切换到该节点的右指针，访问右子树

• 代码

void InOrderTraversal(TreeNode* root)
{
    if(root==NULL) return;
    else
    {
        stack<TreeNode*> s;
        while(root || !s.empty())
        {
            while(root)
            {
                s.push(root);
                root = root->left;    
            }
            //左边到头
            if(!s.empty())
            {
                root = s.top();
                s.pop();                
                cout<<root->val<<" ";                
                root = root->right;
            }            
        }    
    }    
}

后序遍历

后序遍历子树的访问顺序为，先递归访问左子树，再递归访问右子树，最后访问根节点

递归实现

void PostOrderTraversal(TreeNode* root)
{
    if(root == NULL) return ;
    else
    {
        PostOrderTraversal(root->left);
        PostOrderTraversal(root->right);
        cout<<root->val<<" ";
    }    
}

非递归实现