关于树的总结

一、树的基础了解
(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);
}
全部评论

相关推荐

10-24 02:15
美团_测试开发
出生在1024的天选码农
🍜&nbsp;那年的1024，我在食堂悟了道&nbsp;21年10月24日晚上，当时我正坐在学校食堂吃着我最爱吃的鸡汤米线，因为过生日，所以给自己加了个卤蛋。手里刷着抖音，然后刷到一条“1024程序员节”，我当时就有点好奇，这节日咋和我生日同一天？直到想起2的10次方等于1024才明白原因，然后就想难道我命中注定就是做程序员的吗？然后就有了接下来的一系列故事。第一赚-选学校&nbsp;因为煮包当时高考考的也很一般刚过一本线，选专业也没有任何方向就是胡乱选，当时其实想报的是机械制造及其自动化，奈何煮包的分数不够一般的大学也上不了只能去学院，当时也是好面子觉得学院可能不好听完全没有参考什么专业排名，也是误打误撞做了个正确的选...
mengnankk：天生程序员啊明哥
我的第一个1024节
点赞 评论 收藏
分享
10-23 19:07
广东海洋大学 Java
从美团索引题出发，一题深入浅出讲明白 MySQL 索引的一切！
最近碰到有朋友在问这道题，我看到这道题就觉得相当有意思，因为一道&nbsp;SQL&nbsp;索引搭建就串联了好几个&nbsp;MySQL&nbsp;索引的相关知识（联合索引、回表查询、文件排序、最左匹配原则、索引下推），在之前我觉得很难把这些知识点串连起来，但是这道题就给了我一个想法和切入点。其实所有的问题都源自于&nbsp;MySQL&nbsp;索引&nbsp;B+&nbsp;树的结构特征，所以我就明线解题，暗线讲解索引树结构和其导致的特性，呕心沥血连着写了五六个小时，希望对背八股的兄弟们有用。https://mp.weixin.qq.com/s/NAhZF96uN7uP2UaoS6-YnA&nbsp;，文章格式不方便搬运所以直接贴链接了，也可以关注我公众号Java&nbsp;Time，...
一起聊美团
点赞 评论 收藏
分享
头像
09-01 15:54
桂林电子科技大学 安卓
点赞 评论 收藏
分享
09-17 11:50
华中科技大学 Java
点赞 评论 收藏
分享
头像
10-23 10:21
北京理工大学 算法工程师
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# i人适合做什么工作 #
5042次浏览 61人参与
# 大家实习每天都在干啥 #
95722次浏览 533人参与
# 快手技术岗信息交流阵地 #
14098次浏览 80人参与
# 我是面试官，请用一句话让我破防 #
6055次浏览 52人参与
# 你认为哪些项目算烂大街？ #
72896次浏览 607人参与
# 如果秋招能重来，我会____ #
21434次浏览 195人参与
# “vivo”个offer #
28076次浏览 203人参与
# 许愿池 #
321021次浏览 2905人参与
# 校招生月薪1W算什么水平 #
7897次浏览 54人参与
# 硬件应届生薪资是否普遍偏低？ #
88226次浏览 559人参与
# 华为池子有多大 #
105438次浏览 740人参与
# 苦尽甘来时，再讲来时路 #
20386次浏览 306人参与
# 作业帮求职进展汇总 #
70573次浏览 484人参与
# 如果上班像打游戏，你最想解锁什么技能 #
4080次浏览 43人参与
# 一份好的简历长什么样？ #
10622次浏览 242人参与
# 为了实习逃课值吗？ #
17060次浏览 147人参与
# 你认为小厂实习有用吗？ #
94932次浏览 609人参与
# 秋招许愿，本周能____ #
20155次浏览 135人参与
# 班味很重的人是啥样的？ #
6151次浏览 39人参与
# 投递无反馈，如何优化求职策略？ #
3528次浏览 32人参与
# 大学最后一个寒假，我想…… #
62378次浏览 668人参与
# 机械制造秋招总结 #
84137次浏览 826人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务