树和二叉树---概念

https://cloud.tencent.com/developer/article/2464457?shareByChannel=link 作者：池央

文章介绍了类和对象的概念，解析了类的特性、类的语法、如何定义类，通过这篇文章可以学习、了解C++中的类和对象。

一、树的概念和结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

（1）有一个特殊的结点，称为根结点，根节点没有前驱结点。

（2）除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

（3）因此，树是递归定义的。

注意：任何一棵树都由根和子树两部分构成，子树又由根和子树构成。叶子是没有子树的子树。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。如：

1.2树的相关概念

（1）节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6。

（2）叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点。

（3）非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点。

（4）双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：J是P的父节点。

（5）孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：P是J的子节点。

（6）兄弟节点：具有相同父节点的节点互称为兄弟节点（亲兄弟）； 如上图：B、C是兄弟节点。

（7）树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6。

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

对于节点的层次，也可以规定根为第0层。

（9）树的高度或深度：树中节点的最大层次； 如上图：树的高度为4。

（10）堂兄弟节点：双亲在同一层的节点互为堂兄弟（在同一层，不是亲兄弟就是堂兄弟）；如上图：H、I互为堂兄弟节点。

（11）节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先。

（12）子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。

（13）森林：由m（m>0）棵互不相交的树的集合称为森林。

1.3树的表示

实际中树有许多表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里我们简单介绍其中最常用的孩子兄弟表示法。

typedef int DataType;

struct TreeNode

{

struct TreeNode* firstChild1;//指向第一个孩子节点

struct TreeNode* pNextBrother;//指向其下一个兄弟节点

DataType data;//结点中的数据域

};

一个结点不管它有几个孩子，它只指向左边第一个孩子，若它没有孩子，则指向空；结点的兄弟指针指向这个结点的右边第一个兄弟结点（注意不是堂兄弟节点，是亲兄弟结点（父亲是同一个）），若没有兄弟，则指向空。这样可以先找到左边第一个孩子，剩下的孩子通过兄弟指针去遍历，就像遍历链表那样。

二、二叉树的概念和结构

2.1二叉树的概念

二叉树是一种特殊的树。二叉树的每个结点的度不大于2，二叉树的每个节点的度可以是0,1,2，但是不能超过2。二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。二叉树的左子树称为左孩子，右子树称为右孩子。

对于任意的二叉树都是由以下几种情况复合而成的：

2.2特殊的二叉树

1.满二叉树

简单来说，满二叉树是除最后一层的结点度为0之外，其余层的所有结点度都为2的二叉树。

我们假设一棵满二叉树的高度为h（规定根为第一层），那么这棵满二叉树的结点个数是多少呢？由于满二叉树除叶结点外，每个结点均有两个孩子，所以满二叉树的第k层就有2^(k-1)个结点，根据等比数列求和公式可知，高度为h的满二叉树共有2^h-1个结点。

反过来求，我们已知一棵满二叉树的结点个数为N，那么这棵满二叉树的高度是多少呢（规定根为第一层）？我们假设这棵满二叉树的高度为h，由上面的计算，我们可以知道N=2^h-1,根据对数运算，我们可以得到，h = log(N+1)，在计算时间复杂度时，可以认为满二叉树的高度是logN。

2.完全二叉树

完全二叉树要求除最后一层外，每一层都是满的。最后一层可以是满的也可以不是满的，若最后一层不是满的，则要求从左到右必须是连续的。当最后一层是满的，则完全二叉树就是满二叉树，因此我们说满二叉树是特殊的完全二叉树。

我们假设一棵完全二叉树的高度为h（规定根为第一层），那么这棵完全二叉树的结点个数的范围是从哪里到哪里呢？

由上面的计算可以知道，高度为h的满二叉树的结点个数为2^h - 1，又因为满二叉树是完全二叉树结点数目最多的情形，所以我们可以知道高度为h的完全二叉树结点最多是2^h - 1个。从完全二叉树的性质特点，我们可以知道一棵完全二叉树结点数目最少的情况是只有一个叶子结点的时候，则此时完全二叉树的结点个数 = 前h-1层的结点个数 + 1（最后一层是1个），即2^(h-1) -1 + 1个。所以高度为h的完全二叉树的节点个数的范围是[2^(h-1)，2^h - 1]。

反过来求，已知一棵完全二叉树的节点个数为N，求这棵完全二叉树的高度范围（规定根为第一层）。

根据上面求的完全二叉树的结点个数范围和对数运算的知识，我们可以求得高度范围为[logN + 1，log(N+1)]。当计算时间复杂度时，可以认为高度为logN。

2.3二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1.顺序存储

顺序结构存储就是使用数组来存储。将二叉树的数据放到数组中，则父子结点的下标有如下关系：

已知孩子结点的下标child，则其父节点的下标为parent = (child - 1) / 2;

已知父节点的下标parent，则其左孩子的下标为child = parent*2 + 1，其右孩子的下标为child = parent*2 + 2。

由于下标关系固定好了，所以数组只适合存储完全二叉树，不适合存储其他二叉树（存储其它二叉树会有空间浪费。）。​​​​​​​现实中使用中只有堆才会使用数组来存储。

2.链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树。 通常的方法是链表中每个结点有两个指针和当前节点存储的数据，两个指针一个存储左孩子结点的地址，一个存储右孩子节点的地址。

邀请人：池央