【数据结构】第5章树和二叉树二叉树

「爱情、让人受尽委屈。」 2022-11-28 13:41 194阅读 0赞

【二叉树的啦啦啦啦】

--------------------

## 1、二叉树的类型 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]  
**满二叉树**：深度为 k 且含有 2 ^ k - 1 个结点的二叉树。每一层上的结点数都是最大结点数，即每一层l的结点数都具有最大值 2 ^ (i - 1) 可以对满二叉树的结点进行连续编号， 约定编号从根结点起， 自上而下， 自左至右  
**完全二叉树**：深度为 k 的， 有n个结点的二叉树， 其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应。(1) 叶子结点只可能在层次最大的两层上出现； (2) 对任一结点， 若其右分支下的子孙的最大层次为 l ，则其左分支下的子孙的最大层次必为l或 l + 1

## 2、二叉树的性质 ##

**性质1：在二叉树的第 i 层上至多有 2 ^ (i - 1) 个结点（i >= 1)  
性质2：深度为 k 的二叉树至多有 2 ^ k - 1个结点 (k >= 1)  
性质3：对任何一棵二叉树T,，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1**  
证明：  
先看结点数。因为二叉树中所有结点的度均小于或等于2, 所以其结点总数为 n = n0 + n1 + n2 ①  
再看分支数。除了根结点外，其余结点都有一个分支进入，设B为分支总数，则 n = B + 1。这些分支是由度为 1 或 2 的结点射出的，所以又有 B = n1 + 2n2 。于是得 n = n1 + 2n2 + 1 ②  
联立得 n0 = n2 + 1  
![在这里插入图片描述][20200818092420325.png_pic] ![在这里插入图片描述][20200818205020291.png_pic]![在这里插入图片描述][2020081809234145.png_pic]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic]

## 3、二叉树的遍历 ##

