【数据结构】二叉树的基本概念

1.树概念及结构

1.1树的概念

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

子树不能有交集，就是不能有闭环.N个节点两个一条边，所以是N-1个边，父节点的概念在下面讲.

1.2 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

这里父节点只保存第一个孩子的节点，别的孩子由第一个孩子指向，这里c节点也是a的孩子，但是他是由a的第一个孩子b指向的.

2.二叉树概念及结构

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
   

3. 二叉树不存在度大于2的结点//就是不超过两个孩子

4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
   
   这也是个满二叉树，什么是满二叉树呢？

2.3 特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2的k次方 -1，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
   
   
   完全二叉树是连续的，不存在上图情况

2.4 二叉树的性质

2.等比数列求和
首项为a1=1，公比为q=2，等比数列求和公式Sn=a1(1-q^n)/(1-q),这里的n取h(深度)
3.

4.根据第二条2^h-1=n
n+1=2^h;
可得第四条

3.二叉树基础计算题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
   A 不存在这样的二叉树
   B 200
   C 198
   D 199
   解析：叶子结点数为度为0的结点数，根据第三条性质，选择b.
2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
   A n
   B n+1
   C n-1
   D n/2
   解析：二叉树不存在度大于2的，所以度只有0,1，2，分别记度为0,1，2的结点数目为n0,n1,n2;
   n0+n1+n2=2n;n为总结点数，n0=n2+1;度为1的只可能是0,1，因为这个是完全二叉树，有顺序的，不可能出现下图这样

2n0-1+n1=2n;2n0为偶数，2n为偶数，则n1只能取1，则n0=n;选a;
3. 一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
假设树的高度为h,则树的节点范围是最后一行只有一个到最后一行全满，就是2^(h-1)-1+1到全满2的h次方减1；
分别带人选项，选择b.
4. 一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
解析：n0+n1+n2=767;
2n0-1+n1=767
2n0-1为奇数，767为奇数，又因为是完全二叉树，所以n1=0;n0=384,选b;

4. 二叉树的存储结构

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

1. 顺序存储
   顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
   
2. 链式存储
   二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链.