二叉树
在计算机科学中,树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(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
分享到:
相关推荐
2.binaryTree树 标准的二叉树。 实现了各种算法,增删查改等等
本资源是根据括号表达式来绘制相应的二叉树,其中显示二叉树的基本信息,如:高度,宽度,叶节点,等
数据结构中 二叉树 binaryTree
二叉树的实现,各种方法,构造函数,析构函数,前序遍历,中序遍历,后续遍历,层次序遍历
BinaryTree: 用于学习二叉树的Python库
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
二叉树官方源码,可以通过编译,直接参考使用。不是自己写的,官方资源
这是stanford大学计算机专业一位教授写的,讲得非常清晰透彻,代码用C和Java来实现
二叉树相关操作:判断是否为二叉排序树、完全二叉树、二叉平衡树;翻转二叉树,求树的深度、叶子节点个数,某节点到根节点的路径,两个节点的最近公共节点等等。
关于二叉树的操作,含有二叉树的创建、二叉树的销毁,二叉树的清空,返回二叉树的深度,节点的赋值,返回指定节点的双亲、左孩子、右孩子、左兄弟、右兄弟,左右子树的插入,左右子树的删除,递归算法的前中后序遍历...
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
线索二叉树 线索二叉树(Threaded Binary Tree)是对二叉树的一种优化,目的是使遍历二叉树的过程更加高效。
心希盼 C++ STL 二叉树 详细请看“心希盼 binaryTree.doc”
BinaryTreeSort的java实现,简单的二叉树排序
MFC实现binarytree 实现可视化的二叉树 MFC实现binarytree 实现可视化的二叉树 MFC实现binarytree 实现可视化的二叉树
public BinaryTree findNode(BinaryTree tree ,char sign); /**找所给结点的左子树*/ public BinaryTree lChildren(BinaryTree node); /**找所给结点的右子树*/ public BinaryTree rChildren(BinaryTree node);...
有序二叉树创建 有序二叉树查找 二叉树遍历 有序二叉树删除 类模版实现的有序二叉树
数据结构,关于二叉树建立的方法例子,希望对大家有用处
二叉树C++头文件,包括构造器、析构器、begin()、end()、output()、destroy()、*、!=运算符重载。
九章算法之二叉树与分治法(Binary Tree & Divide Conquer) 多看多思考