数据结构-二叉树的基本实现

作者：HerryLo (opens new window)

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

一般二叉树

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

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

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

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

满二叉树和完全二叉树

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

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

生成二叉树的代码参考链接：tree 创建和遍历 (opens new window)

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

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