关于C++数据结构中的二叉树的学习笔记

关于C++数据结构中的二叉树的学习笔记,第1张

关于C++数据结构中的二叉树的学习笔记

这两天回顾了二叉树的上和下的算法专栏,先用这篇博客来记录我的学习笔记。

本.txt,我将再一次学习二叉树这种数据结构!


前面我们都只是讲了线性表结构而已,比如:栈和队列等数据结构。那么今天我们将来讲解一种非线性表结构---树!
树这种数据结构比线性表的数据结构要复杂得多!内容也比较多,因此专栏的王老师分为了4节课去讲解!

二叉树的存储方式主要有2种方式,分别是 链式存储 和 顺序存储

所谓的链式存储其实就是用链表list来do树这种数据结构!
所谓的顺序存储其实就是用数组arr来do树这种数据结构!


	  e
	/   
   a     b
  /    / 
 c   d i   f 这里的每个元素我们都叫做是节点,用来连接相邻节点之间的关系
			 我们就叫做“父子关系”
	树的一些基本概念(必须掌握):
		1-父节点:e是a和b的父亲节点
		2-子节点:a和b都是e的子节点
		3-兄弟节点:父亲节点都是同一个的结点就互称之为兄弟节点。比如:a和b的父节点都是e,因此a和b之间互称为兄弟节点
		4-根节点:没有父亲节点的结点就称之为根节点,比如e就是根节点
		5-叶子节点(叶节点):没子节点的结点就称之为叶子节点,比如c d i f都是叶子节点  

		(用生活中的例子来记忆这种数据结构的特点,非常快!)
		6-节点的高度:(类比生活中你判断一栋大楼的高度是多少,我们就从第0层开始计算,从下往上计算!)
		7-节点的深度:(类比生活中你判断水下的鱼在哪个水深(深度)处,是从水平面为0开始计算,从上往下计算!)
		8-节点的层数:(和节点深度的计算差不多,只不过层数是从1开始计算的,也是从上往下计算,比如根节点的层数就是1)


		9-树的高度:== 跟节点的高度 == 最大层数-1
		
		例子:				高度   深度    层		这个树的高度== 3
			  o		   --->  3      0     1 		
			/   			 
		   o     o	   --->  2      1     2
		  /    / 
		 o   o o   o   --->  1      2     3
		/        /
	   o   o	 o     --->  0      3     4
	

	树的结构多种多样,不过我们最常用的还是二叉树!

	二叉树(binary tree)
		:二叉树,顾名思义,就是每一个节点最多有2个“叉”,也就是有2个子节点,分别是
		左子节点 和 右子节点 。不过,二叉树并不要求每个节点都有2个子节点,有的结点只有左子节点
		而有的结点则只有右子节点。下面这3个图都是二叉树的三种常见的例子!

	二叉树的分类:
		1-普通二叉树:一般二叉树都是普通二叉树
		2-满二叉树:叶子节点全部都在最底层,并且除了叶子节点外,每个节点都有左右2个子节点
		3-完全二叉树:作为完全二叉树必须要满足2个特点:
		①除了最底层外,其他层节点个数达到最大(也即除去最底层后这个二叉树会变成满二叉树的意思!)
		②最底层的叶子节点从左边依次排列过来,并且中间没有断开过
 
		完全二叉树 和 满二叉树 是比较适合于用数组做顺序存储的!因为它们的节点数目都比较多,不会浪费数组的存储空间
		除了0下标外,其他的元素都可以按顺序的按照索引来存储。
		而其他类型的二叉树就比较适合用链表来do存储了!
 
							  o		   
							/   
						   o     o	   
						  /     / 
						 o     o   
					   /  
					  o    o   
						  /    
						 o   o
							(1)	(这是普通的二叉树!)

							o
						/         
					   o           o
					  /          / 
					 o   o       o   o										  
			        /   /     /  / 
				   o  o o  o   o  o o  o  
							(2)	(满二叉树:是满二叉树的一种特殊的case!!!)

						     o
						/         
					   o           o
					  /          / 
					 o   o       o   o
					/   /   
				   o  o o   
							(3)(完全二叉树)
						     o
						/         
					   o           o
					  /          / 
					 o   o       o   o
					/          /
				   o   o       o
				            (4) (这就是个普通的二叉树,非完全二叉树,因为虽然满足除了最底层外其他层的节点个数达到最大)
								(但是最底层的叶子节点们的节点是断开过的,并不连续!)


	

	那么下面我们就来实现一下一棵二叉树:
		我们有2种方法: 一种是基于指针or引用的二叉链式存储法(一个节点有3份字段,一份存data,另外2份分别存储指向左右子节点的指针)
					   一种是基于数组的顺序存储法!(下标为0的空间会浪费掉,用下标为1的空间来存储根节点root,然后用2*i的下标位置存储左子节点,用2*i+1的下标位置存储右子节点)

	我们先来看比较简单和直观的 链式存储法:
			所谓的二叉树的链式存储法,其实就是:一个节点有3个字段,一个存储data,另外2个是分别指向其左右节点的指针!

		比如:
		  data
		  / 
		left right
		/         
	  data          data
	  / 			/   
	left right   left   right
		
	我们再来看不那么直观的 数组存储法:我们会用一个数组来存储二叉树种的all的节点元素
	其中,浪费一个下标为0的数组空间,然后用下标为1的空间存储二叉树的根节点,然后用2*1 = 2的位置存储它的左子节点
	然后用2*1+1 = 3的位置来存储它的右子节点,用2*2=4的位置存储根节点的左字节点的左子节点,用2*2+1=5的位置存储根节点的右子节点
	的右子节点,然后以此类推。
	比如:
			(1)	  a
			  /     
			 b(2)    c(3)
			/   	  /  
		  d(4)  e(5) f(6) g(7)
		  ......................以此类推!

	[] [a] [b]  [c]  [d]  [e]  [f]  [g] ....[] [] []  []
	0  1    2    3    4    5    6    7    8    9    10    11

	当然,这仅仅是把完全二叉树用数组的存储方式表示出来,如果你是一个普通一点的二叉树甚至是单臂树的话,这样就会非常的浪费存储空间!
	so:
	总结:
		如果是满二叉树或者是完全二叉树的话,那么用数组的存储方式来表示是完全没问题的,也无疑是最节省内存的一种方式
	,但是对于别的形式的二叉树,一般我们都是用链式存储方式来存储的!
		当然我们学习到 堆和堆排序时,你就会发现, 堆其实就是一种完全二叉树,其最常用的存储方式就是数组




	下面我们来看二叉树中非常重要的 *** 作,也即二叉树的遍历,这也是非常常见的面试题!
	
	我们如何将所有的节点都遍历打印出来呢?
	经典的方法有3种:
		前序遍历、中序遍历和后序遍历
		其中,何为之前序中序和后序呢?其实就是表示:节点与它的左右子树节点遍历打印的先后顺序!
	
	1-前序遍历:对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树 (本身 左 右)
	2-中序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后才打印它的右子树(左 本身 右)
	3-后序遍历:对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后再打印这个节点本身(左 右 本身)
	
	从以上的概念中,你就可以清晰的认识到所谓的前中后序遍历是啥意思了,
	-前序就是要本身在前,左右在后
	-中序就是要本身在左右的中间
	-后序就是要本山在最后,左右在前
	(实际上呢,二叉树的前中后序遍历其实就是一个递归的过程。比如:前序遍历,其实就是先打印根节点,然后再递归地打印左子树,最后递归地打印右子树)
	(上面这个本质的思想一定要建立起来!不能有所含糊,不然你就会搞不懂怎么对二叉树进行前中后序的遍历了!)
	
	而写递归代码的关键,其实就是看你能不能写出递归的递推公式!以及递归的终止条件了。
	写递归的递推公式的关键就是,如果要解决问题a,就假设子问题b和c已经被解决了,然后再来看如何利用b和c来deal问题a
	比如下面来几个例子(帮助我理解一下这几个概念):
		前序遍历:
			a
		 /    
		b      c
	  /      /  
	 d    e  f    g
