免费浏览网站的软件,徐州网站排名系统,北京红酒网站建设,设备管理系统app本文主要介绍树形结构中的二叉树类型#xff0c;包括二叉树、平衡二叉树、二叉查找树和完全二叉树#xff1b;
1.二叉树
二叉树是一种树形结构#xff0c;其中每个节点最多有两个子节点#xff0c;通常称为左子节点和右子节点。二叉树具有以下特点#xff1a;
每个节点…本文主要介绍树形结构中的二叉树类型包括二叉树、平衡二叉树、二叉查找树和完全二叉树
1.二叉树
二叉树是一种树形结构其中每个节点最多有两个子节点通常称为左子节点和右子节点。二叉树具有以下特点
每个节点最多有两个子节点分别为左子节点和右子节点。左子节点的值小于或等于当前节点的值而右子节点的值大于当前节点的值。这个特性使得二叉树在查找和排序方面有很大的应用价值。二叉树可以为空树此时没有节点。
二叉树可以用递归或迭代方式来遍历。常见的二叉树遍历方法包括
前序遍历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::coutsame 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 TreeBST是一种特殊的二叉树它满足以下条件
对于树中的每个节点其左子树中的所有节点的值都小于该节点的值。对于树中的每个节点其右子树中的所有节点的值都大于该节点的值。对于树中的每个节点其左子树和右子树都是二叉查找树。
因此二叉查找树具有以下特点
左子节点的值小于父节点的值右子节点的值大于父节点的值。中序遍历二叉查找树得到的值序列是递增有序的。可以快速插入、删除和查找节点。
4.完全二叉树
完全二叉树Complete Binary Tree是一种特殊类型的二叉树在完全二叉树中除了最后一层其他层的节点都是满的且最后一层的节点尽可能地靠左排列。
具体来说完全二叉树的定义如下
如果一个二叉树的高度为hh 0并且它的节点从第 1 层到第 h-1 层都是满的第 h 层的节点都连续地排列在最左边若干位置上那么这棵二叉树就是完全二叉树。如果一个完全二叉树的最后一层有缺失节点则缺失节点只能集中在层末尾的若干位置上并且缺失的节点都是从左到右依次缺失的即不会出现在中间位置缺失。
完全二叉树主要涉及到元素的插入
void insert(int value) {Node* newNode new Node(value);// root是根节点if (root nullptr) {root newNode;return;}std::queueNode* 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);}
}
