什么是平衡二叉树?
二叉树 什么 平衡
2023-09-27 14:29:28 时间
什么是平衡二叉树?
任意节点子树的高度差都小于等于1
1.右旋公式
- 创建一个根节点，值等于当前根节点的值
- 把新节点的右子树设置成当前节点的右子树
- 把新节点的左子树设置成当前节点的左子树的右子树
- 把当前节点的值换位左子节点的值
- 把当前节点的左子树设置成左子树的左子树
- 把当前节点的右子树设置为新节点
2.左旋公式
- 创建一个新节点，值等于当前节点的值
- 把新节点的左子树设置成当前节点的左子树
- 把新节点的右子树设置位当前节点的右子树的左子树
- 把当前节点的值换位右子节点的值
- 把当前节点的右子树，设置为右子树的右子树
- 把当前节点的左子树设置为新节点
3.双旋转
- 符合右旋转的条件
- 当前节点的左子树的右子树高度，大于当前节点的左子树的左子树
- 对当前节点的左孩子进行左旋
- 再对当前节点进行右旋
相关文章
- 求二叉树中，包含的最大二叉搜索子树的节点数量是多少
- 五三想休息，今天还学习，图解二叉树的层序遍历BFS（广度优先）模板，附面试题题解
- [nowCoder] 完全二叉树结点数
- 1. 二叉树知识汇总
- 112、【树与二叉树】leetcode ——108. 将有序数组转换为二叉搜索树：二分查找树（C++版本）
- 105、【树与二叉树】leetcode ——530. 二叉搜索树的最小绝对差：中序遍历递归法+迭代法（C++版本）
- 【数据结构/二叉树/二叉树属性】题解+详细备注（共10题）
- 【刷题笔记】之牛客面试必刷TOP101(二叉树的前.中.后.层序遍历+按之字形顺序打印二叉树+二叉树的最大深度+二叉树中和为某一值的路径(一)+二叉搜索树与双向链表+判断是不是二叉搜索树)
- [LeetCode] Encode N-ary Tree to Binary Tree 将N叉树编码为二叉树
- [LeetCode] Second Minimum Node In a Binary Tree 二叉树中第二小的结点
- [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历