result: a->b->d->e->c->f->g
		中序遍历:
			1
		 /    
	   -2      3
	  /      /  
	 -3   -1 2    4    
result: -3 -> -2 -> -1 -> 2 -> 3 -> 4
从这里我们可以看出来对于二叉树的中序遍历,可以输出有序(升序)的数据序列,且时间复杂度为O(n),这是非常高效的!
因此二叉查找树也被称之为二叉排序树。
		后序遍历:
			a
		 /    
		b      c
	  /      /  
	 d    e  f    g
result: d->e->b->f->g->c->a



	前面我们学习了树、二叉树、二叉树的遍历,那么今天我们再来学习一种特殊的二叉树---二叉查找树。

	二叉查找树之最大的特点就是:支持动态数据集合的快速插入、删除、查找 *** 作。

	我们之前说过,散列表也是支持这些 *** 作的,并且散列表的这些 *** 作比二叉查找树更加地高效,且时间复杂度为O(1).
	
	那么既然有了这么高效的散列表,使用二叉树的地方是不是都可以替换成散列表呢?有没有哪些地方是散列表所do不了的呢?
	有什么地方是必须要使用二叉树来do的呢?



	二叉查找树(也称之为二叉搜索树或者说二叉排序树):Binary Search Tree
		二叉查找树是二叉树中最为常用的一种类型,也叫做二叉搜索树。顾名思义呢,二叉查找树是为了实现快速查找而生的。
		只不过呢,它不仅仅是支持快速查找一个数据这一种 *** 作的,它还支持快速的插入、删除一个数据。它是怎么做到这些的呢?

	二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树中的每个节点的值都大于这个节点的值。
	就比如:
		13							16							10
	  /	   					   /                           /  
	10      16					  10                          9    14
    /       /					 /                                /  
  9   11   14                   9    13                           13  16
		(1)							/                           / 
								   11   14                      11
									(2)                          (3)  
  