假如从 L、D、R分别表示遍历左子树、访 问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。 若限定**先左后右**，则只有前3种情况，分别称之为先（根） 序遍历、中（根） 序遍历和后（根） 序遍历。还有按层次遍历二叉树的方式，这种方式按照 “从上到下，从左到右＂ 的顺序遍历二叉树，即先遍历二叉树第一层的结点，然后是第二层的结点，直到最底层的结点，对每一层的遍历按照从左到右的次序进行。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 2]  
中序遍历非递归（栈）示意图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 3]  
由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。  
例：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA, 请画出这棵二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 4]  
先序遍历的顺序建立二叉链表，对图5.10(b)所示的二叉树，读入字符的顺序为： ABC\#\#DE\#G\#\#F\#\#\# (其中＃表示 空树），可建立相应的二叉链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 5]

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef char TElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    -----二叉树的顺序储存表示-----
    //#define MAXTSIZE 100                    //二叉树的最大结点数
    //typedef TElemType SqBiTree[MAXTSIZE];   //0号单元存储根结点
    //SqBiTree bt;
    
    //-----二叉树的二叉链式存储表示-----
    typedef struct BiTNode
    {
        
        TElemType data;
        struct BiTNode *lchild, *rchild;
    }BiTNode, *BiTree;
    
    BiTree T;
    
    // //1
    // InitBiTree(&T)
    // //2
    // DestroyBiTree(&T)
    
    //3、先序遍历的顺序建立二叉链表 
    void CreateBiTree(BiTree &T)
    {
        //按先序次序输入二叉树中结点的值（ 一个字符）， 创建二叉链表表示的二叉树T
        TElemType ch;
        cin>>ch;
        if(ch == '#')                    //递归结束， 建空树
            T = NULL;
        else                            //递归创建二叉树
        {
        
            T = new BiTNode;            //生成根结点
            T->data = ch;               //根结点数据域置为 ch
            CreateBiTree(T->lchild);    //递归创建左子树
            CreateBiTree(T->rchild);    //递归创建右子树
        }
    }
    
    // //4
    // ClearBiTree(&T)
    // //5
    // BiTreeEmpty(T)
    // //6
    // BiTreeDepth(T)
    // //7
    // Root(T)
    // //8
    // Value(T, e)
    // //9
    // Assign(T, e, value)
    // //10
    // Parent(T, e)
    // //11
    // LeftChild(T, e)
    // //12 
    // RightChild(T, e)
    // //13
    // LeftSibling(T, e)
    // //14
    // RightSibling(T, e)
    // //15
    // InsertChild(&T, p, LR, c)
    // //16
    // DeleteChild(&T, p, LR)
    
    //17、先序遍历二叉树
    void PreOrderTraverse(BiTree T)
    {
        //先序遍历二叉树T的递归算法
        if(T)                               //若二叉树非空 
        {
        
            cout<<T->data;                  //访问根结点 
            PreOrderTraverse(T->lchild);     //中序遍历左子树 
            PreOrderTraverse(T->rchild);     //中序遍历右子树
        }
    }
    
    //18、中序遍历二叉树
    void InOrderTraverse(BiTree T)
    {
        //中序遍历二叉树T的递归算法
        if(T)                               //若二叉树非空 
        {
        
            InOrderTraverse(T->lchild);     //中序遍历左子树 
            cout<<T->data;                  //访问根结点 
            InOrderTraverse(T->rchild);     //中序遍历右子树
        }
    }
    
    // //18、中序遍历二叉树
    // void InOrderTraverse(BiTree T)
    // {//中序遍历二叉树T的非递归算法
    //     InitStack(S);
    //     BiTNode *p = T;
    //     BiTNode *q = new BiTNode;
    //     while(p || !StackEmpty(S))
    //     {
        
    //         if(p)                   //p非空
    //         {
        
    //             Push(S, p);         //根指针进栈
    //             p = p->lchild;      //遍历左子树
    //         }
    //         else                    //p为空
    //         {
        
    //             Pop(S, q);          //退栈
    //             cout<<q->data;      //访问根结点
    //             p = q->rchild;      //遍历右子树
    //         }
    //     }
    // }
    
    //19、后序遍历二叉树
    void PostOrderTraverse(BiTree T)
    {
        //后序遍历二叉树T的递归算法
        if(T)                               //若二叉树非空 
        {
        
            PostOrderTraverse(T->lchild);     //中序遍历左子树 
            PostOrderTraverse(T->rchild);     //中序遍历右子树
            cout<<T->data;                  //访问根结点 
        }
    }
    
    // //20
    // LevelOrderTraverse(T)
    
    //21、复制二叉树
    void Copy(BiTree T, BiTree &NewT)
    {
        //先序遍历复制一棵和T完全相同的二叉树
        if(T == NULL)
        {
        
            NewT = NULL;
            return;
        }
        else
        {
        
            NewT = new BiTNode;
            NewT->data = T->data;
            Copy(T->lchild, NewT->lchild);
            Copy(T->rchild, NewT->rchild);
        }
    }
    
    //22、二叉树深度
    int Depth(BiTree T) 
    {
        //后序遍历计算二叉树深度
        if(T == NULL)
            return 0;
        else
        {
        
            int m = Depth(T->lchild);
            int n = Depth(T->rchild);
            if(m > n)
                return (m + 1);
            else
                return (n + 1);
        }
    }
    
    //23、二叉树结点个数
    int NodeCount(BiTree T)
    {
        //统计二叉树T中的结点个数
        if(T == NULL)
            return 0;
        else
            return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }
    //24、二叉树叶子结点个数
    void LeavesCount(BiTree T)
    {
        
        if(T)
        {
        
            if(!T->lchild && !T->rchild)
                cnt++;
            LeavesCount (T->lchild);
            LeavesCount (T->rchild);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/efbd5da32ca6400ba4dcff22574981ca.png
[20200818092420325.png_pic]: https://img-blog.csdnimg.cn/20200818092420325.png#pic
[20200818205020291.png_pic]: https://img-blog.csdnimg.cn/20200818205020291.png#pic
[2020081809234145.png_pic]: https://img-blog.csdnimg.cn/2020081809234145.png#pic
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic]: /images/20221124/a67aa1a7da314c7684ac28b2b271855e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/294817043b2143cea63aad749096981b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/c3123007239342a387de6ca1d852c902.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/4e2ae6f8d2014e509d7e3fba70d94797.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/f0ed05d43af443fa9b8001fadf7b1268.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221124/194a56bead13491d8f2d65418e93f9f5.png