树形结构——二叉树类型

本文主要介绍树形结构中的二叉树类型，包括二叉树、平衡二叉树、二叉查找树和完全二叉树；

1.二叉树

二叉树是一种树形结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树具有以下特点：

1. 每个节点最多有两个子节点，分别为左子节点和右子节点。
2. 左子节点的值小于或等于当前节点的值，而右子节点的值大于当前节点的值。这个特性使得二叉树在查找和排序方面有很大的应用价值。
3. 二叉树可以为空树，此时没有节点。

二叉树可以用递归或迭代方式来遍历。常见的二叉树遍历方法包括：

• 前序遍历（Preorder Traversal）：先访问根节点，再依次访问左子树和右子树。
• 中序遍历（Inorder Traversal）：先访问左子树，再访问根节点，最后访问右子树。中序遍历的结果是有序的。
• 后序遍历（Postorder Traversal）：先访问左子树，再访问右子树，最后访问根节点。
• 层序遍历（Level Order Traversal）：按层级顺序从上到下逐层遍历，即先访问根节点，然后访问第二层的所有节点，接着访问第三层的所有节点，以此类推。

1.1 二叉树的创建

创建一个二叉树的类型

class TreeNode 
{
public:int data;TreeNode* left;TreeNode* right;TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};class BinaryTree 
{
public:BinaryTree() : root(nullptr) {}~BinaryTree(){}// 创建二叉树void createTree(int val) {        root = createNode(val);     }// 创建新节点TreeNode* createNode(int val) {if (val == -1) {return nullptr;} else {return new TreeNode(val);}}    
private:TreeNode* root;
};

1.2 二叉树元素的插入

通过递归插入新的元素，这里需要区分根节点是否空；

	// 插入节点void insert(int val) {if (root == nullptr) {root = new TreeNode(val);return;}insertNode(root, val);}// 递归插入节点void insertNode(TreeNode* node, int val) {if (val <= node->data) {if (node->left == nullptr) {node->left = new TreeNode(val);} else {insertNode(node->left, val);}} else {if (node->right == nullptr) {node->right = new TreeNode(val);} else {insertNode(node->right, val);}}}

1.3 二叉树的删除

二叉树的删除使用递归的思想

// 删除二叉树void deleteTree(TreeNode* node) {if (node == nullptr) {return;}deleteTree(node->left);deleteTree(node->right);delete node;}

1.4 二叉树的遍历

二叉树的遍历分为前序遍历，中序遍历和后序遍历

	//二叉树的遍历——先序（先访问根节点）void preorderTraversal(TreeNode* root) {if (root == nullptr) {return;}// 访问根节点std::cout << root->data << " ";// 先序遍历左子树preorderTraversal(root->left);// 先序遍历右子树preorderTraversal(root->right);}//二叉树的遍历——中序（先访问左子树）void inorderTraversal(TreeNode* root) {if (root == nullptr) {return;}// 中序遍历左子树inorderTraversal(root->left);// 访问根节点std::cout << root->data << " ";// 中序遍历右子树inorderTraversal(root->right);}//二叉树的遍历——后序（先访问右子树）void postorderTraversal(TreeNode* root) {if (root == nullptr) {return;}// 后序遍历左子树postorderTraversal(root->left);// 后序遍历右子树postorderTraversal(root->right);// 访问根节点std::cout << root->data << " ";}

1.5 二叉树的判空

	 // 判断二叉树是否为空bool isEmpty() {return root == nullptr;}

1.6 二叉树的大小计算和深度计算

二叉树的大小计算指的是树形结构中有多少个元素；

二叉树的深度计算指的是树形结构中有多少层；

	// 获取二叉树的深度int getTreeDepth(TreeNode* root) {if (root == nullptr) {return 0;}int leftDepth = getTreeDepth(root->left);int rightDepth = getTreeDepth(root->right);return std::max(leftDepth, rightDepth) + 1;}int getTreeSize(TreeNode* root){int re= 0;//tree为空的时候if(root == nullptr){return re;}int left_size = getTreeSize(root->left);int right_size = getTreeSize(root->right);re = left_size + right_size + 1;return re;}

1.7 二叉树的查找

查找某一个元素是否在二叉树中，如果存在则返回true，不存在则返回false

	// 查询节点值是否存在于二叉树中bool search(int val) {return searchNode(root, val);}// 递归查询节点值是否存在于二叉树中bool searchNode(TreeNode* node, int val) {if (node == nullptr) {return false;}if (node->data == val) {return true;}return searchNode(node->left, val) || searchNode(node->right, val);}TreeNode* getRootValue(){return root;}

二叉树的使用

2.平衡二叉树（AVL树）

