关于树的总结

一、树的基础了解
(1)开始的开始，肯定是先要了解树是什么。首先，树，显然是有根节点，叶子节点的，对每个节点而言他们都可能存在孩子节点，即在下面连着他们的节点。我们将一个节点下面连有的节点数称之为度。所谓根节点，就是最原始开端的顶点，所谓叶节点就是最后没有再连接下一层节点的最后节点，所以叶节点的度是0。我们知道一般树通过横向连接节点，并去掉原右连接，可以得到一颗简单的二叉树。因此，我们多数问题都是围绕二叉树展开的。
(2)那么，二叉树有哪几种呢？ 二叉树从结构上分为，完全二叉树和满二叉树，从功能上分为搜索二叉树，平衡二叉树。完全二叉树包含满二叉树，完全二叉树，是指最后一层不一定全满但一定是节点左倾的二叉树。搜索二叉树是指左树<根节点<右树，且左右树符合这个特点的二叉树,搜索二叉序的中序遍历是一个升序的序列。平衡二叉树是指，左右树的高度差<=1的二叉(搜索)树，其诞生是为了让二叉搜索树不“偏大头”。
(3)接着，我们需要知道我们对树要进行什么操作。其实，不管对什么数据结构，无非四个操作增删查改，那我们的树也不例外。树对应的操作包括，建树、遍历树、验证树、修改树。每一个操作都很麻烦。因此，有必要好好总结下。
二、树的定义
直接看代码吧。

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int n):val(n),left(nullptr),right(nullptr){}
}

三、建树---递归
因为我们的二叉树分成四种，因此，建树也需要分开讨论。
(1) 建一棵普通二叉树
首先要明确建立一棵树的话，如果未声明是特殊树的话，除非是直接给定层序遍历序列，否则单靠一个遍历序列是不足以建树的。一般需要前序遍历序列或者后序遍历序列才能建立一个二叉树。那么如何通过两种遍历序列得到建树呢。得明白三种遍历序列的特点。第一，前序遍历从左往后的第一个节点就是根节点，并且之后的节点排布是先左树节点后右树节点；第二，中序遍历是先左节点再根节点最后右节点，因此，找到根节点，其左边就是左树节点，其右边就是右树节点；第三，后序遍历，最后面一定是根节点，而且之前的节点排布是先左节点后右节点。下面写上有前序+中序建树，以及由后序+中序建树的代码实现：

/*前序+中序建树*/
TreeNode * buildBT(vector<int>&preorder,int pre_left,int pre_right,vector<int>&inorder,int in_left,int in_right){
    //base case 
    if(in_left>in_right)    return nullptr;
    //operations
    TreeNode *head=new TreeNode(preorder[pre_left]);
    for(int i=0;i<inorder.size();++i){
        if(inorder[i]==head->val){
            head->left=buildBt(preorder,pre_left+1,pre_left+i-in_left,inorder,in_left,i-1);
            head->right=buildBT(preorder,pre_left+i-in_left+1,pre_left-in_left+in_right,inorder,i+1,in_right);
            break;
        }
    }
    return head;
}
/*后序+中序建树*/
TreeNode * buildBT(vector<int>&postorder,int post_left,int post_right,vector<int>&inorder,int in_left,int in_right){
    //base case 
    if(in_left>in_right)    return nullptr;
    //operations
    TreeNode *head=new TreeNode(postorder[post_right]);
    for(int i=0;i<inorder.size();++i){
        if(inorder[i]==head->val){
            head->right=buildBT(postorder, post_right-in_right+i,post_right-1,inorder,i+1,in_right);
            head->left=buildBT(postorder,post_right-in_right+in_left,post_right-in_right+i-1,inorder,in_left,i-1);
            break;
        }
    }
    return head;     
}
/*层序递归建树---难一点*/
//注意几个点：第一，需要传入根节点；
//第二，需要判断子节点序号是否小于数组长度；
//第三，一开始，当index为1时，要根根节点赋值。
TreeNode *buildBT(TreeNode *root,vector<int>&levelorder,int index){
    if(index==0)    root=new TreeNode(levelorder[index]);
    int left=2*index+1;right=2*index+2;
    if(left>levelorder.size()-1)    return root;
    if(left<levelorder.size()){
        root->left=new TreeNode(levelorder[left]);
        buildBT(root->left,levelorder,left);
    }
    if(right<levelorder.size()){
        root->right=new TreeNode(levelorder[right]);
        buildBT(root->right,levelorder,right);
    }
    return root;
}