下面是我根据理论知识手动敲出来的二叉查找树的代码:

MyTreeNode.hpp:

#ifndef MYTREENODE 
#define MYTREENODE
#include
using namespace std;
template
class MyTreeNode//无prevFather节点的二叉搜索树!
{
public:
	typedef  MyTreeNode Node;
	T data;
	Node* left;
	Node* right;
public:
	//构造函数
	MyTreeNode() :data(0), left(nullptr), right(nullptr) {}
	MyTreeNode(T d) :data(d), left(nullptr), right(nullptr) {}
	MyTreeNode(T d, Node* l, Node* r) :data(d), left(l), right(r) {}
	//拷贝构造函数
	MyTreeNode(const Node*& node)
	{
		this->data = node->data;
		this->left = new Node(node->left->data,node->left->left,node->right->right);
		this->right = new Node(node->right->data, node->right->left, node->right->right);
	}
	//拷贝赋值函数
	Node*& operator=(const Node*& node)
	{
		Node* tempNode = new Node;
		tempNode->data = node->data;
		tempNode->left = new Node(node->left->data, node->left->left, node->right->right);
		tempNode->right = new Node(node->right->data, node->right->left, node->right->right);
		return tempNode;
	}
};

#endif // !MYTREENODE 

MyBinSearchTree.hpp:

#ifndef MYBINSEARCHTREE 
#define MYBINSEARCHTREE
#include
#include"MyTreeNode.hpp"
using namespace std;                                                                                                                
template

class MyBinSearchTree//无prevFather节点的二叉搜索树!
{
public:
	typedef  MyTreeNode Node;
	Node* root;
public:
	//构造函数
	MyBinSearchTree() :root(nullptr) {}
	MyBinSearchTree(T rootData)
	{
		this->root = new Node;//对于树的根节点,当你创建一颗树的时候就必须要new一个root了!
		this->root->data = rootData;
	}
	//创建一个二叉查找树的函数
	void createMyTree(T val, Node* &temp);
	//二叉查找树的find查找的函数
	MyTreeNode* find(T val);
	//二叉查找树的insert插入节点的函数
	bool insert(T val);
	void findPreFatherOfP(MyTreeNode* & pPrev, MyTreeNode* &p, T val);
	//二叉查找树的delete节点的函数
	bool deleteNode(T val);
	//前序遍历
	void preOrder(Node* tree);
	//中序遍历
	void middleOrder(Node* tree);
	//后序遍历
	void lastOrder(Node* tree);

};

