当前位置： 首页 > article >正文

7. 二叉树****

article 2025/3/25 8:24:13

目录

1. 树的概念

2. 堆

2.1 性质和概念

2.2 堆的实现

2.3 堆排序

1. 建堆

2.在建好的堆上进行排序

2.4 TOP-K问题

1. 数据中前K个元素建堆

2.用剩余的元素依次和堆顶比大小，根据大小替换堆顶

3.二叉树的一些常见问题

1.965. 单值二叉树

2.100. 相同的树

3.101. 对称二叉树

4.二叉树前序遍历144. 二叉树的前序遍历

5. 二叉树的中序遍历94. 二叉树的中序遍历

6.二叉树的后序遍历145. 二叉树的后序遍历

7.572. 另一棵树的子树

8.读入用户输入的一串前序遍历字符串，根据此字符串建立一个二叉树，再对二叉树进行中序遍历，输出遍历结果二叉树遍历_牛客题霸_牛客网

4.搜索树

1.概念性质

2.增删查改

3.缺陷

4. 进阶面试题

1. 二叉树创建字符串606. 根据二叉树创建字符串

2.102. 二叉树的层序遍历

3.自底向上的层序遍历107. 二叉树的层序遍历 II

4.最近公共祖先236. 二叉树的最近公共祖先

5.LCR 155. 将二叉搜索树转化为排序的双向链表

6.105. 从前序与中序遍历序列构造二叉树

7.106. 从中序与后序遍历序列构造二叉树

 8. 二叉树前序遍历—非递归

9.二叉树中序遍历-非递归

10.二叉树后序遍历-非递归

5.缺陷解决方案：平衡树

 

1. 树的概念

树是一种非线性的数据结构，它是由有限个结点组成的一个具有层次关系的集合。

  • 有一个特殊的结点，称为根结点
  • 除根结点外，其余结点被分成若干个互不相交的集合，每一个集合又是一颗结构与树类似的子树。
  • 因此，树是递归定义的

树形结构中，子树之间不能有交集，否则就不是树形结构。

  • 子树是不相交的
  • 除根节点外，每个结点有且仅有一个父结点

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

        对于任何一颗二叉树，如果度为0的叶子结点个数为n0， 度为2的分支节点个数为n2，则有：

n0 = n2+1。

高度为h的完全二叉树的结点数量范围：[2^(h-1)， 2^h-1]

2. 堆

2.1 性质和概念

        普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。

        堆可以筛选出树的大值或小值，作用很大，比如堆排序，冒泡排序。根结点最大的堆叫做大根堆，根节点最小的堆叫做小根堆。

  • 堆中某个结点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树
逻辑结构：
        9
       / \
      7   5
     / \ / \
    6  3 2  1

存储结构：
[9, 7, 5, 6, 3, 2, 1]

父节点的索引为 (i - 1) / 2

2.2 堆的实现

#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
    HPDataType *a;
    int size;
    int capacity;
}Heap;

//堆的构建
void HeapInit(Heap *php)
{
    php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
    if(php->a == NULL)
    {
        perror("malloc fail");
        return;
    }
    php->size = 0;
    php->capacity = 4;
}

void HeapDestroy(Heap *php)
{
    assert(php);
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

void Swap(HPDataType *a, HPDataType *b)
{
    HPDataType tmp = *a;
    *a = *b;
    *b = tmp;
}

void AdjustUp(HPDataType *a, int child)
{
    int parent = (child - 1) / 2;
    while(child > 0)
    {
        if(a[child] > a[parent])//>建大堆，孩子大于父亲就向父亲的位置调整
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child-1) / 2;//parent向上更新
        }
        else//孩子小于父亲，位置合适，break
            break;
    }
}