（2）建一棵搜索二叉树
注意几个点：第一，要先确定根节点，然后放入根节点；第二，确定新元素插入的位置，如果小于根节点就在左树上，如果左节点已经存在，就递归把左节点当根节点找位置插入该元素；反之，在右树上，同理，左节点已存在则递归。

/*建树函数*/
TreeNode* buildBST(TreeNode* root, int val) {
    //base case
    if(!root)    root= new TreeNode(val);
    //operations
    if(val<root->val)    root->left=buildBST(root->left,val);
    if(val>root->right)    root->right=buildBST(root->right,val);
    return root;
}
/*主函数内实现建树*/
    TreeNode* root =nullprt;
    for (int i = 0; i < v.size(); ++i) {
        root=buildBST(root, v[i]); //更新树
    }

(3) 建一棵平衡树---难
<1>首先是要重新定义结构体，多一个数据：高度

struct balancedBT {
    int val;
    int height;
    balancedBT* left;
    balancedBT* right;
    balancedBT() :val(0), height(0), left(nullptr), right(nullptr) {}
    balancedBT(int n) :val(n), height(1), left(nullptr), right(nullptr) {}
};

<2>接着是要获取树的高度：

int height(balancedBT* root) {
    //base case
    //if (!root)   return 0;
    ////operations
    //return max(height(root->left), height(root->right)) + 1;
    //非递归
    if (!root)   return 0;
    queue<balancedBT*>q; q.push(root);
    int res = 0;
    while (!q.empty()) {
        //queue<TreeNode*>tmp;
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            balancedBT* cur = q.front();
            if (cur->left)   q.push(cur->left);
            if (cur->right)     q.push(cur->right);
            q.pop();
        }
        ++res;
    }
    return res;
}

<3>再是明确怎么调整搜索树：分为左树左节点，右树右节点，左树右节点和右树左节点，对应LL、RR、LR、RL
下面分别图示如何调整：
LL型：
图片说明 

//LL型调整
balancedBT* ll_rotate(balancedBT* root) {
    //右旋
    balancedBT* new_root = root->left;
    root->left = new_root->right;
    new_root->right = root;
    //更新高度
    new_root->height = max(height(new_root->left), height(new_root->right)) + 1;
    root->height = max(height(root->left), height(root->right)) + 1;
    //返回结果
    return new_root;
}

RR型：
图片说明 

//RR型调整
balancedBT* rr_rotate(balancedBT* root) {
    //左旋
    balancedBT* new_root = root->right;
    root->right = new_root->left;
    new_root->left = root;
    //更新高度
    new_root->height = max(height(new_root->left), height(new_root->right)) + 1;
    root->height = max(height(root->left), height(root->right)) + 1;
    //返回结果
    return new_root;
}

LR型：
图片说明 

//LR型调整
balancedBT* lr_rotate(balancedBT* root) {
    //先对左节点左旋再对根节点右旋，即先rr_rotate,再ll_rotate
    root->left = rr_rotate(root->left);
    return ll_rotate(root);
}

RL型：
图片说明 

//RL型调整
balancedBT* rl_rotate(balancedBT* root) {
    //先对右节点右旋，再对根节点左旋
    root->right = ll_rotate(root->right);
    return rr_rotate(root);
}

<4>然后，还获得平衡因子：

//获取平衡因子
int BF(balancedBT *root) {
    int left_height = root->left ? root->left->height : 0;
    int right_height = root->right ? root->right->height : 0;
    return (left_height-right_height);
}

