数据结构二叉树的先序中序后序遍历(数据结构二叉树的遍历算法)

导语：数据结构 --- 二叉树

数据结构 --- 二叉树

首先我们来定义什么是树，计算机里的树是指n(n>=0)个节点的有限集合，而节点之间存在层次关系。当树中没有任何节点，即n=0时，这颗树称为空树。对于一颗非空树：

每个元素称为一个节点。一棵树只有一个根节点（没有父节点的节点）。除根节点之外，其余元素被分为m(m>=0)个互不相交的集合。每个集合可以被称为原树的子树。每个节点有0个或多个子节点。没有子节点的节点称为叶子节点。非父节点有且只有一个父节点。

下图展示了一颗树：

二叉树

上图中A是根节点， E,F,I,G,H为叶子节点。每一红色虚线框内的可以看做是一颗子树(图中还有其它子树，你能找出来吗)。而绿色框内的却不是子树，能看出区别吗？

关于树的一些概念：

节点的度：一个节点含有的子节点的个数称为该节点的度。

父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点。

树的度：一棵树中，最大的节点的度称为树的度。

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。

树的高度或深度：树中节点的最大层次。

无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树。

有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树。

二叉树：每个节点最多含有两个子树的树称为二叉树。

上面在树的一些概念中我们定义了二叉树的概念“每个节点最多含有两个子树的树称为二叉树”。根据这个概念，你能判断下图中哪些是二叉树吗？

哪些是二叉树？

二叉树的特点：

1). 每个节点最多有两个子节点（即每个节点的度最大为2）。

2). 二叉树第i层最多有2^(i-1)个节点。

3). 深度为k的二叉树最多拥有2^k – 1个节点。

4). 若任何一颗二叉树的叶节点数量N0，度为2的节点数量为N2，那么N0=N2+1

二叉树的分类：

完美二叉树(也叫满二叉树)

一颗深度为k(k >=0)， 并且其总共节点个数为2^k – 1的二叉树即为一颗完美二叉树，或者叫满二叉树。如上图中的A, B, E, J。

一颗深度为k完美二叉树/满二叉树 的性质：

并且其总共节点个数为2^k – 1。节点个数一定为奇数。第i层共有2^(i-1)个节点。共有2^(k-1)个叶子节点。完全二叉树

在一颗二叉树中，如果除了最后一层元素外，其它层都是满的， 并且最后一层要么是满的，要么缺少右边连续个若干节点。那么这颗二叉树就被称为完全二叉树。如上图中的 A, B, C, E, F, G , J。完全二叉树的性质：

树的深度为log2n + 1。深度为k的完全二叉树至少有2^(k-1)个节点，最多有2^k – 1个节点。满二叉树是一颗完全二叉树

本文内容由小畅整理编辑！