700字范文 > 数据结构树二叉树完全二叉树二叉查找树平衡二叉树红黑树 B+树

数据结构树二叉树完全二叉树二叉查找树平衡二叉树红黑树 B+树

时间：2022-07-12 07:13:20

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

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

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

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

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

二叉树

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

性质1：二叉树第i层上的结点数目最多为 2 i − 1 2^{i-1} 2i−1 (i≥1)。性质2：深度为k的二叉树至多有 2 k − 1 2^{k}-1 2k−1个结点 (k≥1)。性质3：包含n个结点的二叉树的高度至少为 l o g 2 ( n + 1 ) log_2^ {(n+1)} log2(n+1)。性质4：在任意一棵二叉树中，若终端结点的个数为 n 0 n_0 n0，度为2的结点数为 n 2 n_2 n2，则 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1。

性质4的证明：设总节点数位n，则n= n 0 + n 1 + n 2 n_0+n_1+n_2 n0+n1+n2;除了根节点以外，只有叶子节点和非叶子节点并且所有节点都只有一个分支进入，所以 n − 1 = n 1 + 2 n 2 n-1=n_1+2n_2 n−1=n1+2n2(由度建立的等式）,联力则可得到 n 0 = n 2 + 1 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）所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；

（2）第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。

（3）任何一个节点不能只有左子树没有右子树

（4）叶子节点只出现在最后一层或者倒数第二层完全二叉树的应用：堆排序当我们用数组实现一个完全二叉树时，n个节点按层编号（从0开始），然后知道一个节点的位置，就可以轻松地算出它的父节点、孩子节点的位置。比如编号为i的节点：其父节点的编号为 ( i − 1 ) 2 \frac{(i-1)}{2} 2(i−1);如果 2 ∗ i + 1 < n 2*i+1<n 2∗i+1<n，其左子树的根节点编号为 2 ∗ i + 1 2*i+1 2∗i+1，否则没有左子树如果 2 ∗ i + 2 < n 2*i+2<n 2∗i+2<n，其右子树的根节点编号为 2 ∗ i + 2 2*i+2 2∗i+2，否则没有右子树

二叉查找树

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。最坏情况下，比如当先后插入的关键字有序时，生成的二叉排序树退化为单枝树，其实就是一个链表，时间复杂度为 O ( n ) O(n) O(n)，最好的情况是如果二叉排序树是平衡的，则n个节点的二叉排序树的高度为 L o g 2 ( n + 1 ) Log_2^{(n+1)} Log2(n+1),其查找效率为 O ( L o g 2 n ) O(Log_2^{n}) O(Log2n)，其访问性能近似于折半查找。

平衡二叉树（AVL树）

可以参考清华大学数据结构C++第七章，从zig/zag旋转的角度讲解的非常明白

平衡二叉树又被称为AVL树，或者一颗空树，或者是具备以下特征的一种特殊的二叉查找树：

（1）它的左右两个子树的高度差(平衡因子)的绝对值不超过1；

（2）并且左右两个子树都是一棵平衡二叉树；平衡因子：左子树的高度-右子树的高度

以下图为例，左边每个节点的平衡因子绝对值均不超过1，为平衡二叉树；右边树中存在平衡因子绝对值超过2的节点，不是平衡二叉树

平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度；平衡二叉树可以解决二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在 O ( l o g N ) O(logN) O(logN)。平衡调节：当我们往一个平衡二叉树插入一个新的子节点，可能造成平衡二叉树的失衡，即存在有节点的平衡因子为2或者-2的状态，因此我们需要调节二叉树，使之保持平衡。通常会出现四种情况，因此需要四种操作来平衡二叉树。【注意：旋转过程中要注意平衡二叉树是二叉排序树的特点】

(1)右旋：当有节点的平衡因子为2时，说明左边子树深度大于右边，因此需要右旋。

(2)左旋：当有节点的平衡因子为-2时，说明右边的子树的深度大于左边，因此需要左旋。

(3)右左旋：先让子树4和6右旋，再整体左旋

(4)左右旋：先让子树2和4左旋，再整体右旋

伪代码【ZIG/ZAG】