数据结构之初阶二叉树

要努力，但不要急。繁花锦簇，硕果累累都需要过程！

 

目录

前言：

1.树

1.树的概念：

2.树的相关概念：

3.树的表示：

4.小结：

2.二叉树

1.概念：

2.特殊的二叉树：

3.二叉树的性质：

4.二叉树的存储结构：

5.二叉树链式结构的实现：

6.二叉树的应用结构：堆

1.堆的概念和结构：

2.堆的实现：

3.堆排序

3.二叉树的oj面试题：

---

前言：

树是一种在数据结构中经典的非线性结构，在实际应用中非常普遍，例如文件的层级就是一种树形结构，每一个根之下对应许多的子文件，下面我们一一来剖析树的概念：

1.树

1.树的概念：

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

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

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

树是递归定义的

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

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）棵互不相交的树的集合称为森林；

3.树的表示：

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间 的关系

1.第一种表示方法：

 缺点：在实际的过程中并不能确定树的度是多少

2.第二种表示方法：顺序表存储

 3.第三种表示方法：链表存储

父亲指向第一个孩子，孩子之间用兄弟指针链接起来 

4.小结：

以上就是关于一些树的基本概念，现阶段不进行深入研究，下面我们来看树的一种特殊结构，二叉树。

2.二叉树

1.概念：

一颗二叉树是结点的一个有限集合，该集合为空或者一个根结点由左子树和右子树组成

1.二叉树不存在度大于2的结点

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

现实中的二叉树：

 所有的二叉树都是一下几种情况组成的：

2.特殊的二叉树：

1 . 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是2^(K)-1 ，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

 结点数范围：[2^(k-1),2^(k)-1]

3.二叉树的性质：

1 . 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1

3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n1 ,则有

n0 ＝n2 ＋ 1(度为0的结点个数总是比度为2的结点多一)

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度， h= log(n+1). (ps：log(n+1)) 是log以2为底， n+1为对数)

4.二叉树的存储结构：

1.顺序存储：

顺序存储的结构一般是采用数组来存储的，对于完全二叉树一般采用数组存储，但是对于普通二叉树采用数组存储会浪费许多的空间，所以普通的二叉树一般采用的存储结构进行存储

图解：

2.链式存储

图解：

5.二叉树链式结构的实现：

1.二叉树结构的简单创建：

 2.二叉树的遍历：

 前序遍历：访问根结点的操作发生在遍历其左右子树之前（根，左子树，右子树）

 递归详图分解：

 

中序遍历：访问根结点的操作发生在遍历其左右子树之中（间）。（左子树，根，右子树）

 

后序遍历：访问根结点的操作发生在遍历其左右子树之后。（左子树，根，右子树）

  

 层序遍历：设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现方式：构建一个队列，上一层结点出的时候带入下一层

 

3.求二叉树结点个数：

 4.求叶子节点的个数：

 5.求树的高度：

6.求第K层结点的个数：

 7.返回x所在的结点：

8.销毁二叉树：

 9.判断一个树是否是完全二叉树：

思路：采用层序遍历的方式，遇到空之后，如果后边还存在空，则不是完全二叉树：

 

6.二叉树的应用结构：堆

1.堆的概念和结构：

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： 且 = 且 >= ) i = 0， 1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2.堆总是一颗完全二叉树；

堆的图解：

1.小堆：所有孩子结点的值大于等于父亲结点的值

逻辑结构：

物理结构：

 2.大堆：所有孩子的值小于等于父亲的值：

逻辑结构：

物理结构：

 数组下标计算父子之间的关系：

leftChild = parent*2+1;

rightChild = parent*2+2;

parent = (child-1)/2;

2.堆的实现：

例：实现小堆：用数组实现

1.创建结构体：

2.堆的初始化：

void HeapInit(HP* php); 

 3.插入数据并保持堆形态：
void HeapPush(HP* php, HpDataType x);

思路：将数据插入数组的最后一个位置，然后通过最后一个位置的下标计算出父亲的值进行比较，如果孩子的值比父亲的值小就交换，直到孩子的值比父亲的值大(小堆)

4.删除堆顶的数据：
void HeapPop(HP* php); 

