树、二叉树、平衡二叉树、二叉搜索树

树的前序遍历、中序遍历和后序遍历

树的前序遍历、中序遍历和后续遍历是以遍历时根所在的位置顺序命名的。层次遍历即按层从上至下，从左至右遍历即可。

• 前序遍历：根->左子树->右子树
• 中序遍历：左子树->根->右子树
• 后序遍历：左子树->右子树->根

以下图为例，前序遍历的结果则是：ABDGHCEIF；中序遍历的结果是GDHBEICF；后序遍历的结果是GHDBIEFCA。

二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树具有以下性质：

• 性质1：二叉树第i层上的结点数目最多为 $2^{i-1}$2i−1 (i≥1)。
• 性质2：深度为k的二叉树至多有$2^{k}-1$2k−1个结点 (k≥1)。
• 性质3：包含n个结点的二叉树的高度至少为$log_2^ {(n+1)}$log2(n+1)​。
• 性质4：在任意一棵二叉树中，若终端结点的个数为$n_0$n0​，度为2的结点数为$n_2$n2​，则$n_0=n_2+1$n0​=n2​+1。
  性质4的证明：设总节点数位n，则n=$n_0+n_1+n_2$n0​+n1​+n2​;除了根节点以外，只有叶子节点和非叶子节点并且所有节点都只有一个分支进入，所以$n-1=n_1+2n_2$n−1=n1​+2n2​(由度建立的等式）,联力则可得到$n_0=n_2+1$n0​=n2​+1。

采用递归、非递归分别实现前序遍历、中序遍历和后续遍历

仍然以上面的树为列，通过前序输入创建二叉树，输入依次为：ABDG##H###CE#I##F##

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
	char val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char x) :val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	//以前序方式建立二叉树
	void createBiTree(TreeNode* &T) {  //注意：&的意思是传进来节点指针的引用，目的是让传递进来的指针发生改变
		char c;
		std::cout<<"输入节点value，#表示为空\n";
		std::cin >> c;
		if (c == '#') {  //当遇到#时，令树的根节点为NULL，从而结束该分支的递归
			T = NULL;
		}
		else {
			T = new TreeNode(c);
			createBiTree(T->left);
			createBiTree(T->right);
		}
	}
	/*方法一：采用递归实现遍历*/

	//递归前序（根左右）
	void printPreTree(TreeNode* T) {
		if (T != NULL) {
			std::cout << T->val;
			printPreTree(T->left);
			printPreTree(T->right);
		}
	}
	//递归中序（左根右）
	void printMidTree(TreeNode* T) {
		if (T != NULL) {
			printMidTree(T->left);
			std::cout << T->val;
			printMidTree(T->right);
		}
	}
	//递归后序（左右根）
	void printPostTree(TreeNode* T) {
		if (T != NULL) {
			printPostTree(T->left);
			printPostTree(T->right);
			std::cout << T->val;
		}
	}

	/*方法一：采用非递归实现遍历*/
	//非递归前序（根左右）
	//
	void printPreTreeNoRecursion(TreeNode* T) {
		stack<TreeNode*> mystack;
		TreeNode* pre = NULL;
		while (!mystack.empty() || T != NULL) {
			while (T != NULL) {  //把左孩子压入栈内
				std::cout << T->val;
				mystack.push(T);
				T = T->left;
			}
			//当T为空时，说明根和左子树都遍历完了，该进入右子树了
			if (!mystack.empty()) {//出栈+压右孩子入栈
				T = mystack.top();
				mystack.pop();
				T = T->right;
			}
		}
	}
	//非递归中序（左根右）
	void printMidTreeNoRecursion(TreeNode* T) {
		stack<TreeNode*> mystack;
		TreeNode* pre = NULL;
		while (!mystack.empty() || T != NULL) {
			while (T != NULL) {  //把左孩子压入栈内
				mystack.push(T);
				T = T->left;
			}
			//当T为空时，说明根和左子树都遍历完了，该进入右子树了
			if (!mystack.empty()) {//出栈+压右孩子入栈
				T = mystack.top();
				std::cout << T->val;
				mystack.pop();
				T = T->right;
			}
		}

	}
	//递归后序（左右根）
	void printPostTreeNoRecursion(TreeNode* T) {
		stack<TreeNode*> mystack;
		TreeNode* pre = NULL;
		TreeNode* pLastVisit=NULL;//记录上一次访问的点
		while (T != NULL) {  //走到最左下端
			mystack.push(T);
			T = T->left;
		}
		while (!mystack.empty()) {
			T = mystack.top();
			mystack.pop();
			//根节点被访问：右子树为空||右子树已经被访问
			if (T->right == NULL || T->right == pLastVisit)
			{
				std::cout << T->val;
				pLastVisit = T;//修改上次访问节点
			}
			else {
				mystack.push(T); //根节点再次入栈
				T = T->right;   //此时右子树一定没被访问
				while (T != NULL) {
					mystack.push(T);
					T = T->left;
				}
			}
		}
	}
};

