`
darrenzhu
  • 浏览: 804810 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

二叉树(Binary Tree)

阅读更多


二叉树
在计算机科学中,树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是,二叉树不是树的特殊情形。在图论中,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后,每个顶点定义了唯一的根结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。

辨析:
尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。   
树和二叉树的2个主要差别:
1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2;   
2. 树的结点无左、右之分,而二叉树的结点有左、右之分。



二叉排序树,二叉搜索树,二叉查找树是同一个概念,不同的称呼而已。
In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree.
二叉排序树(Binary Sort Tree)又称二叉查找树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树

平衡二叉树
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci数列 1是根节点 F(n-1)是左子树的节点数量 F(n-2)是右子数的节点数量。

平衡二叉搜索(排序)树=平衡二叉树+二叉排序树
 我们知道,对于一般的二叉搜索树(Binary Search Tree),其期望高度(即为一棵平衡树时)为log2n,其各操作的时间复杂度(O(log2n))同时也由此而决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,降低它的操作的时间复杂度。   
平衡二叉搜索树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。
  • 大小: 19.6 KB
分享到:
评论

相关推荐

    java-二叉树binaryTree

    在这个"java-二叉树binaryTree"主题中,我们将深入探讨二叉树的实现、操作以及相关的算法。 在Java编程语言中,二叉树可以被表示为一个类,这个类通常包含指向左右子节点的引用,以及可能包含的数据。下面是一个...

    二叉树BinaryTree

    对于压缩包中的 "Binary_Tree" 文件,很可能包含了一些二叉树的实例,可能有不同形状和特性的二叉树,如满二叉树(所有层都是满的,除了最后一层可能不满),完全二叉树(除了最后一层外,所有层都是满的,并且最后...

    二叉树详解 binary tree

    二叉树(Binary Tree)是一种常见的数据结构,由一系列节点组成,每个节点包含左指针、右指针以及数据元素。在二叉树中,“根”指针指向树的最顶层节点,而左、右指针则递归地指向更小的“子树”。一个空指针代表没有...

    BinaryTree二叉树实现

    二叉树是一种重要的数据结构,它在计算机科学中扮演着至关重要的角色,特别是在算法和...在二叉树的`BinaryTree`文件中,可能会包含这些操作的具体实现,通过阅读和理解这些代码,可以深入学习和掌握二叉树的相关知识。

    二叉树官方源码BinaryTree_src

    在给定的“二叉树官方源码BinaryTree_src”中,我们可以找到一系列与二叉树相关的源代码文件,这为理解和实现二叉树提供了宝贵的参考资料。 首先,我们看到一个名为"BinaryTreeDemo.clw"的文件,这可能是项目的工作...

    C#资源库-binarytree

    标题"C#资源库-binarytree"指的是一个使用C#编程语言实现的二叉树数据结构的代码库。在软件开发中,二叉树是一种基础且重要的数据结构,它由节点构成,每个节点最多有两个子节点,通常称为左子节点和右子节点。这种...

    Python-BinaryTree用于学习二叉树的Python库

    "Python-BinaryTree"是一个专门用于学习和操作二叉树的Python库,它提供了方便的API来创建、遍历和操作二叉树。 1. **二叉树的概念与类型** - 二叉树的基本概念:二叉树的每个节点包含一个值、一个指向左子树的...

    Construct Binary Tree from Preorder and Inorder Traversal

    Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树

    BinaryTree二叉树操作相关代码

    二叉树相关操作:判断是否为二叉排序树、完全二叉树、二叉平衡树;翻转二叉树,求树的深度、叶子节点个数,某节点到根节点的路径,两个节点的最近公共节点等等。

    BinaryTree-源码.rar

    【标题】:“BinaryTree-源码.rar”是一个与二叉树相关的源代码压缩包,它可能包含各种二叉树数据结构的实现,如二叉搜索树、平衡二叉树(AVL树或红黑树)或者自定义的二叉树结构。这个压缩包可能为学习数据结构与...

    BinaryTree_demo.zip_DEMO_binary tree_二叉树

    在“BinaryTree_demo.zip”这个压缩包中,包含了一个名为“BinaryTreeDemo.exe”的可执行文件和一个“www.pudn.com.txt”的文本文件。我们可以推测,这个可执行文件可能是用于演示二叉树操作的程序,而文本文件可能...

    binarytree.rar

    二叉树是一种在计算机科学中广泛使用的数据结构,它的每个节点最多有两个子节点,通常称为左子节点和右...解压“binarytree.rar”,查看其中的文件,理解数据结构,并根据给定的描述编写代码,以实现二叉树的前序遍历。

    二叉树的操作/BinaryTree.h

    关于二叉树的操作,含有二叉树的创建、二叉树的销毁,二叉树的清空,返回二叉树的深度,节点的赋值,返回指定节点的双亲、左孩子、右孩子、左兄弟、右兄弟,左右子树的插入,左右子树的删除,递归算法的前中后序遍历...

    leetcode2-BinaryTree:LeetCodeOJ在Python中的二叉树可视化

    BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...

    Simple Binary Tree Class.zip_binary tree_tree

    在IT领域,二叉树(Binary Tree)是一种基础的数据结构,它由节点构成,每个节点最多有两个子节点,通常称为左子节点和右子节点。这个压缩包"Simple Binary Tree Class.zip"包含了实现简单二叉树类的相关文件,包括...

    线索二叉树(Threaded Binary Tree)是对二叉树的一种优化,目的是使遍历二叉树的过程更加高效

    线索二叉树 线索二叉树(Threaded Binary Tree)是对二叉树的一种优化,目的是使遍历二叉树的过程更加高效。

    binary tree C语言算法

    在计算机科学中,二叉树(Binary Tree)是一种数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。这种数据结构广泛应用于各种算法和问题解决,如搜索、排序、文件系统等。在C语言中实现二叉树,我们...

    BinaryTreeSort

    BinaryTreeSort的java实现,简单的二叉树排序

    心希盼 C++ STL binaryTree

    对于“心希盼 binaryTree.doc”文档,很可能是对这种使用STL实现二叉树的详细教程或示例代码,可能涵盖了如何构建二叉树、执行各种操作以及解决实际问题的实例。通过阅读和理解这份文档,开发者能够深入理解如何结合...

    binaryTree

    在"binaryTree"文件中,可能包含了不同类型的二叉树操作的代码示例,如创建、插入、删除、遍历等。 6. **二叉树的复杂度分析**: - 时间复杂度:二叉树的搜索、插入和删除操作的时间复杂度在最坏情况下可能达到O(n...

Global site tag (gtag.js) - Google Analytics