C++ 各类树的算法_c++实现构建非二叉树已知父子节点

树的内容比较多，我一步步积累到这篇文章中

数据结构

最基本的二叉树，结构体中分别有基本的左孩子节点，有孩子节点，val数据值等基本内容

二叉搜索树：左孩子要比父节点小，右孩子要比父节点大。由于树构建完成后是有序的，所以插入，删除，查找都会有很大的优势。

举一个二叉搜索树的例子：当我们实现排名的数据结构的时候，我们发现，对于任意一个根节点，左子树的排名都比自己小，右子树的排名都比自己大。也就是说，比如1~10000人的排名，数据为10000个人的分数。如果想要查找我们的位置，显然很容易。除此之外，我们可以利用它计算排名。当我们进入右子树的时候，左边的分数都是比自己小的，不考虑，当我们进入左子树的时候，右子树的分数都比自己大，count右子树的节点，将会获得排名在自己后面的人数。

字典树：（字符串树）常用于存储字符串，查询效率比哈希树高。它的特点是不同的单词之间可以共享字符串。比如add和am共享a。这样如果把一个单词存储为从根节点的子节点到叶节点，节点数量会大大减少。根节点的子节点一共才26个。

平衡二叉树
平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。一句话表述为：以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

但是虽然平衡二叉树平衡度高，但是当插入或删除的时候，会由多次旋转才可以得到，改变结构。

红黑树