二叉树遍历与构造
二叉树的遍历
二叉树遍历其实很简单，三种遍历都是一样的，只不过顺序先后不一样罢了。
先序遍历
访问根结点，先序遍历左子树，先序遍历右子树
void PreOrder(BitTree T){
if( T != nullptr){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}中序遍历
中序遍历左子树，访问根结点，中序遍历右子树
void InOrder(BitTree T){
if(T != nullptr){
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}后序遍历
后序遍历左子树，后序遍历右子树，访问根结点
void PostOrder(BitTree T){
if( T != nullptr ){
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}时间复杂度都为O（n），在递归遍历中，递归工作栈的栈深恰好为树的深度，在最坏情况下，二叉树是有n个结点且深度为 n 的单支树，遍历算法的空间复杂度为O（n）。
利用非递归方式遍历二叉树
借助栈，可以将二叉树的递归遍历转换为非递归算法。以中序遍历为例，给出中序遍历非递归算法。先扫描（并非访问）根结点的所有左结点并将它们一一进栈，然后出栈一个结点*p，访问它。然后继续扫描该结点的右孩子结点，将其进栈，在扫描该孩子结点的所有左结点并一一进栈，如此继续，直到栈空。
中序遍历的非递归算法如下：
void InOrderWithoutRecursion(BitTree T){
Stack<BitTree> S; //辅助栈
BitTree p = T; //遍历指针
while( p || !IsEmpty(S) ){ //栈不为空或p不为空时
if( p ){
S.push(p); //根指针进栈
p = p->lchild; //遍历左子树
}else{
S.pop(p); //根指针退栈
visit(p); //cout << p->data;
p = p->rchild; //向右子树走
}
}
}前序遍历的非递归算法：
void PreOrderWithoutRecursion(BitTree T)
{
if (T == nullptr)
return;
BTNode* p = T;
stack<BitNode*> s;
while (!s.empty() || p)
{
if (p)
{
visit(p); // cout << p->data;
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
s.pop();
p = p->rchild;
}
}
cout << endl;
}后序遍历的非递归算法：后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。直接看代码，代码中有详细的注释。
void PostOrderWithoutRecursion(BTNode* root)
{
if (root == NULL)
return;
stack<BTNode*> s;
//pCur:当前访问节点，pLastVisit:上次访问节点
BTNode* pCur, *pLastVisit;
//pCur = root;
pCur = root;
pLastVisit = NULL;
//先把pCur移动到左子树最下边
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
while (!s.empty())
{
//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
pCur = s.top();
s.pop();
//一个根节点被访问的前提是：无右子树或右子树已被访问过
if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
{
cout << setw(4) << pCur->data;
//修改最近被访问的节点
pLastVisit = pCur;
}
/*这里的else语句可换成带条件的else if:
else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
*/
else
{
//根节点再次入栈
s.push(pCur);
//进入右子树，且可肯定右子树一定不为空
pCur = pCur->rchild;
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
}
}
cout << endl;
}层次遍历
层次遍历需要借助队列。先将二叉树根结点入队，然后初岁，访问该结点，若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空。
void LevelOrder(BitTree T){
if( T == nullptr){
return ;
}
Queue<BitNode*> q; //辅助队列
q.push(T); //将根结点入队
while(!q.empty()){ //队列不为空时
int sz = q.size();
for(int i = 0; i < sz; i++){
BitNode* cur = Q.front();
q.pop(); //队头元素出队
if(p->lchild != nullptr){
q.push(p->lchild); //左子树不为空时，左子树入队
}
if(p->rchild != nullptr){
q.push(p->rchild); //右子树不为空时，右子树入队
}
}
}
}由遍历序列构造二叉树
由二叉树的先序和中序序列可以唯一确定一棵二叉树，同样后序和中序序列也可以唯一确定一棵二叉树，但先序和后序不能确定一棵二叉树。
先序和中序序列构造一棵二叉树
思路：我们知道先序序列的第一个值其实就是根节点的值，这样我们就可以在中序序列中找到对应的根节点，那么根节点左边的数就全为左子树的结点，根节点右边的数就全为右子树的结点。根据这个想法，再递归的进行构造，见代码。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
unordered_map<int, int> index; //借助哈希表，让我们快速的找到分割点，不用每次都去循环一遍
public:
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};后序和中序序列构造一棵二叉树
思路：我们知道后序序列的最后一个值其实就是根节点的值，这样我们就可以在中序序列中找到对应的根节点，那么根节点左边的数就全为左子树的结点，根节点右边的数就全为右子树的结点。根据这个想法，再递归的进行构造，见代码。
class Solution {
private:
unordered_map<int,int> index; //借助哈希表，让我们快速的找到分割点，不用每次都去循环一遍
public:
TreeNode* myBuildTree(vector<int>& postorder,vector<int>& inorder,int postorder_left,int postorder_right,int inorder_left,int inorder_right){
if(postorder_left > postorder_right){
return nullptr;
}
//后序遍历的最后一个节点其实就是根节点
int postorder_root = postorder_right;
//在中序遍历中定位根节点
int inorder_root = index[postorder[postorder_root]];
//先建立根节点
TreeNode* root=new TreeNode(postorder[postorder_root]);
//得到左子树节点数量
int size_left_subtree=inorder_root-inorder_left;
//注意区间边界范围 +1，-1 一定要注意判别好
//递归构造左右子树
root->left=myBuildTree(postorder,inorder,postorder_left,postorder_left+size_left_subtree-1,inorder_left,inorder_root-1);
root->right=myBuildTree(postorder,inorder,postorder_left+size_left_subtree,postorder_root-1,inorder_root+1,inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){
int n=postorder.size();
//借助哈希表，让我们快速的找到分割点，不用每次都去循环一遍
for(int i=0;i<n;i++){
index[inorder[i]]=i;
}
return myBuildTree(postorder,inorder,0,n-1,0,n-1);
}
};Last updated
