数据结构第11讲二叉树及其创建

男娘i 2022-06-05 20:09 50阅读 0赞

**数据结构第11讲二叉树及其创建**

二叉树（Binary Tree）是*n*（*n*≥0）个结点所构成的集合，它或为空树（*n* = 0）；或为非空树，对于非空树*T*：

（1）有且仅有一个称之为根的结点；

（2）除根结点以外的其余结点分为两个互不相交的子集*T*1和*T*2，分别称为*T*的左子树和右子树，且*T*1和*T*2本身又都是二叉树。

也就是说，二叉树最多有两个"叉"，即最多有两个子树。如图1所示：

![Center][]

二叉树一般采用链式存储方式：每个结点包含两个指针域，指向两个孩子结点，还包含一个数据域，存储结点信息。如图2所示。

![Center 1][]

**结点结构体的定义：**

![Center 2][]

那么图1中的二叉树就可以存储为二叉链表的形式，如图3所示：

![Center 3][]

如何创建一棵二叉树呢？

我们从二叉树的定义就可以看出，它是递归的方式定义的（除了根之外，左/右子树也是一棵二叉树），因此也可以用递归程序来创建二叉树。

（1）输入结点信息，创建一个结点T；

（2）询问是否创建T的左子树，如果是，则创建其左子树，否则其左子树为NULL；

（3）询问是否创建T的右子树，如果是，则创建其右子树，否则其右子树为NULL。

下面展示图1二叉树的创建过程：

**请输入结点信息:**

**A**

![Center 4][]

**是否添加 A的左孩子? (Y/N)**

**Y**

**请输入结点信息:**

**B**

![Center 5][]

**是否添加 B的左孩子? (Y/N)**

**Y**

**请输入结点信息:**

**D**

![Center 6][]

**是否添加 D的左孩子? (Y/N)**

**N**

**是否添加D的右孩子? (Y/N)**

**N**

![Center 7][]

**是否添加B的右孩子? (Y/N)**

**Y**

**请输入结点信息:**

**E**

![Center 8][]

**是否添加 E的左孩子? (Y/N)**

**N**

**是否添加E的右孩子? (Y/N)**

**N**

![Center 9][]

**是否添加A的右孩子? (Y/N)**

**Y**

**请输入结点信息:**

**C**

![Center 10][]

**是否添加 C的左孩子? (Y/N)**

**Y**

**请输入结点信息:**

**F**

![Center 11][]

**是否添加 F的左孩子? (Y/N)**

**N**

**是否添加F的右孩子? (Y/N)**

**Y**

**请输入结点信息:**

**G**

输入后F的左孩子为空，右孩子创建了一个结点G如图12所示。

![Center 12][]

**是否添加 G的左孩子? (Y/N)**

**N**

**是否添加G的右孩子? (Y/N)**

**N**

输入后G左右孩子均为空如图13所示。

![Center 13][]

**是否添加C的右孩子? (Y/N)**

**N**

输入后G左右孩子均为空如图14所示。

![Center 14][]

#include <iostream>
    
    using namespace std;
    
    typedef struct Bnode	/*定义二叉树存储结构*/
    { char data;
      struct Bnode *lchild,*rchild;
    }Bnode,*Btree;
    
    void createtree(Btree &T)	/*创建二叉树函数*/
    {
        char check;					/*判断是否创建左右孩子*/
        T=new Bnode;
        cout<<"请输入结点信息:"<<endl;	/*输入根结点数据*/
        cin>>T->data;
        cout<<"是否添加 "<<T->data<<"的左孩子? (Y/N)"<<endl; /*询问是否创建T的左子树*/
        cin>>check;
        if(check=='Y')
            createtree(T->lchild);
        else
            T->lchild=NULL;
        cout<<"是否添加"<<T->data<<"的右孩子? (Y/N)"<<endl; /*询问是否创建T的右子树*/
        cin>>check;
        if(check=='Y')
            createtree(T->rchild);
        else
            T->rchild=NULL;
        return;
    }
    
    int main()
    {
        Btree mytree;
        createtree(mytree);/*创建二叉树*/
        return 0;
    }

[Center]: /images/20220606/75c4ff1ab5384841919fe1a8ce9e97c3.png
[Center 1]: /images/20220606/ab04298bb81f4cd3b09a244bf1d374c3.png
[Center 2]: /images/20220606/a99f420aa3e04634a68c1c515ded16c1.png
[Center 3]: /images/20220606/c001b034457f44229941e24497f9b923.png
[Center 4]: /images/20220606/c99b196ead8c4f49b119fb2cbec06729.png
[Center 5]: /images/20220606/e442e4a8242e467b839aaec29623d3d1.png
[Center 6]: /images/20220606/6a522c54ce9a4692b0ba93b0ca77bd46.png
[Center 7]: /images/20220606/fe81a2968a904d4bbca11c28cfc1656e.png
[Center 8]: /images/20220606/241ac6f0ba044e2f86ac4da216bddd17.png
[Center 9]: /images/20220606/d4336ce42c7f4579a00eb792bfeccca8.png
[Center 10]: /images/20220606/6ccc67ea7c1c4fffbbd479b3a45a9254.png
[Center 11]: /images/20220606/74579be4703942b29a34c8119fea0c56.png
[Center 12]: /images/20220606/f3a3a90a575941ebb8163fc3448d8034.png
[Center 13]: /images/20220606/9bfd8f2913d04ab7a2279f28ea62fb00.png
[Center 14]: /images/20220606/71c5e387ee8b44b99f3df704f3a94499.png