void HeapPush(Heap *php, HPDataType x)
{
    assert(php);
    if(php->size == php->capacity)
    {
        HPDataType *tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
        if(tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        php->a = tmp;
        php->capacity *= 2;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

void AdjustDown(HPDataType *a, int parent, int size)
{
    int child = parent * 2 + 1;
    while(child < size)
    {
        if(child + 1 < size && a[child] < a[child + 1])//默认是左孩子，但是因为大根堆要用大的代替这个父亲，所以要找大的孩子
            child++;

        if(a[child] > a[parent])//孩子大于父亲，调整位置
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else//孩子小于父亲，位置合适，break
            break;
    }
}

void HeapPop(Heap* php)
{
    assert(php);
    if(php->size == 0)
        return;
    Swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, 0, php->size);
}

HPDataType HeapTop(Heap *php)
{
    assert(php);
    return php->a[0];
}

bool HeapEmpty(Heap *php)
{
    assert(php);
    return php->size == 0;
}

int HeapSize(Heap *php)
{
    assert(php);
    return php->size;
}

2.3 堆排序

1. 建堆

        升序：建大堆，每次取出最大值，放到数组末尾，逐步形成升序序列。

        降序：建小堆，每次取出最小值，放到数组末尾，逐步形成降序序列。

        向上调整的时间复杂度是O(NlogN)，向下调整的时间复杂度是O(N)，向上向下只是建堆的方式，至于是建大堆还是小堆，要看建堆中的大于号小于号。

        要注意使用向下调整建堆的前提是：左右子树是大或小堆，所以传的parent是叶子结点的父结点，size-1是最后一个叶子结点，-1 / 2 找到它的父节点

void HeapSort(HPDataType *a, int size)
{
    //1向上调整建堆
    for(int i = 1; i < size; i++)
    {
        AdjustUp(a, i);
    }
    //1向下调整建堆
    for(int i = (size-1-1)/2; i >= 0; i--)
    {
        AdjustDown(a, i, size);
    }
    //2利用堆删除思想排序
    for(int i = size - 1; i > 0; i--)
    {
        Swap(&a[0], &a[i]);
        AdjustDown(a, 0, i);
    }
}

int main()
{
    int a[10] = {2, 1, 5, 7, 4, 9, 3, 6, 8, 0};
    HeapSort(a, 10);
    for(int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}
2.在建好的堆上进行排序

        a[0]为堆顶，也是最大值，将他和最后一个元素交换，此时堆顶就是最小的，然后把这个最小的元素向下调整，直到满足还是大根堆。i--，意思是最后一个排好的最大的值就不参与排序了，继续把当前的最大值和“当前”的最末尾进行交换......

2.4 TOP-K问题

        即求数据中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

        对于TOP-K问题，能想到的最简单的方式就是排序，但是如果数据量非常大，排序就不太可取了。最佳的方式就是用堆来解决。

1. 数据中前K个元素建堆

        前K大/第K大：建小堆，想要更大的元素，就得把小的放到堆顶，比堆顶大的一来就出掉堆顶

        前K小/第K小：建大堆，想要更小的元素，就得把大的放到堆顶，比堆顶小的一来就出掉堆顶

2.用剩余的元素依次和堆顶比大小，根据大小替换堆顶

3.二叉树的一些常见问题

1.965. 单值二叉树
class Solution 
{
public:
    bool isUnivalTree(TreeNode* root) 
    {
        if(root == nullptr)
            return true;
        if((root->left && root->left->val != root->val) || 
           (root->right && root->right->val != root->val))
            return false;

        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
};
2.100. 相同的树
class Solution 
{
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        if(p == nullptr && q == nullptr)
            return true;
        //走到这说明，不可能都为空
        if(p == nullptr || q == nullptr)//此时有一个为空，另一个不为空，则false
            return false;
        //两个都不为空，则比较val
        if(p->val != q->val)
            return false;
        
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
3.101. 对称二叉树
class Solution 
{
    bool check(TreeNode* left, TreeNode* right)
    {
        if(left == nullptr && right == nullptr)
            return true;
        if(left == nullptr || right == nullptr)
            return false;
        if(left->val == right->val 
            && check(left->left, right->right) 
            && check(left->right, right->left))
            return true;
        else
            return false;
    }
public:
    bool isSymmetric(TreeNode* root) 
    {
        if(root == nullptr)
            return true;
        return check(root->left, root->right);
    }
};
4.二叉树前序遍历144. 二叉树的前序遍历
class Solution 
{
    void preorder(vector<int>& rv, TreeNode* root)
    {
        if(root == nullptr)
            return;
        rv.push_back(root->val);
        preorder(rv, root->left);
        preorder(rv, root->right);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> rv;
        preorder(rv, root);
        return rv;
    }
};
5. 二叉树的中序遍历94. 二叉树的中序遍历
class Solution 
{
public:
    void inorder(TreeNode* root, vector<int>& rv)
    {
        if(root == nullptr)
            return;
        inorder(root->left, rv);
        rv.push_back(root->val);
        inorder(root->right, rv);
    }
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> rv;
        inorder(root, rv);
        return rv;
    }
};
6.二叉树的后序遍历145. 二叉树的后序遍历
class Solution 
{
public:
    void postorder(vector<int>& rv, TreeNode* root)
    {
        if(root == nullptr)
            return;
        postorder(rv, root->left);
        postorder(rv, root->right);
        rv.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> rv;
        postorder(rv, root);
        return rv;
    }
};
7.572. 另一棵树的子树
class Solution 
{
public:
    bool isSametree(TreeNode* t1, TreeNode* t2)
    {
        if(t1 == nullptr && t2 == nullptr)
            return true;
        if(t1 == nullptr || t2 == nullptr)
            return false;
        return t1->val == t2->val 
            && isSametree(t1->left, t2->left) 
            && isSametree(t1->right, t2->right);
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) 
    {
        if(root == nullptr)
            return false;

        if(isSametree(root, subRoot))
            return true;

        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};
8.读入用户输入的一串前序遍历字符串，根据此字符串建立一个二叉树，再对二叉树进行中序遍历，输出遍历结果二叉树遍历_牛客题霸_牛客网
#include <iostream>
using namespace std;

struct TreeNode
{
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) 
        : val(x)
        , left(nullptr)
        , right(nullptr) 
    {}
};

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

TreeNode* creatTree(string& s, int& i)
{
    if(s[i] == '#')
    {
        i++;
        return nullptr;
    }
    auto root = new TreeNode(s[i++]);
    root->left = creatTree(s, i);
    root->right = creatTree(s, i);
    return root;
}

int main() 
{
    string s;
    cin >> s;
    int i = 0;
    TreeNode* root = creatTree(s, i);
    Inorder(root);
    return 0;
}

4.搜索树

1.概念性质

2.增删查改

3.缺陷

都在下面这篇文章里写到了：1.二叉树进阶-CSDN博客

4. 进阶面试题

1. 二叉树创建字符串606. 根据二叉树创建字符串
class Solution 
{
public:
    string tree2str(TreeNode* root) 
    {
        if(root == nullptr)
            return "";

        string rs = to_string(root->val);

        if(root->left || root->right)//1.左不为空，肯定要添加；2.左为空，但是右不为空，不能省略括号
        {
            rs += "(";
            rs += tree2str(root->left);
            rs += ")";
        }

        if(root->right)//1.若右不为空，就该添加；2.都为空，都省略
        {
            rs += "(";
            rs += tree2str(root->right);
            rs += ")";
        }
        return rs;
    }
};
2.102. 二叉树的层序遍历
class Solution 
{
    vector<vector<int>> rvv;
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        bfs(root);
        return rvv;
    }

    void bfs(TreeNode* root)
    {
        if(root == nullptr)
            return;
        queue<TreeNode*> q;
        q.emplace(root);
        while(!q.empty())
        {
            vector<int> tmp;
            int sz = q.size();
            while(sz--)
            {
                auto cur = q.front();
                q.pop();
                tmp.push_back(cur->val);
                if(cur->left)
                    q.emplace(cur->left);
                if(cur->right)
                    q.emplace(cur->right);
            }
            rvv.emplace_back(tmp);
        }
    }
};
3.自底向上的层序遍历107. 二叉树的层序遍历 II
class Solution 
{
    vector<vector<int>> rvv;
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
        bfs(root);
        return rvv;
    }

    void bfs(TreeNode* root)
    {
        if(root == nullptr)
            return;
        queue<TreeNode*> q;
        q.emplace(root);
        while(!q.empty())
        {
            vector<int> tmp;
            int sz = q.size();
            while(sz--)
            {
                auto cur = q.front();
                q.pop();
                tmp.emplace_back(cur->val);
                if(cur->left)
                    q.emplace(cur->left);
                if(cur->right)
                    q.emplace(cur->right);
            }
            rvv.emplace_back(tmp);
        }
        reverse(rvv.begin(), rvv.end());
    }
};
4.最近公共祖先236. 二叉树的最近公共祖先
class Solution 
{
    bool InTree(TreeNode* tree, TreeNode* x)
    {
        if(tree == nullptr)
            return false;
        return tree == x || InTree(tree->left, x) || InTree(tree->right, x);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root == nullptr)
            return root;
        if(p == root || q == root)
            return root;

        bool pleft = InTree(root->left, p), pright = InTree(root->right, p);
        bool qleft = InTree(root->left, q), qright = InTree(root->right, q);

        if((pleft && qright) || (pright && qleft))
            return root;
        else if(pleft && qleft)
            return lowestCommonAncestor(root->left, p, q);
        else
            return lowestCommonAncestor(root->right, p, q);
    }
};
5.LCR 155. 将二叉搜索树转化为排序的双向链表
class Solution 
{
    void InOrder(Node* cur, Node* prev)
    {
        if(cur == nullptr)
            return;
        InOrder(cur->left, prev);
        cur->left = prev;
        if(prev)
            prev->right = cur;
        prev = cur;
        InOrder(cur->right, prev);
    }
public:
    Node* treeToDoublyList(Node* root) 
    {
        if(root == nullptr)
            return nullptr;
        Node* prev = nullptr;
        InOrder(root, prev);
        // if(prev == nullptr)
        //     cout << 1 << endl;
        Node* head = root;
        while(head && head->left)
        {
            head = head->left;
        }
        head->left = prev;//如果prev不传引用，递归回溯回来的prev是nullptr，就不是更新后的prev了
        prev->right = head;
        return head;
    }
};
6.105. 从前序与中序遍历序列构造二叉树
class Solution 
{
    TreeNode* _buildR(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
    {
        if(inbegin > inend)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[prei]);
        int rooti = inbegin;
        while(rooti <= inend)
        {
            if(preorder[prei] == inorder[rooti])
                break;
            rooti++;
        }
        ++prei;
        root->left = _buildR(preorder, inorder, prei, inbegin, rooti-1);
        root->right = _buildR(preorder, inorder, prei, rooti+1, inend);//如果prei不传引用，left走完，prei还是原来的prei
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int i = 0;
        return _buildR(preorder, inorder, i, 0, inorder.size()-1);
    }
};
7.106. 从中序与后序遍历序列构造二叉树
class Solution 
{
    TreeNode* _buildR(vector<int>& inorder, vector<int>& postorder, int& posti, int inbegin, int inend)
    {
        if(inbegin > inend)
            return nullptr;
        TreeNode* root = new TreeNode(postorder[posti]);
        int rooti = inbegin;
        while(rooti <= inend)
        {
            if(inorder[rooti] == postorder[posti])
                break;
            rooti++;
        }
        posti--;

        root->right = _buildR(inorder, postorder, posti, rooti+1, inend);
        root->left = _buildR(inorder, postorder, posti, inbegin, rooti-1);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        int i = postorder.size()-1;
        return _buildR(inorder, postorder, i, 0, inorder.size()-1);
    }
};
 8. 二叉树前序遍历—非递归
class Solution 
{
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> rv;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                rv.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();//某个左路结点
            st.pop();
            cur = top->right;//这个左路结点的右子树
        }
        return rv;
    }
};
9.二叉树中序遍历-非递归
class Solution 
{
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> rv;
        stack<TreeNode*> st;
        TreeNode* cur = root;

        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();