//二叉查找树的find查找的函数
template
MyTreeNode* MyBinSearchTree::find(T val)
{
	
	Node* temp = this->root;
	while (temp != nullptr)
	{
		if (val == temp->data) {
			return temp;
		}
		if (val < temp->data) {
			temp = temp->left;
			continue;
		}
		if (val > temp->data) {
			temp = temp->right;
			continue;
		}
	}
	return nullptr;//if都找不到就返回nullptr!
}
template
void MyBinSearchTree::findPreFatherOfP(MyTreeNode* &pPrev, MyTreeNode* &p,T val)
{
	while (p != nullptr && p->data != val)
	{
		pPrev = p;
		if (val < p->data) {
			p = p->left;
		}
		else if (val > p->data) {
			p = p->right;
		}
	}
}
//二叉查找树的delete节点的函数
template
bool MyBinSearchTree::deleteNode(T val)
{
	Node* node = MyBinSearchTree::find(val);
	if (node == nullptr) {
		return false;
		//你 在这一棵二叉查找树中连找都找不到这个元素当然删除失败啦!
	}
	//这个元素存在的大case下你才能删除啊对吧?
	Node* p = this->root;
	Node* pPrev = nullptr;
	if (node->left == nullptr && node->right == nullptr)
	{//小case1:若值等于给定值的这个节点既没有左子树也没有右子树
		findPreFatherOfP(pPrev, p, val);
		//删除元素
		if (p->data < pPrev->data) {
			pPrev->left = nullptr;
			return true;
			cout << "删除成功!" << endl;
		}
		else if (p->data > pPrev->data) {
			pPrev->right = nullptr;
			return true;
			cout << "删除成功!" << endl;
		}
	}
	if (node->left != nullptr && node->right == nullptr)
	{//小case2:若值等于给定值的这个节点有左子树但没有右子树
		findPreFatherOfP(pPrev, p, val);
		//删除元素
		Node* thisdeleteNode = p;
		p = p->left;
		if (p->data < pPrev->data) {
			pPrev->left = p;
		}
		else if (p->data > pPrev->data) {
			pPrev->right = p;
		}
		thisdeleteNode = nullptr;
		cout << "删除成功!" << endl;
		return true;
	}
	if (node->left == nullptr && node->right != nullptr)
	{	//小case3:若值等于给定值的这个节点没有左子树但有右子树
		findPreFatherOfP(pPrev, p, val);
		//删除元素
		Node* thisdeleteNode = p;
		p = p->right;
		if (p->data < pPrev->data) {
			pPrev->left = p;
		}
		else if (p->data > pPrev->data) {
			pPrev->right = p;
		}
		thisdeleteNode = nullptr;
		cout << "删除成功!" << endl;
		return true;
	}

	if (node->left != nullptr && node->right != nullptr) 
	{//小case4:若值等于给定值的这个节点既有左子树也有右子树
		findPreFatherOfP(pPrev, p, val);
		Node* minP = p->right;//保存找待删除节点的右子树中值等于最小值的当前节点
		Node* minPP = p;//保存找待删除节点的右子树中值等于最小值的父亲节点
		//左子树不为空的case下!
		if (minP->left != nullptr) {
			while (minP->left != nullptr) {
				minPP = minP;
				minP = minP->left;
			}
			p->data = minP->data;//只需要把待删除节点的值赋值为其右子树中的最小值
			minPP->left = minP->right;
			//我不管你当前最小值是否还存在右子树,
			//我都把他的父亲节点的左子树赋值为该最小值节点的右子树
			//(当然,左子树肯定是不存在的,因为最小了,就必须不存在左子树了!否则就不是二叉查找树了啊!)
			minP = nullptr;
			cout << "删除成功!" << endl;
			return true;
		}//左子树为空的case下!
		else {
			if (minP->right != nullptr) {
				p->data = minP->data;//只需要把待删除节点的值赋值为其右子树中的最小值
				minPP->right = minP->right;
				minP = nullptr;
				cout << "删除成功!" << endl;
				return true;
			}
			else {
				p->data = minP->data;
				minPP->right = nullptr;
				minP = nullptr;
				cout << "删除成功!" << endl;
				return true;
			}
		}

	}

	return false;
}

//二叉查找树的insert插入节点的函数
template
bool MyBinSearchTree::insert(T val)
{
	if (MyBinSearchTree::find(val) != nullptr) {
		cout << "我的二叉查找树不允许存在重复的"<root;
	while (temp != nullptr)
	{
		if (val < temp->data && temp->left==nullptr) {
			temp->left = new Node(val);
			return true;
		}
		if (val > temp->data && temp->right == nullptr) {
			temp->right = new Node(val);
			return true;
		}
		if (val < temp->data && temp->left != nullptr) {
			temp = temp->left;
			continue;
		}
		if (val > temp->data && temp->right != nullptr) {
			temp = temp->right;
			continue;
		}
	}
	return false;
}

//前序遍历
template
void MyBinSearchTree::preOrder(Node* tree)//中左右
{
	Node* temp = tree;
	if (temp != nullptr) {
		cout << temp->data << endl;
	}
	if (temp->left != nullptr) {
		MyBinSearchTree::preOrder(temp->left);
	}
	if (temp->right != nullptr) {
		MyBinSearchTree::preOrder(temp->right);
	}
}
//中序遍历
template
void MyBinSearchTree::middleOrder(Node* tree)//左中右
{
	Node* temp = tree;
	if (temp->left != nullptr) {
		MyBinSearchTree::middleOrder(temp->left);
	}
	if (temp != nullptr) {
		cout << temp->data << endl;
	}
	if (temp->right != nullptr) {
		MyBinSearchTree::middleOrder(temp->right);
	}
}
//后序遍历
template
void MyBinSearchTree::lastOrder(Node* tree)//左右中
{
	Node* temp = tree;
	if (temp->left != nullptr) {
		MyBinSearchTree::lastOrder(temp->left);
	}
	if (temp->right != nullptr) {
		MyBinSearchTree::lastOrder(temp->right);
	}
	if (temp != nullptr) {
		cout << temp->data << endl;
	}
}
template
void MyBinSearchTree::createMyTree(T val, Node* &temp)
{
	
	if (temp == nullptr)
	{
		cout << "插入成功!" << endl;
		temp = new Node(val);
	}
	else
	{
		if (temp->data == val)
		{
			cout << "我不允许二叉查找(搜索)树中存在从重复元素!" << endl;
		}
		else if (val < temp->data) {
			createMyTree(val, temp->left);
		}
		else if (val > root->data) {
			createMyTree(val, temp->right);
		}
	}
}
#endif // !MYBINSEARCHTREE 

MyBinTree.cpp:

#include
#include"MyTreeNode.hpp"
#include"MyBinSearchTree.hpp"
using namespace std;
void createMyTree(MyBinSearchTree* &myTree)
{
	//创建一个二叉树
	int val = 0;
	while (1)
	{
		cout << "请输入你要插入的节点的val值:(-999 to quit!)" << endl;
		cin >> val;
		if (val == -999) {
			cout << "结束创建二叉树!" << endl;
			break;
		}
		myTree->createMyTree(val, myTree->root);
	}
}
void testMyTree()
{
	int v = 0;
	cout << "请输入你所要创建的二叉搜索树的root根节点的val值:" << endl;
	cin >> v;
	MyBinSearchTree* myTree = new MyBinSearchTree(v);
	//创建一个二叉树
	createMyTree(myTree);
	//前序遍历
	cout << "前序遍历:" << endl;
	myTree->preOrder(myTree->root);
	//中序遍历
	cout << "中序遍历:" << endl;
	myTree->middleOrder(myTree->root);
	//后序遍历
    cout << "后序遍历:" << endl;
	myTree->lastOrder(myTree->root);
	//查找val值
	cout << "查找操作:" << endl;
	MyTreeNode* t = myTree->find(-6);
	if (t) {
		cout << "查找元素:" << t->data << "成功!"<insert(5);
	if (ret) {
		cout << "插入5成功!" << endl;
	}
	else cout << "插入5失败!" << endl;
	//用前序遍历来show 一下当前的二叉查找树中的all元素!
	myTree->preOrder(myTree->root);
	bool ret2 = myTree->insert(6);
	if (ret2){
		cout << "插入6成功!" << endl;
	}
	else cout << "插入6失败!" << endl;
	//用前序遍历来show 一下当前的二叉查找树中的all元素!
	myTree->preOrder(myTree->root);

	//删除值为val的节点
	cout << "删除操作:" << endl;
	bool retDeleteResult = myTree->deleteNode(18);
	if (retDeleteResult) 
		cout << "删除成功!" << endl;
	else
		cout << "删除失败!" << endl;
	//用前序遍历来show 一下当前的二叉查找树中的all元素!
	myTree->preOrder(myTree->root);
}
int main(void)
{
	
	testMyTree();
	system("pause");
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/4653842.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-06
下一篇 2022-11-06

发表评论

登录后才能评论

评论列表(0条)

保存