二叉树的各种操作

前言

二叉树的各种操作，前中后序的递归与非递归实现，二叉树的构建（序列化和反序列化），二叉树的最大高度与最小高度，打印出从根节点到叶子的节点的所有路径，打印出根节点到特定节点的路径，反转二叉树，判断两个二叉树是否相等等等操作。

算法这东西，就得多练，几天不写，还是感觉手生，需要定期不断温习，温故而知新啊，好好努力。

二叉树的各种操作

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

struct TreeNode{
    char val;   //节点值
    TreeNode *left;  //左节点
    TreeNode *right;  //右节点
    TreeNode(char v='0'):val(v),left(nullptr),right(nullptr){}
};

/*           A
            / \
           B   C
          / \  /
         D   E F
        /
       G
*/

//前序序列化二叉树  ABDG$$$E$$CF$$$
TreeNode* CreateTree(vector<char>::iterator &iter){
    if(*iter=='$') return nullptr;
    TreeNode *root = new TreeNode(*iter);
    root->left = CreateTree(++iter);
    root->right = CreateTree(++iter);
    return root;
}
//获取前序序列串
void getSequence(TreeNode *root,vector<char> &sequence){
    if(!root) {
        sequence.push_back('$');
        return;
    }
    sequence.push_back(root->val);
    getSequence(root->left,sequence);
    getSequence(root->right,sequence);
}

void Print(vector<char> &sequence){
    for(auto ele:sequence){
        cout<<ele<<" ";
    }
    cout<<endl;
}

//递归先序遍历
void PreTravel(TreeNode *root){
    if(!root) return;
    cout<<root->val<<" ";
    PreTravel(root->left);
    PreTravel(root->right);
}

//非递归先序遍历
void NonCurPreTravel(TreeNode *root){
    stack<TreeNode*> s;
    if(!root) return;
    TreeNode *iter = root;
    while(!s.empty()||iter){
        if(iter){  //如果左节点不为空的话，遍历左子树
            cout<<iter->val<<" ";
            s.push(iter);
            iter = iter->left;  //左结点依次入栈
        }else{ //左节点为空，遍历右子树
            iter = s.top();
            s.pop();
            iter = iter->right;  //出栈，遍历右子树
        }
    }
    cout<<endl;
}

//递归中序遍历
void InTravel(TreeNode *root){
    if(!root) return;
    InTravel(root->left);
    cout<<root->val<<" ";
    InTravel(root->right);
}

//非递归中序遍历
void NonCurInTravel(TreeNode *root){
    stack<TreeNode*> s;
    if(!root) return;
    TreeNode *iter = root;
    while(!s.empty()||iter){
        if(iter){  //如果左节点不为空的话，遍历左子树
            s.push(iter);
            iter = iter->left;  //左结点依次入栈
        }else{ //左节点为空，遍历右子树
            iter = s.top();
            cout<<iter->val<<" ";
            s.pop();
            iter = iter->right;  //出栈，遍历右子树
        }
    }
    cout<<endl;
}

//递归后序遍历
void PostTravel(TreeNode *root){
    if(!root) return;
    PostTravel(root->left);
    PostTravel(root->right);
    cout<<root->val<<" ";
}

//非递归后序遍历
void NonCurPostTravel(TreeNode *root){
    if(!root) return ;
    stack<TreeNode*> s;
    TreeNode *prenode = nullptr;
    TreeNode *curnode = root;
    while(curnode){
        s.push(curnode);
        curnode = curnode->left;  //cur先走到左子树最左边结点
    }
    while(!s.empty()){
        curnode = s.top();
        s.pop();
        if(curnode->right==nullptr||curnode->right==prenode){ //右子树为空，或者右子树已经访问过了，此时访问根结点
            cout<<curnode->val<<" ";
            prenode = curnode;
        }else{
            //根节点继续入栈，因为此时根节点右子树没有访问，我们需要访问完右子树，还需要继续访问根节点，所以根节点要再此入栈
            s.push(curnode);
            //访问右子树
            curnode = curnode->right;
            while(curnode){
                s.push(curnode);
                curnode = curnode->left;
            }
        }
    }
    cout<<endl;
}

//层次遍历
void LevelTravel(TreeNode *root){
    if(!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){  //队列非空
        TreeNode *node = q.front();   //获得队首
        q.pop();   //移除队列中的第一个元素
        cout<<node->val<<" ";
        if(node->left) q.push(node->left);
        if(node->right) q.push(node->right);
    }
    cout<<endl;
}

//获取树的高度(最大高度)
int GetTreeMaxHigh(TreeNode *root){
    if(!root) return 0;   //根节点为空
    int leftHigh = GetTreeMaxHigh(root->left);
    int rightHigh = GetTreeMaxHigh(root->right);
    return leftHigh>rightHigh?leftHigh+1:rightHigh+1;
}

//获取树的最小高度,递归实现
int GetTreeMinHigh(TreeNode *root){
    if(!root) return 0;
    if(!root->left){  //左子树为空，返回右子树的高度
        return GetTreeMinHigh(root->right)+1;
    }
    if(!root->right){  //右子树为空，返回左子树的高度
        return GetTreeMinHigh(root->left)+1;
    }
    //左右子树不空，返回左右子树高度的较小值
    int leftHigh = GetTreeMinHigh(root->left);
    int rightHigh = GetTreeMinHigh(root->right);
    return leftHigh>rightHigh?rightHigh+1:leftHigh+1;
}