            rv.push_back(top->val);
            cur = top->right;
        }
        return rv;
    }
};
10.二叉树后序遍历-非递归
class Solution 
{
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> rv;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        stack<TreeNode*> st;

        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
//1.top右为空，说明这个左路结点的右子树为空，可以直接打印值，否则要先打印右子树中的值；
//2.prev在top的右，说明在访问top前访问的是top的右，即top左右都访问完毕，该访问根(top)了
            if(top->right == nullptr || prev == top->right)
            {
                rv.push_back(top->val);
                st.pop();
                prev = top;
            }
            else//说明top的右不为空，而且也没访问过右，是第一次访问top，应该去访问右
            {
                cur = top->right;
            }
        }
        return rv;
    }
};

5.缺陷解决方案：平衡树

下一章介绍


http://www.kler.cn/a/596990.html

相关文章：

  • AXI总线之相关应用
  • ffmpeg+ubuntu编译库（完整版本）
  • Scrapy 入门教程
  • 探索 Ollama：开源大语言模型平台的无限可能​
  • Linux：xxx is not in the sudoers file. This incident will be reported.
  • PyTorch中BatchNorm2D的实现与BatchNorm1D的区别解析
  • HCL—我与虚拟机的爱恨情仇[特殊字符][特殊字符]‍[特殊字符]️
  • 32.[前端开发-JavaScript基础]Day09-元素操作-window滚动-事件处理-事件委托
  • 【gradio】全面解析 Gradio 的 Blocks 框架：构建灵活的 Python 前端界面
  • Spring的IOC
  • dv-scroll-board 鼠标移入单元格显示单元格所有数据
  • systemd-networkd 的 /etc/systemd/network/*.network 的配置属性名称是不是严格区分大小写?是
  • 全面解读 联核科技四向穿梭车的常见功能介绍
  • 记录一次truncate导致MySQL夯住的故障
  • 【003安卓开发方案调研】之ReactNative技术开发安卓
  • 金蝶云星辰数据集成技术案例：采购退货对接旺店通
  • SpringBoot项目实战（初级）
  • 在Android Studio中，如何快速为变量添加m？
  • 2025年3月22日（自动控制原理）
  • 【赵渝强老师】在Docker中运行达梦数据库