第五章节 树和二叉树

参考：1.���据结构C语言版|第2版；2.力扣；3.2024年数据结构考研复习指导。三个参考分别依次对应文章三个部分。

文章目录

• 第一部分
• • 基本概念
  • 基本性质
  • 存储结构
  • 经典应用
  • • 遍历
    • • 前序遍历
      • 中序遍历
      • 后序遍历
      • 层序遍历
      • 建树
      • • 根据先序序列加上中序序列建立二叉树
        • 根据后序序列加上中序序列建立二叉树
        • 计算
        • • 计算树的最小深度
          • 计算树的最大深度
          • Huffman树编码以及解码
          • 杂七杂八
          • 第二部分
          • 第三部分

            第一部分

            基本概念

            树是 n ( n ≥ 0 ) n(n\geq0) n(n≥0)个结点的有限集，它或为空树 ( n = 0 ) (n=0) (n=0)；或为非空树，对于非空树T：(1)有且仅有一个称之为根的结点；(2)除根结点以外的其余节点可分为 m ( m > 0 ) m(m>0) m(m>0)个互不相交的有限集 T 1 , T 2 , ⋯   , T m T_1,T_2,\cdots,T_m T1​,T2​,⋯,Tm​，其中每一个集合本身又是一棵树，并且称为根的子树。重要术语：孩子、兄弟、结点的度、树的高度、叶子或者终端结点。 二叉树是 n ( n ≥ 0 ) n(n\geq0) n(n≥0)个结点所构成的集合，它或为空树 ( n = 0 ) (n=0) (n=0)；或为非空树，对于非空树T：(1)有且仅有一个称之为根的结点；(2)除根结点以外的其余结点分为两个互不相交的子集 T 1 T_1 T1​和 T 2 T_2 T2​，分别称为T的左子树和右子树，且 T 1 T_1 T1​和 T 2 T_2 T2​本身又都是二叉树。满二叉树： 深度为k且含有 2 k − 1 2^k-1 2k−1个结点的二叉树。完全二叉树： 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

            基本性质

            性质1： 在二叉树的第 i i i层上至多有 2 i − 1 2^{i-1} 2i−1个结点 ( i ≥ 1 ) (i\geq1) (i≥1)。性质2： 深度为k的二叉树至多有 2 k − 1 2^k-1 2k−1个结点 ( k ≥ 1 ) (k\geq 1) (k≥1)。性质3： 对任何一棵二叉树T，如果其终端结点数为 n 0 n_0 n0​，度为2的结点数为 n 2 n_2 n2​，则 n 0 = n 2 + 1 n_0=n_2+1 n0​=n2​+1。性质4： 具有n个结点的完全二叉树的深度为 [ l o g 2 n ] + 1 [log_2^n]+1 [log2n​]+1。性质5： 如果对一棵有n个结点的完全二叉树(其深度为 [ l o g 2 n ] + 1 [log_2^n]+1 [log2n​]+1)的结点按层序编号(从第1层到第 [ l o g 2 n ] + 1 [log_2^n]+1 [log2n​]+1层，每层从左到右)，则对任一结点 i ( 1 ≤ i ≤ n ) i(1\leq i\leq n) i(1≤i≤n)，有(1)如果 i = 1 i=1 i=1，则结点 i i i是二叉树的根，无双亲；如果 i > 1 i>1 i>1，则其双亲 P A R E N T ( i ) PARENT(i) PARENT(i)是节点 [ i / 2 ] [i/2] [i/2]。(2)如果 2 i > n 2i>n 2i>n，则结点 i i i无左孩子(结点 i i i为叶子结点)；否则其左孩子 L C H I L D ( i ) LCHILD(i) LCHILD(i)是结点 2 i 2i 2i。(3)如果 2 i + 1 > n 2i+1>n 2i+1>n，则结点 i i i无右孩子；否则其右孩子 R C H I L D ( i ) RCHILD(i) RCHILD(i)是结点 2 i + 1 2i+1 2i+1。

            存储结构

            顺序存储

            （）

            用零补全，参考堆吧。

            链式存储

            struct TreeNode {    int val;    TreeNode *left;    TreeNode *right;};

            经典应用

            遍历

            前序遍历

            递归

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector result;    vector preorderTraversal(TreeNode* root) {        PreOrder(root);        return result;    }    void PreOrder(TreeNode * root)    {        if (!root) return;        result.push_back(root->val);        PreOrder(root->left);        PreOrder(root->right);    }};

            非递归

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector preorderTraversal(TreeNode* root) {        vector result;        if (!root) return result;        stack z;        z.push(root);result.push_back(root->val);        while (!z.empty())            if (z.top()->left)            {                TreeNode * temp=z.top()->left;z.top()->left=nullptr;                z.push(temp);result.push_back(temp->val);            }            else if (z.top()->right)            {                TreeNode * temp=z.top()->right;z.top()->right=nullptr;                z.push(temp);result.push_back(temp->val);            }            else z.pop();        return result;    }};

            中序遍历

            递归

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector result;    vector inorderTraversal(TreeNode* root) {        InOrder(root);        return result;    }    void InOrder(TreeNode * root)    {        if (!root) return;        InOrder(root->left);        result.push_back(root->val);        InOrder(root->right);    }};

            非递归

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector inorderTraversal(TreeNode* root) {        vector result;        if (!root) return result;        stack z;        z.push(root);        while (!z.empty())            if (z.top()->left)            {                TreeNode * temp=z.top()->left;z.top()->left=nullptr;z.push(temp);            }            else            {                result.push_back(z.top()->val);                if (z.top()->right)                {                    TreeNode * temp=z.top()->right;z.pop();z.push(temp);                }                else z.pop();            }        return result;    }};

            后序遍历

            递归

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector result;    vector postorderTraversal(TreeNode* root) {        PostOrder(root);        return result;    }    void PostOrder(TreeNode * root)    {        if (!root) return;        PostOrder(root->left);        PostOrder(root->right);        result.push_back(root->val);    }};

            非递归

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector postorderTraversal(TreeNode* root) {        vector result;        if (!root) return result;        stack z;        z.push(root);        while (!z.empty())            if (z.top()->left)            {                TreeNode * temp=z.top()->left;z.top()->left=nullptr;z.push(temp);            }            else if (z.top()->right)            {                TreeNode * temp=z.top()->right;z.top()->right=nullptr;z.push(temp);            }            else {result.push_back(z.top()->val);z.pop();}        return result;    }};

            层序遍历

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector levelOrder(TreeNode* root) {        vector lb;        if (!root) return lb;        queue dl;        dl.push(root);        while (!dl.empty())        {            queue temp_dl;            vector temp_lb;            while (!dl.empty())            {                TreeNode * temp_node=dl.front();dl.pop();                if (temp_node->left) temp_dl.push(temp_node->left);                if (temp_node->right) temp_dl.push(temp_node->right);                temp_lb.push_back(temp_node->val);            }            lb.push_back(temp_lb);            dl=temp_dl;        }        return lb;    }};

            建树

            先序序列加上中序序列可以建立唯一的二叉树。

            后序序列加上中序序列可以建立唯一的二叉树。

            先序序列加上后序序列不能建立唯一的二叉树。

            根据先序序列加上中序序列建立二叉树

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector lb1,lb2;    TreeNode* buildTree(vector& preorder, vector& inorder) {        lb1=preorder;lb2=inorder;        TreeNode * result=new TreeNode;        traverse(result,0,lb1.size()-1,0,lb2.size()-1);        return result;    }    void traverse(TreeNode * node,int l1,int r1,int l2,int r2)    {        node->val=lb1[l1];        int m;        for (int i=l2;ival)            {                m=i;break;            }        if (m!=l2)        {            node->left=new TreeNode;            traverse(node->left,l1+1,l1+m-l2,l2,m-1);        }        if (m!=r2)        {            node->right=new TreeNode;            traverse(node->right,l1+m-l2+1,r1,m+1,r2);        }    }};

            根据后序序列加上中序序列建立二叉树

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    vector lb1,lb2;    TreeNode* buildTree(vector& inorder, vector& postorder) {        lb1=postorder;lb2=inorder;        TreeNode * result=new TreeNode;        traverse(result,0,lb1.size()-1,0,lb2.size()-1);        return result;    }    void traverse(TreeNode * node,int l1,int r1,int l2,int r2)    {        node->val=lb1[r1];        int m;        for (int i=l2;ival)            {                m=i;break;            }        if (m!=l2)        {            node->left=new TreeNode;            traverse(node->left,l1,r1-(r2-m)-1,l2,m-1);        }        if (m!=r2)        {            node->right=new TreeNode;            traverse(node->right,r1-(r2-m),r1-1,m+1,r2);        }    }};

            计算

            计算树的最小深度

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    int minDepth(TreeNode* root) {        if (!root) return 0;        if (!root->left) return minDepth(root->right)+1;        if (!root->right) return minDepth(root->left)+1;        if (!root->left and !root->right) return 0;        return min(minDepth(root->left),minDepth(root->right))+1;    }};

            计算树的最大深度

            /** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode() : val(0), left(nullptr), right(nullptr) {} *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:    int maxDepth(TreeNode* root) {        if (!root) return 0;        return max(maxDepth(root->left),maxDepth(root->right))+1;    }};

            Huffman树编码以及解码

            输入样例

            51 2 3 4 5010011001011

            输出样例

            010011001011abcde

            #include#include#include#includeusing namespace std;int n;vector lt1;struct Node{    int x=-1;    Node * l=nullptr;    Node * r=nullptr;};vector lt2;pair function1(){    vector::iterator zz1=lt2.begin(),zz2=lt2.begin()+1;    if ((*zz1)->x>(*zz2)->x)     {        vector::iterator zz_temp=zz1;zz1=zz2;zz2=zz_temp;    }    for (vector::iterator zz3=lt2.begin()+2;zz3!=lt2.end();zz3++)        if ((*zz3)->xx) {zz2=zz1;zz1=zz3;}        else if ((*zz3)->xx) zz2=zz3;    //这样做使huffman树唯一    Node * zz1node=*zz1;Node * zz2node=*zz2;    bool x=zz1    for (int i=0;i        Node * nodel;Node * noder;        pairx+noder->x;        node_father->l=nodel;        node_father->r=noder;        lt2.push_back(node_father);    }}typedef Node * Tree;unordered_map zd;//构建字典void function2(Node * node,string s){    if (node->l==nullptr and node->r==nullptr)    {        zd[node->x]=s;return;    }    if (node->l!=nullptr) function2(node->l,s+'0');    if (node->r!=nullptr) function2(node->r,s+'1');}int function4(int x){    for (int i=0;i    string s;cin>s;Node * temp=node;    for (int i=0;i        if (s[i]=='0') temp=temp-l;        else temp=temp->r;        if (temp->l==nullptr and temp->r==nullptr)        {            int x=function4(temp->x);            cout    //n大于等于2;    cinn;    for (int i=0;i        int x;cinx;        lt1.push_back(x);        Node * node=new Node;node-x=x;lt2.push_back(node);    }    create();    Tree root=lt2[0];    string s;    function2(root,s);    for (int x:lt1) cout    char s;    int prev;};    int position;    next * brother;};struct node{    char s;    next * child;};