思路：将第一个数据和最后一个数据交换，然后size--,交换上去的数据如果比孩子的值大，为了保持堆形态，就向下调整直到父亲的值比孩子的值小。

5.获取堆顶的元素：
HpDataType HeapTop(HP* php); 

6.判断堆是否为空：
bool HeapEmpty(HP* php); 

7.获取堆上元素的个数：
int HeapSize(HP* php); 

8.堆的打印：
void HeapPrint(HP* php); 

9.堆销毁：
void HeapDestroy(HP* php); 

3.堆排序

1.建堆：

第一种方案：向上调整建堆

 

第二种方案：向下调整建堆

方法：从倒数第一个非叶子结点（最后一个结点的父亲）开始向下调整建堆，直到调整到根

 

在堆排序的时候既可以采用向上调整建堆，也可以采用向下调整建堆，但是相互比较下向下调整建堆时间复杂度比向上调整建堆低，所以采用向下调整建堆

2.排序：

思路：升序排序的时候采用建大堆的方式，降序排序的时候采用建小堆的方式。

原因：当建好堆之后，采用向下调整的方式，将排序的复杂度优化到O(N*logN)

例：降序：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		if (minChild + 1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}
		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int sz)
{
	//向下调整建堆：
	int i = 0;
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	i = 1;
	while (i < sz)
	{
		Swap(&arr[0], &arr[sz - i]);
		AdjustDown(arr, sz - i, 0);
		i++;
	}
}
int main()
{
	int arr[] = { 32,56,79,45,57,100,67,78 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

TOP-K问题：

即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

解决思路：

1.用数据集合中前k个元素建堆：

求K个最大的元素，建立小堆；

求K个最小的元素，建立大堆；

2.遍历剩余的N-K个元素，不满足就交换：最后在堆中的元素就是最大或者是最小的K个元素

时间复杂度为O(N)  空间复杂度为O(K)

例：找出文件中前10个最大的数据：

3.二叉树的oj面试题：

题目1：

1.单值二叉树：oj链接

题目描述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;
    if(root->left != NULL && root->val != root->left->val)
        return false;
    if(root->right != NULL && root->val != root->right->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

题目二：

2.检查两颗树是否相同：oj链接

题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p == NULL && q == NULL)
        return true;
    if(p == NULL || q == NULL)
        return false;
    if(p->val != q->val)
        return false;
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

题目三：

3.对称二叉树：oj链接

题目描述：给你一个二叉树的根节点 root ， 检查它是否轴对称。

bool isSameTree(struct TreeNode* left, struct TreeNode* right){
    if(left == NULL && right == NULL)
        return true;
    if(left == NULL || right == NULL || left->val != right->val)
        return false;
    return isSameTree(left->left,right->right) && isSameTree(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root){
    if(root == NULL)
        return true;
    return isSameTree(root->left,root->right);  
}

题目四：

4.二叉树的前序遍历：oj链接

题目描述:给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

int TreeSize(struct TreeNode* root){
    if(root == NULL)
        return 0;
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root,int*a,int* pos){
    if(root == NULL)
        return;
    a[*pos] = root->val;
    (*pos)++;
    preorder(root->left,a,pos);
    preorder(root->right,a,pos);
 
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //求结点的个数：
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int)*n);
    *returnSize = n;
    int pos = 0;
    //前序遍历：
    preorder(root,a,&pos);
    return a;
}

题目五：

5.另一棵树的子树：oj链接

题目描述：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p == NULL && q == NULL)
        return true;
    if(p == NULL || q == NULL)
        return false;
    if(p->val != q->val)
        return false;
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;
    if(isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

题目六：

6.二叉树的构建和遍历：oj链接

题目描述：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

#include<stdio.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
   if(a[*pi] == '#')
   {
       (*pi)++;
       return NULL;
   }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if(root == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    root->data = a[*pi];
    (*pi)++;
    root->left = BinaryTreeCreate(a,pi);
    root->right = BinaryTreeCreate(a,pi);
    return root;
}
void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main()
{
    char str[100];
    scanf("%s",str);
    //前序构建树：
    int i = 0;
    BTNode* root = BinaryTreeCreate(str,&i);
    //中序遍历打印：
    InOrder(root);
    return 0;
}