数据结构之二叉树基本概念_二叉树是树形结构的一个重要类型,许多实际问题抽象出来的数据结构往往是二叉树形

二叉树的基本概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分
_{来自百度词条}

二叉树的基本形态：

1.空的二叉树：

其实就是指向空的指针

2.只有根节点的二叉树：

也就是一个指针指向一个节点，这个节点是根节点

3.只有左子树和右子树：

只有左子树和右子树（又称斜树，其实也就成了链表）：如下图：

4.完全二叉树

这个怎么说，如果对每个结点按照层序编号，然后按照从上到下，从左到右依次编号，编号时不跳过空结点。二叉树可能有的结点只有一个孩子，不是最后一层也可能出现叶子结点，但是我们编号的时候不跳过，始终按照左孩子 -> 右孩子的顺序去编号，如果发现某个编号处位置空缺，这棵树就不是完全二叉树。举几个例子

树1的结点5，按编号顺序它的左孩子应该编号10，右孩子11，但它没有左孩子，位置10就空缺了，所以不是完全二叉树；树2中第二层的结点3的两个孩子应分别编号6和7的，然后是下一层的8和9，但是由于结点3没有孩子，所以造成位置6、7空缺，也不是完全二叉树。树3也是不是完全二叉树，结点5的孩子应编号为10和11，然后是结点6的孩子编号为12，但是结点5没有孩子，造成了位置10、11空缺。

5.满二叉树

如果二叉树中所有的非叶子结点都有左孩子和右孩子，而且叶子结点位于同一层。我们称这样的树为满二叉树。如下

这个很好理解

二叉树的相关知识点

1.孩子节点：

结点子树的根结点为该结点的孩子结点。

2.双亲节点：

相应该结点称为孩子结点的双亲结点。

3.兄弟节点：

同一个双亲结点的孩子结点之间互称兄弟结点。

4.有序树：

如果树中各棵子树的次序是有先后次序，则称该树为有序树

5.无序树：

如果树中各棵子树的次序没有先后次序，则称该树为无序树
（当然百度百科最好，我毕竟是个小白）

树的遍历：

下面我以这个图为例：

前序遍历：

前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

中序遍历：

中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

后序遍历：

后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

结论

可以看到我的图里面标记的， 只要记住根的位置就行，也就是遍历的名称

层次遍历

也就是按照树的层来遍历，这个过于简单，不去详述。

---

好了关于树的基本概念，我的笔记也就到这里了，下一个博客用C语言实现这个数据结构（链表二叉树）