精华内容
下载资源
问答
  • 生成平衡二叉树例题
    千次阅读
    2021-02-12 02:06:04

    力扣关于平衡二叉树的题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树的题目应该不至于没有思路。当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。

    110. 平衡二叉树(简单)

    最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。

    题目描述

    给定一个二叉树,判断它是否是高度平衡的二叉树。

    本题中,一棵高度平衡二叉树定义为:

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

    示例 1:

    给定二叉树 [3,9,20,null,null,15,7]

    3

    / \

    9 20

    / \

    15 7

    返回 true 。

    示例 2:

    给定二叉树 [1,2,2,3,3,null,null,4,4]

    1

    / \

    2 2

    / \

    3 3

    / \

    4 4

    返回 false

    思路

    由于平衡二叉树定义为就是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。用伪代码描述就是:

    if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是平衡二叉树 and root.right 也是平衡二叉树:

    print('是平衡二叉树')

    else:

    print('不是平衡二叉树')

    而 root.left 和 root.right 如何判断是否是二叉平衡树就和 root 是一样的了,可以看出这个问题有明显的递归性。

    因此我们首先需要知道如何计算一个子树的高度。这个可以通过递归的方式轻松地计算出来。计算子树高度的 Python 代码如下:

    def dfs(node, depth):

    if not node: return 0

    l = dfs(node.left, depth + 1)

    r = dfs(node.right, depth + 1)

    return max(l, r) + 1

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def isBalanced(self, root: TreeNode) -> bool:

    def dfs(node, depth):

    if not node: return 0

    l = dfs(node.left, depth + 1)

    r = dfs(node.right, depth + 1)

    return max(l, r) + 1

    if not root: return True

    if abs(dfs(root.left, 0) - dfs(root.right, 0)) > 1: return False

    return self.isBalanced(root.left) and self.isBalanced(root.right)

    复杂度分析

    时间复杂度:对于 isBalanced 来说,由于每个节点最多被访问一次,这部分的时间复杂度为 $O(N)$,而 dfs 函数 每次被调用的次数不超过 $log N$,因此总的时间复杂度为 $O(NlogN)$,其中 $N$ 为 树的节点总数。

    空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 $O(h)$,其中 $h$ 为树的高度。

    108. 将有序数组转换为二叉搜索树(简单)

    108 和 109 基本是一样的,只不过数据结构不一样,109 变成了链表了而已。由于链表操作比数组需要考虑更多的因素,因此 109 是 中等难度。

    题目描述

    将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    示例:

    给定有序数组: [-10,-3,0,5,9],

    一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

    0

    / \

    -3 9

    / /

    -10 5

    思路

    对于这个问题或者 给定一个二叉搜索树,将其改为平衡(后面会讲) 基本思路都是一样的。

    题目的要求是将有序数组转化为:

    高度平衡的二叉树

    二叉搜索树

    由于平衡二叉树是左右两个子树的高度差的绝对值不超过 1。因此一种简单的方法是选择中点作为根节点,根节点左侧的作为左子树,右侧的作为右子树即可。原因很简单,这样分配可以保证左右子树的节点数目差不超过 1。因此高度差自然也不会超过 1 了。

    上面的操作同时也满足了二叉搜索树,原因就是题目给的数组是有序的。

    你也可以选择别的数作为根节点,而不是中点,这也可以看出答案是不唯一的。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

    if not nums: return None

    mid = (len(nums) - 1) // 2

    root = TreeNode(nums[mid])

    root.left = self.sortedArrayToBST(nums[:mid])

    root.right = self.sortedArrayToBST(nums[mid + 1:])

    return root

    复杂度分析

    时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 $O(N)$,其中 $N$ 为数组长度。

    空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 $O(h)$,其中 $h$ 为树的高度。同时由于是平衡二叉树,因此 $h$ 就是 $log N$。

    109. 有序链表转换二叉搜索树(中等)

    题目描述

    `给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    示例:

    给定的有序链表: [-10, -3, 0, 5, 9],

    一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

    0

    / \

    -3 9

    / /

    -10 5

    思路

    和 108 思路一样。 不同的是数据结构的不同,因此我们需要关注的是链表和数组的操作差异。

    417f4a08024c444b43c4aca75073f099.png

    (数组的情况)

    我们再来看下链表:

    8ec5e2235093c589bb2cb7eeab028b79.png

    (链表的情况)

    找到中点,只需要使用经典的快慢指针即可。同时为了防止环的出现, 我们需要斩断指向 mid 的 next 指针,因此需要记录一下中点前的一个节点,这只需要用一个变量 pre 记录即可。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def sortedListToBST(self, head: ListNode) -> TreeNode:

    if not head:

    return head

    pre, slow, fast = None, head, head

    while fast and fast.next:

    fast = fast.next.next

    pre = slow

    slow = slow.next

    if pre:

    pre.next = None

    node = TreeNode(slow.val)

    if slow == fast:

    return node

    node.left = self.sortedListToBST(head)

    node.right = self.sortedListToBST(slow.next)

    return node

    复杂度分析

    时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 $O(N)$,其中 $N$ 为链表长度。

    空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 $O(h)$,其中 $h$ 为树的高度。同时由于是平衡二叉树,因此 $h$ 就是 $log N$。

    1382. 将二叉搜索树变平衡(中等)

    题目描述

    给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。

    如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。

    如果有多种构造方法,请你返回任意一种。

    示例:

    199e0219f41fca7db5dcdabed903baa9.png

    输入:root = [1,null,2,null,3,null,4,null,null]

    输出:[2,1,3,null,null,null,4]

    解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。

    提示:

    树节点的数目在 1 到 10^4 之间。

    树节点的值互不相同,且在 1 到 10^5 之间。

    思路

    由于二叉搜索树的中序遍历是一个有序数组,因此问题很容易就转化为 108. 将有序数组转换为二叉搜索树(简单)。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:

    def inorder(self, node):

    if not node: return []

    return self.inorder(node.left) + [node.val] + self.inorder(node.right)

    def balanceBST(self, root: TreeNode) -> TreeNode:

    nums = self.inorder(root)

    def dfs(start, end):

    if start == end: return TreeNode(nums[start])

    if start > end: return None

    mid = (start + end) // 2

    root = TreeNode(nums[mid])

    root.left = dfs(start, mid - 1)

    root.right = dfs(mid + 1, end)

    return root

    return dfs(0, len(nums) - 1)

    复杂度分析

    时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 $O(N)$,其中 $N$ 为链表长度。

    空间复杂度:虽然使用了递归,但是瓶颈不在栈空间,而是开辟的长度为 $N$ 的 nums 数组,因此空间复杂度为 $O(N)$,其中 $N$ 为树的节点总数。

    总结

    本文通过四道关于二叉平衡树的题帮助大家识别此类型题目背后的思维逻辑,我们来总结一下学到的知识。

    平衡二叉树指的是:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

    如果需要让你判断一个树是否是平衡二叉树,只需要死扣定义,然后用递归即可轻松解决。

    如果需要你将一个数组或者链表(逻辑上都是线性的数据结构)转化为平衡二叉树,只需要随便选一个节点,并分配一半到左子树,另一半到右子树即可。

    同时,如果要求你转化为平衡二叉搜索树,则可以选择排序数组(或链表)的中点,左边的元素为左子树, 右边的元素为右子树即可。

    小提示 1: 如果不需要是二叉搜索树则不需要排序,否则需要排序。

    小提示 2: 你也可以不选择中点, 算法需要相应调整,感兴趣的同学可以试试。

    小提示 3: 链表的操作需要特别注意环的存在。

    更多相关内容
  • 2.7二叉排序树的操作-生成 2.8二叉排序树的操作-删除 2.8.1删除节点要考虑的两点 2.8.2若被删除结点节点为叶子节点 ​ 2.8.3若被删除节点只有左子树或只有右子树 2.8.4若被删除节点既有左子树又有右子树 2.8.5...

    目录

    1、为什么要用树表查询

    ​ 2、二叉排序树

    2.1二叉排序树的定义

    2.2二叉排序树的操作-查找

    2.3用二叉链表存储二叉排序树

    2.4二叉排序树递归查找的算法与思想

    2.5二叉排序树的查找分析

    2.6二叉排序树的操作-插入

    2.7二叉排序树的操作-生成

    2.8二叉排序树的操作-删除

     2.8.1删除节点要考虑的两点

     2.8.2若被删除结点节点为叶子节点

    ​ 2.8.3若被删除节点只有左子树或只有右子树

     2.8.4若被删除节点既有左子树又有右子树

     2.8.5 三种情况删除的例子

    3、平衡二叉树

    3.1为什么要用平衡二叉树

    3.2平衡二叉树的定义

    3.3平衡二叉树失衡的调整

    3.3.1四种失衡二叉排序树的具体过程

     3.4给出数值构造平衡二叉树的例题


    1、为什么要用树表查询

    2、二叉排序树

    2.1二叉排序树的定义

     注意子树左边是小于,而右边是大于等于。

    2.2二叉排序树的操作-查找

    2.3用二叉链表存储二叉排序树

     一个数据域,两个左右孩子节点

    2.4二叉排序树递归查找的算法与思想

    2.5二叉排序树的查找分析

    不同的二叉排序树平均查找长度的例子:

     

     

     

    2.6二叉排序树的操作-插入

     此时不用考虑效率平衡的问题,只需要不断地查找知道某个叶子结点的左子树或右子树为空,节点为该叶子节点的左孩子或右孩子

    2.7二叉排序树的操作-生成

     

    2.8二叉排序树的操作-删除

     2.8.1删除节点要考虑的两点

    1.要保证删除后的重新连接的二叉树还是二叉排序树,中序遍历后还是一个递增的有序序列

    2.要保证重新连接的而二叉树树的高度不能增加

    2.8.2若被删除结点节点为叶子节点

    2.8.3若被删除节点只有左子树或只有右子树

     2.8.4若被删除节点既有左子树又有右子树

     因为要满足二叉排序树的中序排列必须是递增的有序序列,所以用中序遍历的前驱节点或后继节点来代替它,中序遍历的前驱节点是左子树中最大的节点,中序遍历的后继节点是右子树中最小的节点。

    2.8.5 三种情况删除的例子:

    3、平衡二叉树

    3.1为什么要用平衡二叉树

    为了提高二叉排序树的查找效率,所以要对二叉排序树进行平衡化处理

    3.2平衡二叉树的定义

     

     

    3.3平衡二叉树失衡的调整

    最小失衡子树根节点是说子根是最少的失衡的节点。

     

     按照中序遍历的顺序,把数值排序第二的节点作为根节点,然后在保持二叉树的特性就OK了。

    3.3.1四种失衡二叉排序树的具体过程

     LL型,RR型,RL型,LR型是根据最小失衡子树根节点来作为判断的,LL就是左子树的左子树插入一个节点造成失衡,但是不一定是根节点必须移动。

     

     

     

     因为此时是7节点为最小失衡子树的根节点,所以此时为RL型,此时就应该选择中间的9节点作为7与11的根节点,最后把插入的8节点作为7节点的右子树

     

     3.4给出数值构造平衡二叉树的例题

     

     

     

    展开全文
  • 平衡二叉排序树(完整案例详解及完整C代码实现)

    千次阅读 多人点赞 2020-08-17 21:19:45
    写在前面:博主是一位普普通通的19届双非软工在读生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想...平衡二叉树简介 2.二叉排序.

    写在前面:博主是一位普普通通的19届双非软工在读生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习,在记录知识的同时获得部分浏览量,得到更多人的认可,满足小小的成就感,同时在写博客的途中结交更多志同道合的朋友,让自己在技术的路上并不孤单。

    目录:
    1.平衡二叉树简介
    2.二叉排序树转换平衡为平衡二叉树
    3.不平衡因子的四种情况
    4.构建平衡二叉树的代码实现

    1.平衡二叉树简介

    平衡二叉树,又称为 AVL 树。实际上就是遵循以下两个特点的二叉树:

    • 每棵子树中的左子树和右子树的深度差不能超过 1;
    • 二叉树中每棵子树都要求是平衡二叉树;

    其实就是在二叉树的基础上,若树中每棵子树都满足其左子树和右子树的深度差都不超过 1,则这棵二叉树就是平衡二叉树。

    如下图所示,其中 (a) 的两棵二叉树中由于各个结点的平衡因子数的绝对值都不超过 1,所以 (a) 中两棵二叉树都是平衡二叉树;而 (b) 的两棵二叉树中有结点的平衡因子数的绝对值超过 1,所以都不是平衡二叉树。
    在这里插入图片描述

    平衡因子:每个结点都有其各自的平衡因子,表示的就是其左子树深度同右子树深度的差。平衡二叉树中各结点平衡因子的取值只可能是:0、1 和 -1。

    2.二叉排序树转换平衡为平衡二叉树

    为了排除动态查找表中不同的数据排列方式对算法性能的影响,需要考虑在不会破坏二叉排序树本身结构的前提下,将二叉排序树转化为平衡二叉树。

    例如,使用上一节的算法在对查找表{13,24,37,90,53}构建二叉排序树时,当插入 13 和 24 时,二叉排序树此时还是平衡二叉树:
    在这里插入图片描述

    当继续插入 37 时,生成的二叉排序树如下图 (a),平衡二叉树的结构被破坏,此时只需要对二叉排序树做“旋转”操作(如下图 (b)),即整棵树以结点 24 为根结点,二叉排序树的结构没有破坏,同时将该树转化为了平衡二叉树:

    在这里插入图片描述
    当二叉排序树的平衡性被打破时,就如同扁担的两头出现了一头重一头轻的现象,如下图(a)所示,此时只需要改变扁担的支撑点(树的树根),就能使其重新归为平衡。实际上图b中的 (b) 是对(a) 的二叉树做了一个向左逆时针旋转的操作。

    继续插入 90 和 53 后,二叉排序树如下图(a)所示,导致二叉树中结点 24 和 37 的平衡因子的绝对值大于 1 ,整棵树的平衡被打破。此时,需要做两步操作:

    1. 如下图(b) 所示,将结点 53 和 90 整体向右顺时针旋转,使本该以 90 为根结点的子树改为以结点 53 为根结点;
    2. 如下图 (c) 所示,将以结点 37 为根结点的子树向左逆时针旋转,使本该以 37 为根结点的子树,改为以结点 53 为根结点;

    在这里插入图片描述做完以上操作,即完成了由不平衡的二叉排序树转变为平衡二叉树。

    3.不平衡因子的四种情况

    1.单向右旋平衡处理:若由于结点 a 的左子树为根结点的左子树上插入结点,导致结点 a 的平衡因子由 1 增至 2,致使以 a 为根结点的子树失去平衡,则只需进行一次向右的顺时针旋转,如下图这种情况:

    在这里插入图片描述

    2.单向左旋平衡处理:如果由于结点 a 的右子树为根结点的右子树上插入结点,导致结点 a 的平衡因子由 -1变为 -2,则以 a 为根结点的子树需要进行一次向左的逆时针旋转,如下图这种情况:

    在这里插入图片描述

    3.双向旋转(先左后右)平衡处理:如果由于结点 a 的左子树为根结点的右子树上插入结点,导致结点 a 平衡因子由 1 增至 2,致使以 a 为根结点的子树失去平衡,则需要进行两次旋转操作,如下图这种情况:

    在这里插入图片描述

    上图中插入结点也可以为结点 C 的右孩子,则(b)中插入结点的位置还是结点 C 右孩子,(c)中插入结点的位置为结点 A 的左孩子。

    4.双向旋转(先右后左)平衡处理:如果由于结点 a 的右子树为根结点的左子树上插入结点,导致结点 a 平衡因子由 -1 变为 -2,致使以 a 为根结点的子树失去平衡,则需要进行两次旋转(先右旋后左旋)操作,如下图这种情况:

    在这里插入图片描述

    上图中插入结点也可以为结点 C 的右孩子,则(b)中插入结点的位置改为结点 B 的左孩子,(c)中插入结点的位置为结点 B 的左孩子

    4.构建平衡二叉树的代码实现

    #include <stdio.h>
    #include <stdlib.h>
    //分别定义平衡因子数
    #define LH +1
    #define EH  0
    #define RH -1
    typedef int ElemType;
    typedef enum {false,true} bool;
    //定义二叉排序树
    typedef struct BSTNode{
        ElemType data;
        int bf;//balance flag
        struct BSTNode *lchild,*rchild;
    }*BSTree,BSTNode;
    //对以 p 为根结点的二叉树做右旋处理,令 p 指针指向新的树根结点
    void R_Rotate(BSTree* p)
    {
        //借助文章中的图 5 所示加以理解,其中结点 A 为 p 指针指向的根结点
        BSTree lc = (*p)->lchild;
        (*p)->lchild = lc->rchild;
        lc->rchild = *p;
        *p = lc;
    }
    对以 p 为根结点的二叉树做左旋处理,令 p 指针指向新的树根结点
    void L_Rotate(BSTree* p)
    {
        //借助文章中的图 6 所示加以理解,其中结点 A 为 p 指针指向的根结点
        BSTree rc = (*p)->rchild;
        (*p)->rchild = rc->lchild;
        rc->lchild = *p;
        *p = rc;
    }
    //对以指针 T 所指向结点为根结点的二叉树作左子树的平衡处理,令指针 T 指向新的根结点
    void LeftBalance(BSTree* T)
    {
        BSTree lc,rd;
        lc = (*T)->lchild;
        //查看以 T 的左子树为根结点的子树,失去平衡的原因,如果 bf 值为 1 ,则说明添加在左子树为根结点的左子树中,需要对其进行右旋处理;反之,如果 bf 值为 -1,说明添加在以左子树为根结点的右子树中,需要进行双向先左旋后右旋的处理
        switch (lc->bf)
        {
            case LH:
                (*T)->bf = lc->bf = EH;
                R_Rotate(T);
                break;
            case RH:
                rd = lc->rchild;
                switch(rd->bf)
            {
                case LH:
                    (*T)->bf = RH;
                    lc->bf = EH;
                    break;
                case EH:
                    (*T)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    lc->bf = LH;
                    break;
            }
                rd->bf = EH;
                L_Rotate(&(*T)->lchild);
                R_Rotate(T);
                break;
        }
    }
    //右子树的平衡处理同左子树的平衡处理完全类似
    void RightBalance(BSTree* T)
    {
        BSTree lc,rd;
        lc= (*T)->rchild;
        switch (lc->bf)
        {
            case RH:
                (*T)->bf = lc->bf = EH;
                L_Rotate(T);
                break;
            case LH:
                rd = lc->lchild;
                switch(rd->bf)
            {
                case LH:
                    (*T)->bf = EH;
                    lc->bf = RH;
                    break;
                case EH:
                    (*T)->bf = lc->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    lc->bf = LH;
                    break;
            }
                rd->bf = EH;
                R_Rotate(&(*T)->rchild);
                L_Rotate(T);
                break;
        }
    }
    
    int InsertAVL(BSTree* T,ElemType e,bool* taller)
    {
        //如果本身为空树,则直接添加 e 为根结点
        if ((*T)==NULL)
        {
            (*T)=(BSTree)malloc(sizeof(BSTNode));
            (*T)->bf = EH;
            (*T)->data = e;
            (*T)->lchild = NULL;
            (*T)->rchild = NULL;
            *taller=true;
        }
        //如果二叉排序树中已经存在 e ,则不做任何处理
        else if (e == (*T)->data)
        {
            *taller = false;
            return 0;
        }
        //如果 e 小于结点 T 的数据域,则插入到 T 的左子树中
        else if (e < (*T)->data)
        {
            //如果插入过程,不会影响树本身的平衡,则直接结束
            if(!InsertAVL(&(*T)->lchild,e,taller))
                return 0;
            //判断插入过程是否会导致整棵树的深度 +1
            if(*taller)
            {
                //判断根结点 T 的平衡因子是多少,由于是在其左子树添加新结点的过程中导致失去平衡,所以当 T 结点的平衡因子本身为 1 时,需要进行左子树的平衡处理,否则更新树中各结点的平衡因子数
                switch ((*T)->bf)
                {
                    case LH:
                        LeftBalance(T);
                        *taller = false;
                        break;
                    case  EH:
                        (*T)->bf = LH;
                        *taller = true;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = false;
                        break;
                }
            }
        }
        //同样,当 e>T->data 时,需要插入到以 T 为根结点的树的右子树中,同样需要做和以上同样的操作
        else
        {
            if(!InsertAVL(&(*T)->rchild,e,taller))
                return 0;
            if (*taller)
            {
                switch ((*T)->bf)
                {
                    case LH:
                        (*T)->bf = EH;
                        *taller = false;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = true;
                        break;
                    case  RH:
                        RightBalance(T);
                        *taller = false;
                        break;
                }
            }
        }
        return 1;
    }
    //判断现有平衡二叉树中是否已经具有数据域为 e 的结点
    bool FindNode(BSTree root,ElemType e,BSTree* pos)
    {
        BSTree pt = root;
        (*pos) = NULL;
        while(pt)
        {
            if (pt->data == e)
            {
                //找到节点,pos指向该节点并返回true
                (*pos) = pt;
                return true;
            }
            else if (pt->data>e)
            {
                pt = pt->lchild;
            }
            else
                pt = pt->rchild;
        }
        return false;
    }
    //中序遍历平衡二叉树
    void InorderTra(BSTree root)
    {
        if(root->lchild)
            InorderTra(root->lchild);
       
        printf("%d ",root->data);
       
        if(root->rchild)
            InorderTra(root->rchild);
    }
    
    int main()
    {
        int i,nArr[] = {1,23,45,34,98,9,4,35,23};
        BSTree root=NULL,pos;
        bool taller;
        //用 nArr查找表构建平衡二叉树(不断插入数据的过程)
        for (i=0;i<9;i++)
        {
            InsertAVL(&root,nArr[i],&taller);
        }
        //中序遍历输出
        InorderTra(root);
        //判断平衡二叉树中是否含有数据域为 103 的数据
        if(FindNode(root,103,&pos))
            printf("\n%d\n",pos->data);
        else
            printf("\nNot find this Node\n");
        return 0;
    }
    

    本篇博客转载C语言中文网

    展开全文
  • 因本人最近在恶补数据结构与算法,学识经验有限...根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。 #Definitionforabinarytreenode. #classTreeNode: #de...

    因本人最近在恶补数据结构与算法,学识经验有限,如有不正之处望读者指正,不胜感激;也望借此平台留下学习笔记以温故而知新。这一篇博客主要是剑指offer上面关于树的数据结构的面试题,希望对您有所帮助。

    剑指offer-二叉树经典例题

    • 二叉树的镜像

    递归法

    根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个节点的左 / 右子节点,即可生成二叉树的镜像。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def mirrorTree(self, root: TreeNode) -> TreeNode:
            if root is None: return
            root.left, root.right = root.right, root.left 
            self.mirrorTree(root.left)
            self.mirrorTree(root.right)
            return root
    • 对称的二叉树

    解题思路:

    对称二叉树定义: 对于树中 任意两个对称节点 L 和 R ,一定有:

    L.val = R.val:即此两对称节点值相等。

    L.left.val = R.right.val:即 L 的 左子节点 和 R 的 右子节点 对称;

    L.right.val = R.left.val:即 L 的 右子节点 和 R 的 左子节点 对称。

    根据以上规律,考虑从顶至底递归,判断每对节点是否对称,从而判断树是否为对称二叉树。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def isSymmetric(self, root: TreeNode) -> bool:
            def isSym(leftnode: TreeNode, rightnode: TreeNode):
                if not leftnode and not rightnode:
                    return True
                
                if not leftnode or not rightnode or leftnode.val != rightnode.val:
                    return False
                return isSym(leftnode.left, rightnode.right) and isSym(leftnode.right, rightnode.left)
            return isSym(root, root)
    
    • 从上到下打印二叉树

    解法1:

    将二叉树广度优先问题转化成队列问题,并使用Python中popleft达到O(1)的时间复杂度

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if not root: return []
            res = []
            queue = collections.deque()
            queue.append(root)
            while(queue):
                temp = []
                for _ in range(len(queue)):
                    node = queue.popleft()
                    temp.append(node.val)
                    if node.left: queue.append(node.left)
                    if node.right: queue.append(node.right)
                res.append(temp)
            return res
    

    解法2:

    将二叉树遍历使用迭代算法进行,时间复杂度为O(logn)

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if not root: return []
            res = []
            def recur(root, depth):
                if len(res) == depth:
                    res.append([])
                res[depth].append(root.val)
                if root.left: recur(root.left, depth+1)
                if root.right: recur(root.right, depth+1)
            
            recur(root, 0)
            return res 
    
    • 二叉搜索树的第k大节点

    解题思路:

    基于性质:二叉搜索树的中序遍历为 递增序列 ,即:求 “二叉搜索树第 k大的节点” 可转化为求 “此树的中序遍历倒序的第 k个节点”。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def kthLargest(self, root: TreeNode, k: int) -> int:
            
            def df(root):
                if not root or self.k == 0: return 
                df(root.right)
                self.k -= 1
                if self.k == 0: self.res = root.val
                df(root.left)
                
            self.k = k
            df(root)
            return self.res
    
    • 二叉树的深度

    树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS);

    常见的 DFS : 先序遍历、中序遍历、后序遍历;

    常见的 BFS : 层序遍历(即按层遍历)。

    方法一:后序遍历(DFS)

    树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现,本文使用递归实现。

    关键点: 此树的深度和其左(右)子树的深度之间的关系。显然,此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if not root: return 0
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
    

    方法二:层序遍历(BFS)

    树的层序遍历 / 广度优先搜索往往利用 队列 实现。

    关键点: 每遍历一层,则计数器 +1+1 ,直到遍历完成,则可得到树的深度。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def maxDepth(self, root: TreeNode) -> int:
            if not root: return 0
            queue, res = [root], 0
            while queue:
                tmp = []
                for node in queue:
                    if node.left: tmp.append(node.left)
                    if node.right: tmp.append(node.right)
                queue = tmp
                res += 1
            return res
    
    
    • 平衡二叉树

    基本思路:

    是构造一个获取当前子树的深度的函数 depth(root) ,通过比较某子树的左右子树的深度差 abs(depth(root.left) - depth(root.right)) <= 1 是否成立,来判断某子树是否是二叉平衡树。若所有子树都平衡,则此树平衡。

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            if not root: return True
            return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
                self.isBalanced(root.left) and self.isBalanced(root.right)
        def depth(self, root):
            if not root: return 0
            return max(self.depth(root.left), self.depth(root.right)) + 1
    
    

    • 参考资料:

    LeetCode博主:力扣

    展开全文
  • title: 平衡二叉树(AVL) date: 2020-01-14 11:26:36 tags: 数据结构 1.1平衡二叉树的定义 为了解决二叉查找树如果插入的顺序不合适,会导致二叉查找树变成一个单链(可以看二叉查找树文章当中的讨论),例如按照递增...
  • 【说明】:博客内容选自课程课件 已知长度为12的表:  (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec) ...2.按表中元素的顺序依次插入生成一颗二叉排序树(初始为空),并求其在等概率的情况下...
  • 树,二叉树,森林有关习题

    千次阅读 2018-12-22 23:18:15
    1.已知一棵有2011个结点的树,其叶节点个数为116,该树对应的二叉树中无右孩子的结点个数是 A)115 B)116 C)1895 D)1896 [解析]  树——&gt;二叉树,最左孩子变左孩子,兄弟变右孩子 因此对应的二叉树没有右...
  • 二分查找 https://www.cnblogs.com/longyunfeigu/p/9316082.html 散列表 python的dict 二叉树 堆 python的heapq 字符串匹配 图 贪心、分治、回溯和动态规划
  • 左子树和右子树又各是一棵二叉排序树,二叉排序树可用于元素的排序、搜索 平衡二叉树:树上任一结点的左子树和右子树的深度之差不超过1,平衡二叉树能有更高的搜索效率 二叉树的性质 二叉树的常考性质 常见考点1: 设...
  • 二叉树算法题汇总

    2022-05-03 20:28:50
    判断是不是平衡二叉树 2.输出二叉树中和为某一值的全部路径(1) 3.输出二叉树中和为某一值的全部路径(2) 二、适用BFS(借助队列) 1. 从上往下打印二叉树(不分行) 2. 从上往下打印二叉树(分行) 前言 更新算法题的...
  • 第五章 树与二叉树 从本章开始学习非线性数据结构,树作为一类重要的一对多的数据结构的代表,以分支结构关系定义层次结构,在现实生活中很多关系都可以用树形结构表示,其中二叉树更是最常出现的一种表现方式。 ...
  • 1、二叉排序树定义 ...题目:现有10 个元素 (54,28,16,34,73,62,95,60,26,43) ,按照依次插入的方法生成一棵二叉排序树,查找值为 62 的结点所需比较次数为()。 解:如下图依次生成二叉排序树 ...
  • 搜索二叉树 搜索二叉树:对于搜索二叉树的任何...具备平衡性的搜索二叉树: AVL树——平衡性最严格 任何一个节点的左子树和右子树高度差不大于1,复杂度还是O(logN)。导致调整非常频繁。 红黑树——平衡性要求不严格...
  • 二叉树和递归

    2020-04-10 20:58:52
    二叉树的天然递归结构 1. 二叉树的最大深度 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 使用一个递归可以轻松解决,那么...
  • 5.2 二叉树

    2021-10-27 14:39:05
    5.2 二叉树 比起紫书上二叉树的基础知识,黑书拓展了一些特殊的树形结构。 5.2.1 二叉树的存储 二叉树的基本概念就不再多做介绍,对一些用语不太明白的详见紫书6.3 树和二叉树。 关于二叉树的存储结构,一般用指针...
  • 力扣LeetCode-二叉树

    2022-02-16 21:30:09
    二叉树 基本知识 1. 二叉树的递归遍历 前序遍历 class Solution { public: void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中 ...
  • 本文是递归算法系列文的第7篇,依然沿着递归的脉络,介绍了常常运用递归处理问题的一个典型数据结构——二叉树。分析总结了LeetCode中的相关习题在解法上的思路和模板。 本文内容如下: 树的前、中、后序、层次遍历...
  • NEEPAlgorithms 《王道机试指南》和《算法笔记》(“晴神宝典”)例题题解
  • PS:rd的比较问题 例题:普通平衡树 题目 代码实现 真的太难了,刚开始是直接用模板不断A题,其实自己根本不是很理解,于是今天放弃了刷题时间,理解并背诵了这个模板,写了这篇blog 二叉查找树BST(Binary Search ...
  • leetcode二叉树

    2019-04-08 21:44:54
    二叉树:如果树中的每个节点最多有两个子节点,我们说该树是一个二叉树。 1.列表表示的树 在列表树的列表中,将根节点的值存储为列表的第一个元素;第二个元素:一个表示左子树的列表;第三个元素:表示右子树的另一...
  • 树与二叉树 叶子结点(无后继) 1. 树的基本概念 1.1 树的定义 递归定义: 树是由n >= 0个结点组成的有穷集合(不妨用符号D表示)以及结点之间关系组成的集合构成的结构,记为T。 当n=0时,称T为空树。 在任何一棵...
  • 版权声明 本文非纯粹原创,是综合了多位作者的资料融合而成的学习笔记。部分图片也来源于其他文章。...常见的数据结构,因此衍生的数据结构有平衡二叉树,红黑树,Btree,B+tree。 二叉树结构体 struct tree
  • 平衡二叉树 平衡二叉树又被称为AVL树,它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 二叉排序树:是一棵空树,或者:若它...
  • 数据结构与算法基础内容提要数组与矩阵线性表广义表树与二叉树图排序与查找算法基础及常见的算法数组数组类型:存储地址计算一维数组a[n]:a[i]的存储地址为:a+i*len二维数组a[m][n]:a[i][j]的存储地址(按行存储)...
  • [算法系列]递归应用——二叉树(2):一种带信息递归返回的求解方式 本文是递归系列文的第七篇,和上篇文章类似,介绍BinaryTree的解题思路。这里介绍一种和“遍历”行为类似的,自下而上递归返回信息的解题思路。其...
  • 树和二叉树树的定义树和二叉树的相关概念树的分类二叉树的重要性质 树的定义 树(tree)是包含n(n≥1)n(n\geq 1)n(n≥1)个结点,(n−1)(n-1)(n−1)条边的有穷集,其中: (1)每个元素称为结点(node); (2)有一...
  • 直接得出: 根据数组建立平衡二叉搜索树 java整体打印二叉树 判断平衡二叉树 判断完全二叉树 判断二叉搜索树 二叉搜索树实现 堆的简单实现 堆应用例题三连 一个数据流中,随时可以取得中位数。 金条 项目最大收益...
  • 树是数据结构中的重中之重,尤其以各类二叉树为学习的难点。一直以来,对于树的掌握都是模棱两可的状态,现在希望通过写一个关于二叉树的专题系列。 1重点名词 1.1 结点 结点是数据结构中的基础,是构成复杂数据结构...
  • 提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里可以添加本文要记录的大概内容: ...
  • 数据结构第9章例题与答案

    千次阅读 2021-01-12 02:59:31
     在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为a,并已知a的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。【合肥工业大学 2001 一、4 (2分)】 a. ll b. lr c...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 956
精华内容 382
关键字:

生成平衡二叉树例题