数据结构之初阶二叉树

发布于:2023-01-20 ⋅ 阅读:(12) ⋅ 点赞:(0) ⋅ 评论:(0)

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

 

目录

前言:

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;
}


网站公告

欢迎关注微信公众号

今日签到

点亮在社区的每一天
签到