前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构 第11讲 二叉树及其创建

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

作者头像
rainchxy
发布2018-09-13 16:04:26
6130
发布2018-09-13 16:04:26
举报
文章被收录于专栏:趣学算法

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

二叉树(Binary Tree)是nn≥0)个结点所构成的集合,它或为空树(n = 0);或为非空树,对于非空树T

(1)有且仅有一个称之为根的结点;

(2)除根结点以外的其余结点分为两个互不相交的子集T1和T2,分别称为T的左子树和右子树,且T1和T2本身又都是二叉树。

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

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

结点结构体的定义:

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

如何创建一棵二叉树呢?

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

(1)输入结点信息,创建一个结点T;

(2)询问是否创建T的左子树,如果是,则创建其左子树,否则其左子树为NULL;

(3)询问是否创建T的右子树,如果是,则创建其右子树,否则其右子树为NULL。

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

请输入结点信息:

A

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

Y

请输入结点信息:

B

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

Y

请输入结点信息:

D

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

N

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

N

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

Y

请输入结点信息:

E

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

N

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

N

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

Y

请输入结点信息:

C

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

Y

请输入结点信息:

F

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

N

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

Y

请输入结点信息:

G

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

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

N

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

N

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

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

N

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

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年11月08日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档