淘先锋技术网

首页 1 2 3 4 5 6 7

专栏:数据结构
个人主页:HaiFan.
专栏简介:这里是HaiFan.的数据结构专栏,今天的内容是二叉树。

树的概念及结构

树是一种非线性的数据结构,是由n个有限结点组成的具有一个层次关系的集合,把称为树是因为把它倒着看很像一颗树。

  • 有一个特殊的结点,称为根节点,根节点没有前驱结点
  • 除根结点之后,其余的结点都是互不相交的集合,每一个集合都是一颗结构与树类似的子树。
  • 树是递归定义的

在这里插入图片描述

像这样,就被称为树。

子树一旦相交,就不再叫做树,而是另一种特殊的数据结构—图

在这里插入图片描述


除此之外,树还有一些性质。

在这里插入图片描述

节点的度:一个节点含有的子树的个数称为该节点的度,如1的度为2

叶节点或终端节点:度为0的节点称为叶节点,如4,5,6,7都是叶节点

非终端节点或分支节点:度不为0的节点 ,如1,2,3

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点 ,如1是2的父节点

孩子节点或子节点:一个节点含有的子树的根节点,如2是1的孩子节点

兄弟结点:具有同一个父节点的子树,如2和3就互为兄弟结点

树的度:树最大的节点的度称为树的度,如树的度为2

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为3

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:4和6

节点的祖先:从根到该节点所经分支上的所有节点;如上图:1是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是1的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林


那么树是怎么表示的呢?

树的结构就有点复杂了,用线性表定义树的话呢,会面临一个问题:就是一个节点可能有n个子树,那么定义多少个接口来存储该节点和子树的关系呢?这个不太好解决。于是,有大佬相出了解决办法:孩子兄弟表示法,孩子表示法等等,在这里讲解一下孩子兄弟表示法。

struct Node
{
	struct Node* left_child; //左孩子
	struct Node* right_child;//右兄弟
	int data;//数据
}

就比如上图中的树,

在这里插入图片描述

这样存,不管有多少个子树,都可以存储,left存左二子,right存兄弟。


二叉树概念及结构

二叉树的概念

二叉树是一种特殊的树形结构,它有一个根节点以及每个节点最多有两个子节点(一个左孩子,一个右孩子)

性质:

  1. 因为每个节点最多两个孩子,所以二叉树的最大的度不超过2
  2. 左儿子是左儿子,右儿子是右儿子,有顺序之分
  3. 叶子节点没有子节点
  4. 每一层上的节点数目都不超过2的n - 1次方,根节点为第一层
  5. 对于深度为k的二叉树来说,最多有2的n次方-1个节点,最少有k个节点
  6. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2,则有n0 = n2 + 1
  7. 若规定根节点的层数为1,具有n个结点的满二叉树的深度**,**h= log(n + 1). (ps: 是log以2为底,n+1为对数)

特殊的二叉树

满二叉树:深度为k且有2的k次方-1个节点的二叉树称为满二叉树

完全二叉树:对于深度为k的二叉树来说,除了第k层节点从左到右连续排列外,其余层节点都连续的排列

二叉树的存储结构

提到存储结构,肯定是顺序结构和链式结构。

  1. 二叉树的顺序结构就是利用数组去存储,一般使用数组只适合完全二叉树,因为不是完全二叉树会有空间的浪费(完全二叉树会使得数组中的每一个位置都存的有元素,而非完全二叉树会造成空间的浪费,想一想为什么)

  2. 链式存储:定义一个结构体,结构体中 有两个结构体指针,一个存数据,一个指针用来指向左二子,一个指针用来指向右儿子。

    typedef char TreeDataType;
    typedef struct BinaryTreeNode
    {
    	TreeDataType val;
    	struct BinaryTreeNode* left;
    	struct BinaryTreeNode* right;
    }BTNode;
    

二叉树的顺序结构及实现

普通的二叉树不适合用数组来存储数据,因为可能会造成大量的空间浪费,而完全二叉树比较适合使用顺序结构存储。

提到完全二叉树,就不得不提到堆这一概念,堆是一个数据结构而不是管理内存的一块区域分段。