//获取树的最小高度，层次遍历实现，也就是找到第一个叶子节点，得到该叶子节点所在的层即可
int GetTreeMinHighWithLevelTravel(TreeNode *root){
    if(!root) return 0;
    queue<TreeNode*> q;
    int level = 0;
    q.push(root);
    while(!q.empty()){
        int length = q.size();
        ++level;
        while(length--){
            TreeNode *node = q.front();
            q.pop();
            if(node->left==nullptr&&node->right==nullptr) return level;  //找到第一个叶子节点，返回
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
    }
    return level;
}

//获取从根节点到所有叶子节点的路径，递归前序遍历思想
void GetAllPath(TreeNode *root,vector<vector<char>> &allpath,vector<char> &path){
    if(!root) return;
    path.push_back(root->val);
    if(root->left==nullptr&&root->right==nullptr){  //叶子节点，将path存入到allpath中
        allpath.push_back(path);
    }
    GetAllPath(root->left,allpath,path);
    GetAllPath(root->right,allpath,path);
    path.pop_back();  //在返回到父节点之前，在路径上删除当前节点
}

//获取根节点到某一固定节点的路径，递归前序遍历的思想
void GetPathFromRootTOnode(TreeNode *root,vector<vector<char>> &allpath,vector<char> &path,char &ch){  //allpath,可能有多个相同的节点
    if(!root) return ;
    path.push_back(root->val);
    if(root->val == ch){   //找到该节点，保存路径
        allpath.push_back(path);
    }
    GetPathFromRootTOnode(root->left,allpath,path,ch);
    GetPathFromRootTOnode(root->right,allpath,path,ch);
    path.pop_back();  //在返回到父节点之前，在路径上删除当前结点
}

void Print(vector<vector<char>> &allpath){
    for(auto path : allpath){
        for(auto ele : path){
            cout<<ele<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

//判断两棵树是否相同
bool IsSameTree(TreeNode *root1,TreeNode *root2){
    if(!root1 && !root2) return true;
    if(!root1 || !root2) return false;
    //两个节点都不为空
    if(root1->val == root2->val){
        return IsSameTree(root1->left,root2->left) && IsSameTree(root1->right,root2->right);
    }
    //不相等
    return false;
}

//反转二叉树，层次遍历实现
TreeNode* invertTree1(TreeNode* root) {   //层次遍历，遍历每一层时，同时翻转该层的左右子树
    if(!root) return root;   //如果根节点为空，返回根节点
    queue<TreeNode*> q;
    q.push(root);     //根节点入队列
    while(!q.empty()){  //队列不为空
        TreeNode *node = q.front();   //遍历每层时，交换节点的左右节点
        q.pop();     //出队
        swap(node->left,node->right);  //交换左右节点
        if(node->left) q.push(node->left);   //左右结点不为空入队
        if(node->right) q.push(node->right);
    }
    return root;
}

//反转二叉树，递归实现
TreeNode* invertTree2(TreeNode *root){
    if(root){
        invertTree2(root->left);
        invertTree2(root->right);
        swap(root->left,root->right);
    }
    return root;
}

int main()
{
    //构建一个二叉树
    vector<char> sequence = {'A','B','D','G','$','$','$','E','$','$','C','F','$','$','$'};
    auto iter = sequence.begin();
    TreeNode *root = CreateTree(iter);
    cout<<"获取前序序列串"<<endl;
    vector<char> s;
    getSequence(root,s);
    Print(s);
    cout<<"先序递归与非递归"<<endl;
    PreTravel(root);
    cout<<endl;
    NonCurPreTravel(root);
    cout<<"中序递归与非递归"<<endl;
    InTravel(root);
    cout<<endl;
    NonCurInTravel(root);
    cout<<"后序递归与非递归"<<endl;
    PostTravel(root);
    cout<<endl;
    NonCurPostTravel(root);
    cout<<"层次遍历"<<endl;
    LevelTravel(root);
    cout<<"树的高度(最大高度)"<<endl;
    int maxhigh = GetTreeMaxHigh(root);
    cout<<maxhigh<<endl;
    cout<<"树的最小高度(根节点到叶子节点的最小距离)"<<endl;
    cout<<GetTreeMinHigh(root)<<endl;
    cout<<GetTreeMinHighWithLevelTravel(root)<<endl;
    cout<<"输出根节点到叶子节点的所有路径"<<endl;
    vector<vector<char>> allpath;
    vector<char> path;
    GetAllPath(root,allpath,path);
    Print(allpath);
    cout<<"输出根节点到某一特定节点的路径"<<endl;
    vector<vector<char>> allivec;
    vector<char> ivec;
    char ch = 'E';
    GetPathFromRootTOnode(root,allivec,ivec,ch);
    Print(allivec);
    cout<<"判断两棵树是否相同"<<endl;
    if(IsSameTree(root,root)) cout<<"is the same"<<endl;
    else cout<<"is not the same"<<endl;
    cout<<"反转二叉树"<<endl;
    root = invertTree2(root);
    LevelTravel(root);
    return 0;
}

/*           A
            / \
           B   C
          / \  /
         D   E F
        /
       G
*/

输出结果：