平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不超过1，并且左子树和右子树也都是平衡二叉树。平衡二叉树的设计目的是为了保持树的平衡，提高查找、插入和删除操作的效率，避免出现退化成链表的情况。实现一个平衡二叉树可以使用各种方法，最常用的是AVL树和红黑树。这些方法都通过旋转、重新平衡等操作来保持树的平衡性。在插入或删除节点时，需要根据树的平衡性进行相应调整，以保证树仍然是平衡的。平衡二叉树的平衡性可以确保树上的操作的时间复杂度为O(log n)，提供了高效的数据访问和操作能力。

平衡二叉树与二叉树相比，在元素插入的时候需要根据平衡因子，进行左旋操作或者右旋操作；

2.1 平衡二叉树的结构

class TreeNode 
{
public:int val;int height;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
};

2.3 获取平衡因子

这里的平衡因子指的是左子树和右子树的高度差值

    // 获取节点的平衡因子int getBalanceFactor(TreeNode* node) {if (node == nullptr) {return 0;}return getHeight(node->left) - getHeight(node->right);}// 获取节点的高度int getHeight(TreeNode* node) {if (node == nullptr) {return 0;}return node->height;}// 更新节点的高度void updateHeight(TreeNode* node) {node->height = std::max(getHeight(node->left), getHeight(node->right)) + 1;}

2.2 左旋操作和右旋操作

左旋操作和右旋操作是为了调整树形结构的高度；

	// 右旋操作，根节点TreeNode* rotateRight(TreeNode* y) {TreeNode* x = y->left;TreeNode* T2 = x->right;x->right = y;y->left = T2;updateHeight(y);updateHeight(x);return x;}// 左旋操作，根节点TreeNode* rotateLeft(TreeNode* x) {TreeNode* y = x->right;TreeNode* T2 = y->left;y->left = x;x->right = T2;updateHeight(x);updateHeight(y);return y;}

2.3 元素的插入

在每一个元素插入的时候，都需要根据平衡因子来判断是否需要进行左旋和右旋的操作；

void insert(int val){if (root == nullptr) {root =  new TreeNode(val);return;}root = insertNode(root, val);        }// 插入节点TreeNode* insertNode(TreeNode* node, int val) {        if (val < node->val) {if(node->left == nullptr ) {node->left = new TreeNode(val);}else{node->left = insertNode(node->left, val);}            } else if (val > node->val) {if(node->right == nullptr){node->right = new TreeNode(val);}else{node->right = insertNode(node->right, val);}} else {std::cout<<"same data!"<<std::endl;            return node;}updateHeight(node);int balanceFactor = getBalanceFactor(node);        if(node->left != nullptr){// Left-Left caseif (balanceFactor > 1 && val < node->left->val) {return rotateRight(node);}// Left-Right caseif (balanceFactor > 1 && val > node->left->val) {node->left = rotateLeft(node->left);return rotateRight(node);}            }if(node->right != nullptr){        // Right-Right caseif (balanceFactor < -1 && val > node->right->val) {return rotateLeft(node);}// Right-Left caseif (balanceFactor < -1 && val < node->right->val) {node->right = rotateRight(node->right);return rotateLeft(node);}        }return node;}

3.二叉查找树（BST）

二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下条件：

1. 对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值。
2. 对于树中的每个节点，其右子树中的所有节点的值都大于该节点的值。
3. 对于树中的每个节点，其左子树和右子树都是二叉查找树。

因此，二叉查找树具有以下特点：

1. 左子节点的值小于父节点的值，右子节点的值大于父节点的值。
2. 中序遍历二叉查找树得到的值序列是递增有序的。
3. 可以快速插入、删除和查找节点。

4.完全二叉树

完全二叉树（Complete Binary Tree）是一种特殊类型的二叉树，在完全二叉树中，除了最后一层，其他层的节点都是满的，且最后一层的节点尽可能地靠左排列。

具体来说，完全二叉树的定义如下：

1. 如果一个二叉树的高度为h（h >= 0），并且它的节点从第 1 层到第 h-1 层都是满的，第 h 层的节点都连续地排列在最左边若干位置上，那么这棵二叉树就是完全二叉树。
2. 如果一个完全二叉树的最后一层有缺失节点，则缺失节点只能集中在层末尾的若干位置上，并且缺失的节点都是从左到右依次缺失的（即不会出现在中间位置缺失）。

完全二叉树主要涉及到元素的插入

void insert(int value) {Node* newNode = new Node(value);// root是根节点if (root == nullptr) {root = newNode;return;}std::queue<Node*> q;q.push(root);while (!q.empty()) {Node* front = q.front();q.pop();   //删除队首元素if (front->left == nullptr) {front->left = newNode;return;} else if (front->right == nullptr) {front->right = newNode;return;}q.push(front->left);   q.push(front->right);}
}