大根堆和小根堆

大根堆就是每个节点的值都大于等于父节点的值,根节点的值最大

在这里插入图片描述

小根堆就是每个节点的值都小于等于父节点的值,根节点的值最小

在这里插入图片描述

堆的实现及其各个接口

实现堆,还是结构体那一套。

typedef struct Heap
{
	int capacity;
	HeapDataType* val;
	int count;
}Heap;

void HeapInit(Heap* ps);//初始化
void HeapDestory(Heap* ps);//销毁空间

void HeapPush(Heap* ps, HeapDataType x);//入堆
void HeapPop(Heap* ps);//出堆

HeapDataType HeapTop(Heap* ps);//返回堆顶元素

int HeapSize(Heap* ps);//堆的大小
bool HeapEmpty(Heap* ps);//堆是否为空

堆的初始化和空间销毁

之前的链表,顺序表,双链表等数据结构会的话相信堆的初始化和销毁难不倒各位。

void HeapInit(Heap* ps)
{
	ps->capacity = 4;
	ps->count = 0;
	ps->val = (HeapDataType*)malloc(sizeof(HeapDataType) * ps->capacity);
}

void HeapDestory(Heap* ps)
{
	ps->capacity = ps->count = 0;
	free(ps->val);
	ps->val = NULL;
}

入堆

入堆之前要检查数组的空间是否够用,够用则直接加入数据,不够则扩容。

void HeapPush(Heap* ps, HeapDataType x)
{
	assert(ps);
	if (ps->capacity == ps->count)
	{
		ps->capacity *= 2;
		HeapDataType* tmp = (HeapDataType*)realloc(ps->val, sizeof(HeapDataType) * ps->capacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
	}

	ps->val[ps->count++] = x;
	HeapJustUp(ps->val, ps->count);
}

但是光加入数据可不行,要进行向上调整,把数据调整成小根堆或者大根堆,但是调整是有前提的,左右子树必须是一个堆,才不会导致堆内数据乱。所以我们每加入一个数据调整一次,即可做到堆是一个大堆或者小堆。


void HeapJustUp(HeapDataType* a, int n)
{
	int parent = n - 2 >> 1;
	int child = n - 1;

	while (parent >= 0)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}

		if (a[parent] < a[child])
		{
			std::swap(a[parent], a[child]);
			child = parent;
			parent = child - 1 >> 1;
		}
		else
		{
			break;
		}
	}

}

向上调整堆,要找到父亲和孩子,父亲就是元素的总个数-2之后在/2,孩子就是元素总个数-1.

因为是向上调整,父亲节点的下标会慢慢变小,所以循环条件可以设置成parent>=0,有了循环条件,还要比较左右孩子哪个大,然后在让孩子和父亲比较,最后更新父亲下标和孩子下标即可。

删除堆顶元素

删除堆顶元素就是让堆顶元素和堆底元素进行一个交换,然后元素个数-1.交换完成之后,要进行向下调整,向下调整要求左右子树是大根堆或者小根堆,在入堆这一步,我们已经完成了这个操作,所以可以直接调整。

void HeapPop(Heap* ps)
{
	assert(ps);
	assert(ps->count);

	std::swap(ps->val[0], ps->val[ps->count--]);

	HeapJustDown(ps->val, 0, ps->count);
}

那么向下调整是怎么调的呢?

因为要把堆顶元素调到下面,所以从下标为0的位置开始向下调整。

0的位置就是父亲节点,然后要找到儿子节点child = parent * 2 + 1,然后判断左右孩子哪个大,在判断父亲节点和孩子节点的大小关系,更新下标即可。