于是，就可以调整了：

//调整平衡二叉树
balancedBT* balance(balancedBT* root,int val) {
    if (BF(root) > 1 && val < root->left->val)
        return ll_rotate(root);
   if (BF(root) < -1 && val > root->right->val)
        return rr_rotate(root);
    if (BF(root) > 1 && val > root->left->val)
        return lr_rotate(root);
   if (BF(root) < -1 && val < root->right->val)
        return rl_rotate(root);
    return root;
}

<5>最后就是结合二叉搜索树的建立方法，建立平衡二叉树：

//建树(插入)函数
balancedBT* buildBalancedBT(balancedBT *root,int val) {
    if (!root)   root= new balancedBT(val);
    if (val < root->val)   root->left = buildBalancedBT(root->left, val);
    if (val > root->val)  root->right = buildBalancedBT(root->right, val);
    //更新高度
    root->height = max(height(root->left), height(root->right)) + 1;
    return balance(root,val);
}
/*主函数内实现建树*/
    balancedBT* root3 = nullptr;
    for (int i = 0; i < v.size(); ++i) {
       root3=buildBalancedBT(root3, v[i]);//每次都修改根节点，所以必须给root3重新赋值
    }

四、遍历树---递归、栈、队列

  1. DFS式遍历
    (1)前序遍历：
    注意非递归实现的步骤：
    先遍历到左边底部，边遍历边打印和入栈
    再在栈内，不断pop掉节点，并检查节点是否有右节点，如有则继续遍历到左边底部，并入栈节点。

    void preorderSearch(TreeNode *root) {
 //1.递归实现
 //base case
 //if (!root)   return;
 ////operations
 //cout << root->val << "  ";
 //preorderSearch(root->left);
 //preorderSearch(root->right);

 //2.非递归实现，利用栈
 stack<TreeNode*>s; TreeNode* cur = root;
 //先搜索到左边最底并打印
 while (cur) {
     cout << cur->val << "  ";
     s.push(cur);
     cur = cur->left;
 }
 //然后遍历右边的节点
 while (!s.empty()) {
     cur = s.top(); s.pop();
     if (cur->right) {
         //继续搜索到左边底
         cur = cur->right;
         while (cur) {
             cout << cur->val << "  ";
             s.push(cur);
             cur = cur->left;
         }
     }
 }
}

    (2)中序遍历
    注意非递归遍历的步骤：
    先遍历到左边底部，并入栈，不打印
    再在栈内，不断pop掉节点并打印，然后检查是否有右节点，如有，则继续遍历到左边底部，入栈节点

    void inorderSearch(TreeNode* root) {
 //1. 递归实现
 //base case 
 //if (!root)   return;
 ////operations
 //inorderSearch(root->left);
 //cout << root->val << "  ";
 //inorderSearch(root->right);

 //2. 非递归实现
 stack<TreeNode*>s; TreeNode* cur = root;
 //先搜索到左边最底，但不打印
 while (cur) {
     s.push(cur);
     cur = cur->left;
 }
 //然后遍历右边的节点
 while (!s.empty()) {
     cur = s.top(); s.pop();
     cout << cur->val << "  ";
     //继续搜索到左边底
     if (cur->right) {
         cur = cur->right;
         while (cur) {
             s.push(cur);
             cur = cur->left;
         }
     }
 }
}

    (3) 后序遍历---难一点
    注意非递归遍历的步骤：
    类似层序遍历，先入栈根节点
    再在栈内，检查节点是否无左右节点或左右节点被遍历过了，如是，则打印该节点，并标记该节点为已遍历：pre=cur;
    否则，就依次入栈右节点，左节点。

    void postorderSearch(TreeNode *root) {
//1.递归实现
 //base case
 //if(!root)    return;
 ////operations
 //postorderSearch(root->left);
 //postorderSearch(root->right);
 //cout << root->val << "  ";

 //2. 非递归实现---这个会难很多，比较费解，先记住！！！
 stack<TreeNode*>s; TreeNode* cur = root;
 TreeNode* pre = nullptr; s.push(root);
 while (!s.empty()) {
     cur = s.top(); 
     if ((!cur->left && !cur->right) || (pre && (pre == cur->left || pre == cur->right))) {
         cout << cur->val << "  ";
         pre = cur;
         s.pop();
     }
     else {
         if (cur->right) s.push(cur->right);
         if (cur->left) s.push(cur->left);
     }
 }
}

  2. BFS式遍历，即层序遍历---队列

    void levelorderSearch(TreeNode *root) {
 queue<TreeNode* >q; q.push(root);
 while (!q.empty()) {
     TreeNode* cur = q.front(); q.pop();
     cout << cur->val << "  ";
     if (cur->left)   q.push(cur->left);
     if (cur->right)     q.push(cur->right);
 }
}

    五、验证树---递归、队列
    (1)是否是完全二叉树---队列
    我们通过改变层序遍历队列的入队规则，来实现这一功能，具体见博文：刷 树专题 有感

    bool isValidCBT(TreeNode *root){
 queue<TreeNode*>q;q.push(root);
 TreeNode *front=nullptr;
 while(front=q.front()){//放入非空节点的左右节点
     q.push(front->left);
     q.push(front->right);
     q.pop();
 }
 while(!q.empty()){
     TreeNode *cur=q.front();
     if(cur!=nullptr)    return 0;
     q.pop();
 }
 return 1;
}

    (2)验证是否是满二叉树---递归

    bool isValidFBT(TreeNode *root){
 //base case
 if(!root)    return 1;
 if((!root->left&&root->right)||(root->left&&!root->right))    return 0;
 //operations
 return isValidFBT(root->left)&&isValidFBT(root->right);
}

    (3)验证是否是有效二叉搜索树---递归

    bool isValidBST(TreeNode *root){
 return helper(root,LONG_MIN,LONG_MAX);
}
bool helper(TreeNode* root,long long lower,long long upper){
 //base case
 if(root->val<=lower||root->val>=upper)    return 0;
 //operations:维护最大最小值
 return helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);
}

    (4)验证是否是平衡二叉树---递归、队列
    首先必须了解下如何获取一棵二叉树的深度，有两种方法，一种是层序遍历不断更新队列，来记录最大深度
    一种是直接递归实现。下面先写一下这两种方法.

    //获取树的深度
