黑客必知：数据结构中的树、二叉树和树的遍历是什么？

一、树（Tree）：

树的概念 n（n≥0）个结点构成的有限集合。当n=0时，称为“空树”。

树的相关概念

结点的度（Degree）：结点的子树个数；

树的度：树的所有结点中最大的度数；

叶结点（Leaf）：度为0的结点；

父结点（Parent）：有子树的结点是其子树的根节点的父结点；

子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；

兄弟结点（Sibling）：具有同一个父结点的各结点彼此是兄弟结点；

路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；

祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；

子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；

结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；

树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；

二、二叉树

二叉树T：一个有穷的结点集合。这个集合可以为空；若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。二叉树的子树有左右顺序之分。

下面我们介绍一下满二叉树和完全二叉树的概念和性质。

满二叉树

除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。

完全二叉树

有n个结点的二叉树，对树中结点从上至下、从左到右顺序进行编号，编号为i（1≤i≤n）结点与满二叉树中编号为i结点在二叉树中的位置相同。

二叉树的性质

一个二叉树第i层的最大结点数为：2i-1，i≥1；

深度为k的二叉树有最大结点总数为：2k-1，k≥1；

对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者满足关系：n0=n2+1；

三、树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。二叉树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。