void HeapJustDown(HeapDataType* a, int parent, int n)
{
	int child = parent * 2 + 1;

	while (child <= n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}

		if (a[parent] < a[child])
		{
			std::swap(a[parent], a[child]);
			
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

返回堆顶元素

HeapDataType HeapTop(Heap* ps)
{
	assert(ps);

	return ps->val[0];
}

返回堆的大小

int HeapSize(Heap* ps)
{
	assert(ps);
	return ps->count;
}

判断堆是否为空

bool HeapEmpty(Heap* ps)
{
	assert(ps);

	return ps->count == 0;
}

二叉树的链式实现

typedef char TreeDataType;

typedef struct BinaryTreeNode
{
	TreeDataType val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* TreeInit();//初始化

BTNode* BinaryTreeCreate();//创建二叉树

void BinaryTreeDestory(BTNode* root);//销毁二叉树

int BinaryTreeSize(BTNode* root);//二叉树的大小

int BinaryTreeLeveKSize(BTNode* root, int k);//第k层有多少个元素

BTNode* BinaryTreeFind(BTNode* root, TreeDataType x);//查找数据

void PrevOrder(BTNode* root);//前序遍历

void InOrder(BTNode* root);//中序遍历

void PosOrder(BTNode* root);//后序遍历

二叉树的初始化

BTNode* TreeInit()
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->val = 0;
	root->left = NULL;
	root->right = NULL;

	return root;
}

二叉树的创建

BTNode* Creat(BTNode* t)
{
	TreeDataType ch;
	cin >> ch;
	if (ch == '-1')
	{
		t = NULL;
	}
	else
	{
		t->val = ch;
		Creat(t->left);
		Creat(t->right);
	}
}
----------------------------------------------------------

BTNode* BuyNode(TreeDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTNode* BinaryTreeCreate()
{
	BTNode* newnode1 = BuyNode('A');
	BTNode* newnode2 = BuyNode('B');
	BTNode* newnode3 = BuyNode('C');
	BTNode* newnode4 = BuyNode('D');
	BTNode* newnode5 = BuyNode('E');
	BTNode* newnode6 = BuyNode('F');
	BTNode* newnode7 = BuyNode('G');


	newnode1->left = newnode2;
	newnode1->right = newnode3;
	newnode2->left = newnode4;
	newnode4->left = newnode7;
	newnode3->left = newnode5;
	newnode3->right = newnode6;



	return newnode1;
}

两种方法创建二叉树,第一种方法是用前序遍历的方法创建二叉树,第二种是自己手动创建一个二叉树。

前序遍历

二叉树的前序遍历是先访问根节点,在访问左子树,在访问右子树,是以递归的形式进行的

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL ";
		return;
	}

	cout << root->val << ' ';
	PrevOrder(root->left);
	PrevOrder(root->right);
}

在这里插入图片描述

在这里插入图片描述

中序遍历

二叉树的中序遍历是先访问左子树,在访问根节点,然后右子树,同样是以递归的形式进行的。

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL ";
		return;
	}

	cout << root->val << ' ';
	PrevOrder(root->left);
	PrevOrder(root->right);
}

后序遍历

先左子树,在右子树,最后根节点

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		cout << "NULL ";
		return;
	}

	InOrder(root->left);
	cout << root->val << ' ';
	InOrder(root->right);
}

二叉树的销毁

二叉树的创建是用的先序遍历,而二叉树的销毁则用的是后续遍历

void BinaryTreeDestory(BTNode* root)
{
	if (!root)
	{
		return;
	}

	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);

	free(root);
}

二叉树的大小

二叉树的大小很好判断,想一想一个树很深,很多叶子,每个子树上都有一个小领导,小领导来查他管理的地区的叶子,然后层层向上汇报,直到汇报给最大的领导,就可以完成了。

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int l = BinaryTreeSize(root->left);
	int r = BinaryTreeSize(root->right);

	return l + r + 1;

}

二叉树第k层的大小

第k层的大小该怎么判断呢,还是用上面的办法,找到第k层的小领导,让他把第k层的情况汇报给你即可

int BinaryTreeLeveKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	int l = BinaryTreeLeveKSize(root->left, k - 1);
	int r = BinaryTreeLeveKSize(root->right, k - 1);

	return l + r;

}

二叉树查找数据

查找数据,从左子树找,从右子树找,依次递归即可

BTNode* BinaryTreeFind(BTNode* root, TreeDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->val == x)
	{
		return root;
	}

	BTNode* l = BinaryTreeFind(root->left, x);
	if (l)
	{
		return l;
	}
	BTNode* r = BinaryTreeFind(root->right, x);
	if (r)
	{
		return r;
	}

	return NULL;


}