//方法一：非递归实现
int depth1(TreeNode* root) {
 queue<TreeNode*>q; q.push(root);
 int res = 0;
 while (!q.empty()) {
     queue<TreeNode*>tmp;
     while (!q.empty()) {
         TreeNode* cur = q.front();
         if (cur->left)   tmp.push(cur->left);
         if (cur->right)  tmp.push(cur->right);
         q.pop();
     }
     q=tmp;
     ++res;
 }
 return res;
}
//方法二：递归实现
int depth2(TreeNode* root) {
 //base case
 if (!root)   return 0;
 //operations
 return max(depth2(root->left), depth2(root->right)) + 1;   
}

    那么，接下来就是如何验证是否是平衡二叉树，抓住平衡二叉树的特点：左右树的深度差不超过1。
    有两种方法，一种是再计算深度的同时，判断是否符合平衡条件，一种是分开，先计算深度，再判断是否符合平衡条件。

    /*方法一：计算深度的同时，判断是否符合平衡条件*/
bool isBalancedBT(TreeNode *root){
 return depth(root)!=-1;
}
int depth(TreeNode *root){
 //base case 
 if(!root)    return 0;
 //operations
 int left=depth(root->left);
 if(left==-1)    return -1;
 int right=depth(root->right);
 if(right==-1)    return -1;
 return abs(left-right)<2 ? max(left,right)+1:-1;
}
/*方法二:先计算深度，再判断是否符合平衡条件*/
bool isBalancedBT(TreeNode *root){
 return abs(depth(root->left)-depth(root->right))<2&&isBalancedBT(root->left)&&isBalancedBT(root->right);
}
int depth(TreeNode *root){
 //base case
 if(!root)    return 0;
 //operations
 return max(depth(root->left),depth(root->right))+1;
}

    六、修改树

  3. 搜索二叉树的插入与删除
    插入很简单，跟建立的函数一样的，不再说明。
    删除就会比较麻烦，需要分两种情况。
    (1)如果删除节点只含左树或右树，那么只需要修改指针就行了，就像删除链表节点一样。
    (2)如果删除节点有左右树，那么就需要分两种情况考虑，如图所示
    如图所示，删除A节点(A节点是树内的某一个节点)
    图片说明
    为保证搜索二叉树中序遍历结果是排序的特点，我们可以用删除节点在中序遍历中的前驱或后继来替代删除的节点。
    我们需要找到A的前驱(后继)，同时获取A的前驱(后继)的父节点，然后直接将A的前驱(后继)的值赋给删除节点即可，然后再改变指针指向就行了。

    //需要一个查找函数