int main()
{
	Solution s;
	TreeNode* T=NULL;
	s.createBiTree(T);
	std::cout << "二叉树建立完成\n";
	//前序打印
	std::cout << "递归前序打印的结果为：";
	s.printPreTree(T);
	std::cout << "\n";
	std::cout << "递归中序打印的结果为：";
	s.printMidTree(T);
	std::cout << "\n";
	std::cout << "递归后序打印的结果为：";
	s.printPostTree(T);
	std::cout << "\n";
	std::cout << "非递归前序打印的结果为：";
	s.printPreTreeNoRecursion(T);
	std::cout << "\n";
	std::cout << "非递归中序打印的结果为：";
	s.printMidTreeNoRecursion(T);
	std::cout << "\n";
	std::cout << "非递归后序打印的结果为：";
	s.printPostTreeNoRecursion(T);
	return 0;
}

完全二叉树

1. 完全二叉树是一种特殊的二叉树，满足以下要求：
   （1）所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；
   （2）第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。
   （3）任何一个节点不能只有左子树没有右子树
   （4）叶子节点只出现在最后一层或者倒数第二层
2. 完全二叉树的应用：堆排序
3. 当我们用数组实现一个完全二叉树时，n个节点按层编号（从0开始），然后知道一个节点的位置，就可以轻松地算出它的父节点、孩子节点的位置。比如编号为i的节点：

• 其父节点的编号为$\frac{(i-1)}{2}$2(i−1)​;
• 如果$2*i+1&lt;n$2∗i+1<n，其左子树的根节点编号为$2*i+1$2∗i+1，否则没有左子树
• 如果$2*i+2&lt;n$2∗i+2<n，其右子树的根节点编号为$2*i+2$2∗i+2，否则没有右子树

二叉查找树

1. 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
   （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
   （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
   （3）左、右子树也分别为二叉排序树；
   （4）没有键值相等的节点。
2. 最坏情况下，比如当先后插入的关键字有序时，生成的二叉排序树退化为单枝树，其实就是一个链表，时间复杂度为 $O(n)$O(n)，最好的情况是如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为$Log_2^{(n+1)}$Log2(n+1)​,其查找效率为$O(Log_2^{n})$O(Log2n​)，其访问性能近似于折半查找。

平衡二叉树（AVL树）

1. 平衡二叉树又被称为AVL树，或者一颗空树，或者是具备以下特征的一种特殊的二叉查找树：
   （1）它的左右两个子树的高度差(平衡因子)的绝对值不超过1；
   （2）并且左右两个子树都是一棵平衡二叉树；
2. 平衡因子：左子树的高度-右子树的高度
   以下图为例，左边每个节点的平衡因子绝对值均不超过1，为平衡二叉树；右边树中存在平衡因子绝对值超过2的节点，不是平衡二叉树
   
3. 平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度；平衡二叉树可以解决二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在$O(logN)$O(logN)。
4. 平衡调节： 当我们往一个平衡二叉树插入一个新的子节点，可能造成平衡二叉树的失衡，即存在有节点的平衡因子为2或者-2的状态，因此我们需要调节二叉树，使之保持平衡。通常会出现四种情况，因此需要四种操作来平衡二叉树。【注意：旋转过程中要注意平衡二叉树是二叉排序树的特点】
   (1)右旋：当有节点的平衡因子为2时，说明左边子树深度大于右边，因此需要右旋。
   
   (2)左旋：当有节点的平衡因子为-2时，说明右边的子树的深度大于左边，因此需要左旋。
   
   (3)右左旋：先让子树4和6右旋，再整体左旋
   
   (4)左右旋：先让子树2和4左旋，再整体右旋
   
5. 伪代码
   

红黑树R-B Tree

1. 红黑树，是一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红或黑。满足：
   （1）每个节点或者是黑色，或者是红色。
   （2）根节点是黑色。
   （3）每个叶子节点是黑色。【注：这里叶子节点，是指为空(NIL或NULL)的叶子节点】
   （4）如果一个节点是红色的，则它的子节点必须是黑色的。
   （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
   【注】：特性(3)中的叶子节点，是只为空(NIL或null)的节点；特性(5)确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对接近平衡的二叉树。
   
2. 红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高

B+树

B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。
B+树只要遍历叶子节点就可以实现整棵树的遍历

参考资料

二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解
二叉树，平衡二叉树，红黑树，B-树、B+树、B*树的区别
大话数据结构之平衡二叉树
一步步分析为什么B+树适合作为索引的结构