二叉树的基本实现

我学习数据结构之余总结的第三篇文章,力求不概念化,文字通俗易懂。主要会说到三种二叉树:一般二叉树、满二叉树、完全二叉树。如果这些你都知道下面的文章可以不用看。

一般二叉树

图中左边是普通树(左边只是一般树),具备树的结构。而右边是才是一般二叉树,上面这幅图是将一颗普通树转换为一颗一般二叉树,转化的具体规则是:节点的左指针域指向它的第一个孩子节点,右指针指向它的兄弟节点,只要满足此条件,就可以把普通树转换为一般二叉树。

从图中的一般二叉树我们可以得到一些东西,二叉树只有一个根节点,当然这是树的共同点,但是可以看到,二叉树任意一个子节点个数最多只有两个,如果超过,它就不是一颗二叉树了,而是普通树。

下面是每个节点的基本结构:

typedef char ElemType;
// 每个子树的基本结构struct
typedef struct BinNode {
    ElemType data; // 存在数据
    struct BinNode * pLeft;  // 左子树
    struct BinNode * pRight; // 右子树
}BinNode, *BinTree

满二叉树和完全二叉树

满二叉树:在不增加树的层数的前提下,无法再多添加一个节点的二叉树就是满二叉树

完全二叉树:如果只是删除满二叉树最右边的连续若干节点,这样形成的二叉树就是完全二叉树;

生成二叉树的代码参考链接:tree 创建和遍历

更多内容可以参考我个人学习项目C语言数据结构

ps: 微信公众号:Yopai,有兴趣的可以关注,每周不定期更新。不断分享,不断进步

上次更新: 7/25/2020, 9:20:49 AM

评 论: