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