//搜索二叉树查找
TreeNode * searchBSTnode(TreeNode* root, int val) {
 //recursion
 //base case
 if (!root)   return nullptr;
 if (root->val == val)  return root;
 //operations
 if (val < root->val)   searchBSTnode(root->left, val);
 else if(val > root->val)   searchBSTnode(root->right, val);
}
//////////////////////////////////////////////
bool deleteBSTnode(TreeNode *root,int val){
 //先查找
 TreeNode *node=searchBSTnode(root,val);
 if(!node)    return 0;
 //删除
 if(!node->left&&!node->right)    free(node);
 else if(node->left&&!node->right){
     TreeNode *tmp=node;
     node=node->left;
     free(tmp);
 }
 else if(node->right&&!node->left){
     TreeNode *tmp=node;
     node=node->right;
     free(tmp);
 }
 else{
     TreeNode *node1=node->left,* node2=node1->right;
     if(!node2){
         node->val=node1->val;
         TreeNode *tmp=node1;
         node->left=node1->left;
         free(tmp);
     }
     else{
         while(node2->right){//找前驱
             node1=node2;
             node2=node2->right;
         }
         node->val=node2->val;
         TreeNode *tmp=node2;
         node1->right=node2->left;
         free(tmp);
     }
 }
 return 1;
}

  4. 平衡二叉树的插入和删除
    插入跟建立一样。
    删除的话，就是先用搜索二叉树的方法删除后，再调用balance函数调整就可了。
    但其实这里还并不是很确定！！！

    balancedBT* searchbalancedBTnode(balancedBT* root, int val) {
 //recursion
 //base case
 if (!root)   return nullptr;
 if (root->val == val)  return root;
 //operations
 if (val < root->val)   searchbalancedBTnode(root->left, val);
 else if (val > root->val)   searchbalancedBTnode(root->right, val);
}
//平衡二叉树删除
balancedBT* deletebalancedBT(balancedBT* root, int val) {
 //先查找
 balancedBT* node = searchbalancedBTnode(root, val);
 if (!node)    return nullptr;
 //删除
 if (!node->left && !node->right)    free(node);
 else if (node->left && !node->right) {
     balancedBT* tmp = node;
     node = node->left;
     free(tmp);
 }
 else if (node->right && !node->left) {
     balancedBT* tmp = node;
     node = node->right;
     free(tmp);
 }
 else {
     balancedBT* node1 = node->left, * node2 = node1->right;
     if (!node2) {
         node->val = node1->val;
         balancedBT* tmp = node1;
         node->left = node1->left;
         free(tmp);
     }
     else {
         while (node2->right) {//找前驱
             node1 = node2;
             node2 = node2->right;
         }
         node->val = node2->val;
         balancedBT* tmp = node2;
         node1->right = node2->left;
         free(tmp);
     }
 }
 return balance(root,val);
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-24 20:53
点赞 评论 收藏
分享
11-23 14:55
小红书_社区技术部_前端开发(实习员工)
9.24古茗一面
今年没想到卷成这样，面试表现挺好的，但是问多久出结果，说是候选人特别多，可能要很久，然后就一直没给后续，估计是进池子了。自我介绍如何了解到的我们公司心动的复杂权限场景以及性能优化，按钮权限，菜单权限，接口权限都是怎么实现的ci/cd是什么大文件的分片上传怎么实现的如何保证每一片的完整性文件传输某一片失败的该怎么办为什么这样子设计介绍一下promisetry&nbsp;catch能否监听到promise的错误，为什么promise.race的特点promise还有什么方法hash路由与history路由的区别为什么history需要服务端配置入口地址小程序开发的了解前端浏览器缓存mvc和mvvm是什么什么...
查看26道真题和解析 面经烤面筋
点赞 评论 收藏
分享
头像
09-30 15:16
已编辑
携程_前端(准入职员工)
点赞 评论 收藏
分享
头像
11-06 10:58
已编辑
门头沟学院 嵌入式工程师
和HR的默契
看似什么都没问，实则什么都问了，哈哈哈哈哈哈哈哈哈字节跳动，我来了！#牛客创作赏金赛##字节求职进展汇总#
双非25想找富婆不想打工：哦，这该死的伦敦腔，我敢打赌，你简直是个天才，如果我有offer的话，我一定用offer狠狠的打在你的脸上
牛客创作赏金赛 字节求职进展汇总
点赞 评论 收藏
分享
11-21 15:55
学而思_学科教育管理(准入职员工)
学而思教育（好未来）2025届校园招聘进
学而思教育（好未来）2025届校园招聘进行中【企业介绍】国内教培行业龙头，上市企业；学而思成立于2003年，是好未来旗下综合性教育品牌，目前已有39所分校、350+教学点。【面向对象】22-25届毕业生均可投递，专业不限，应聘阶段无教资要求【招聘岗位】全职授课主讲教师-高中：数、理、化、英-彼芯：理科、文科-素养：科学思维、人文创作、机器人编程、国际英语-竞赛：数理化信息学【薪酬结构】基本工资+课时费；综合年收入：10~30万；每年2-6次涨薪，入职2~3年平均涨幅40%~50%【工作地点】全国39城内推链接：https://app.mokahr.com/m/campus-recruitmen...
投递好未来等公司10个岗位 >
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
323144次浏览 3000人参与
# 上班苦还是上学苦呢？ #
69929次浏览 617人参与
# 阿里云管培生offer #
36420次浏览 421人参与
# 地方国企笔面经互助 #
4402次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
20695次浏览 357人参与
# 选完offer后，你后悔学本专业吗 #
21552次浏览 155人参与
# 百度开奖 #
180311次浏览 1128人参与
# 如何一边实习一边秋招 #
995892次浏览 12661人参与
# 我的实习求职记录 #
6067477次浏览 83521人参与
# 招聘要求与实际实习内容不符怎么办 #
10679次浏览 276人参与
# 入职第一天，你准备什么时候下班 #
21498次浏览 144人参与
# 许愿池 #
214553次浏览 2534人参与
# bilibili求职进展汇总 #
32893次浏览 354人参与
# 学历or实习经历，哪个更重要 #
53503次浏览 419人参与
# 实习工作，你找得还顺利吗？ #
247562次浏览 2902人参与
# 海康威视求职进展汇总 #
400373次浏览 3407人参与
# 通信硬件薪资爆料 #
607642次浏览 5150人参与
# 正在实习的你，几点下班 #
52994次浏览 395人参与
# 如果再来一次，你还会学硬件吗 #
95067次浏览 1169人参与
# 工作两年想退休了 #
52961次浏览 672人参与
# 软件开发薪资爆料 #
2192643次浏览 21878人参与
# 我的失利项目复盘 #
668164次浏览 11247人参与
牛客网
牛客企业服务