c++ || 详解二叉树_c++二叉树

树的定义

树(Tree)是n(n≥0）个结点的有限集。n=O时称为空树。
在任意一棵非空树中:
(1)有且仅有一个特定的称为根( Root)的结点;
(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree )

1）n>0时，根节点是唯一的
2）m>0时，子树的个数没有限制，但是子树一定是互不相交的

• 结点分类

1. 结点拥有的子树数称为结点的度（Degree），度为0的结点称为叶节点或终端节点，度不为0的结点称为非终端结点或分支节点（内部节点）。
2. 树的度是树内各节点的度的最大值
   
   结点关系
   

树的存储结构

1. 双亲表示法
   每个结点中，附设一个指示器指向其双亲结点到链表中的位置
   

data：数据域，存储结点的数据信息
parent：指针域，存储该结点的双亲在数组中的下标

2. 孩子表示法

每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们吧这种方法叫做多重链表表示法

方案1：指针域的个数等于树的度。
如果树中各结点的度相差很大时，是很浪费空间的，有很多的结点，指针域都是空的，但是当各结点的度相差很小时，那就意味开辟的空间被充分的利用
方案2：每个结点的指针域的个数等于该结点的度，专门取一个位置存储结点指针域的个数
克服浪费空间的缺点，对空间的利用率提高，但是由于各结点的链表是不同的结构，还需要维护结点度的数值，带来了时间上的损耗
- 孩子表示法： 每个结点的孩子结点排列起来，以单链表做存储结构，则n个结点有n个孩子链表，叶子结点则表示该单链表为空，然后n个头指针组成一个线性表，采用顺序存储结构，存放进一维数组中

3. 孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此设计两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

二叉树

1. 定义： 是n个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树构成。

满足两个条件：

1. 本身是有序树
2. 树中包含的各个结点的度不能超过2，只能是0,1,2

二叉树的性质

1. 二叉树中，第i层最多有2^i-1个结点
2. 如果二叉树的深度为k，那么此二叉树最多有2^k-1个结点
3. 二叉树中，终端结点数（叶子结点数）为n0,度为2的结点数为n2,则n0=n2+1
4. 

满二叉树

二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树

• 满二叉树的性质
  1.满二叉树中第 i 层的节点数为 2^(i-1) 个。
  2.深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子数为 2^k-1。
  3.满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
  4.具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树

• 满二叉树一定是完全二叉树，但完全二叉树不一定是满的

完全二叉树从右向左依次标号，对于任意结点i来说：

1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i
3. 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1

二叉树的存储结构

顺序存储、链式存储

二叉树的顺序存储

使用顺序表(数组)存储二叉树，顺序存储只适用于完全二叉树，如果想顺序存储普通二叉树，则需要提前将普通二叉树转化为完全二叉树

完全二叉树的顺序存储仅需从根结点开始，按照层次依次将树中结点存储到数组即可

若结点i有左右孩子，则其左孩子结点为2i，右孩子结点为2i+1

二叉树的链式存储

顺序存储二叉树，如果是普通二叉树会造成空间浪费的现象。

结点结构：

• 指向左孩子结点的指针（Lchild）
• 结点存储的数据（data）
• 指向右孩子结点的指针（Rchild）
  

typedef struct BiTNode
{
   
	ElemType data;
	BiTNode* Lchild; //左孩子
	BiTNode* Rchild; //右孩子
}BiTNode,*BiTree;
1
2
3
4
5
6
7

二叉树的建立

将二叉树的每个结点的空指针引出一个虚结点，它的值是特定值，比如‘#’，称这种处理后的二叉树为原二叉树的扩展二叉树。

 //递归建立
void CreateBiTree(BiTree* T) //AB#D##C##扩展二叉树
{
   
	ElemType ch;
	cin >> ch;
	if (ch == '#')
		*T = NULL;
	else {
   
		*</
1
2
3
4
5
6
7
8
9
10