C++实现链表存储二叉树

Dear 丶 2023-07-18 11:23 15阅读 0赞

前言：国内很多教材，讲完二叉树的结构，就直接开始讲二叉树的遍历，我就觉得很奇怪，你连个完整的二叉树都没创建，遍历什么，于是我写了下面这篇文章，详细介绍了创建过程，然后再说遍历，循序渐进

# 1.什么是二叉树？什么是完美二叉树和完全二叉树？ #

直接上图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]  
可以看到，图中的**根结点拥有左右两个结点**，同时左右两个结点，**又是一棵独立的、互不相交的树**，**分别称为左子树、右子树**，这就是二叉树名字的由来

*  **完美二叉树**：又称满二叉树，上图就是一棵完美二叉树，**所有分支结点都存在左子树和右子树**，**并且所有叶子(无子树的结点)都在同一层上。直观感觉整棵树都是满的**

*  **完全二叉树**：如果**编号为i的结点与同样深度的满二叉树中编号i的结点位置一样**，则这棵二叉树称为完全二叉树 ，其实就是满二叉树少了某个部分，如下  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]

由于当空结点很多时，**二叉树的顺序存储结构**会造成空间浪费，一般**只适用于满二叉树**，所以通常使用**链表**来存储二叉树，这种链表称**二叉链表**

# 2.二叉链表的结点结构定义 #

typedef int ElemntType;
    struct Bintree_Node
    {
        
    ElementType data;//数据域
    Bintree_Node* left;//左子树指针
    Bintree_Node* right;//右子树指针
    }

# 3.创建一个二叉链表 #

void Create(Bintree_Node** p)//形参为指针的指针，那么*p就是传入的指针
    {
        
        ElementType temp;
        cout<<"请输入数据";
        cin>>temp;
        if(temp==0)//这里我们用'0'来指示创建一个空结点，对于不同的数据，这个标识可以任意设置
        {
        
          *p=Null;
        }
        else
       	{
        
          *p=new Bintree_Node;//如果不空，就创建一个节点
          (*p)->data=temp;//存入数据，注意要用(*p)，因为->的优先级比*高
          Create(&(*p)->left);//递归创建左结点，实参是左指针的地址
          Create(&(*p)->right);
        }
    }
    void main()
    {
        
    	Bintree_Node* P = NULL;
    	Create(&P);
    }

假设创建一个3层，共7个结点的二叉树。根结点中存放数据为10，第二层两个结点都为5，第三层的三个结点分别存1、2、3、4，示意图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 2]  
(圆圈中的为存储的数据，同时把结点从上到下，从左到右，依次编号)

从键盘输入如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 3]  
你一定会很好奇，为什么是这样的输入，才能创建这样一个二叉树

# 4.创建的具体过程分析 #

*  首先输入10，判断不为空，**然后创建一个根结点**，把10存进根结点的data中，**此时\*p指向根结点(A)**
 *  然后输入5，判断不为空，**取根结点中的left指针的地址**传给Create函数，运行Create(&(\*p)->left)，**创建第二层的B结点**，并把数据存入，**此时\*p指向的是B结点**
 *  然后输入1，判断不为空，**取B结点中的left指针的地址**，继续递归运行Create(&(\*p)->left)，**创建第三层的D结点**，并把数据存入，**此时\*p指向的是D结点**
 *  然后输入0，判断为空，即D结点的左子树为空
 *  然后输入0，判断为空，即D结点的右子树为空
 *  然后输入2，判断不为空，**取B结点中的right指针的地址**，继续递归运行Create(&(\*p)->left)，**创建第三层的E结点**，并把数据存入，**此时\*p指向的是E结点**
 *  然后输入0，判断为空，即E结点的左子树为空
 *  然后输入0，判断为空，即E结点的右子树为空  
    至此，左半边的树，就创建完成了，右边也是同理，**总之整个创建顺序是ABDECFG**

其实整个创建顺序，与后面要说的二叉树的三种遍历方式中的先序遍历是一样的，关于二叉树的遍历请看[C++详解 二叉树的三种遍历方式][C_]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]: /images/20230528/b30e807212274888b4eede37b0e7c43d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]: /images/20230528/fa102643a43b44458a94e9d00a98a24f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 2]: /images/20230528/03be2fa8de7d4fc5805fb042fb86ca85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 3]: /images/20230528/72e0b9facaf84dfd9dca98e002f75418.png
[C_]: https://blog.csdn.net/weixin_43335392/article/details/105152511