剑指Offer面试题27题:二叉搜索树与双向链表 题目描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 例如: 调整之后,节点的left指针相当于链表中的pred指针,
【OJ】二叉搜索树转换为有序双向链表

剑指Offer面试题27题:二叉搜索树与双向链表 题目描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 例如: 调整之后,节点的left指针相当于链表中的pred指针,
红黑树也是一种平衡二叉树,但并不像AVL那样严格。红黑树有一些等价的表述,其中比较流行的就是给结点染上红色或黑色。下面是一棵红黑树。 红黑树满足4条性质: 1. 根结点是黑色的(如果不是空树) 2. 外部结点是黑色的(外部结点是把NULL指
伸展树也是一种平衡二叉搜索树,但它的平衡是在平均意义下的。伸展树中n次操作,每次的均摊复杂度是O(logn) 。而单独的一次操作,可能达到O(n)的复杂度。那么,与AVL相比,伸展树的优势又在哪里呢? 伸展树中,每次会把访问到的结点通过单旋
一般的二叉搜索树的高度并没有得到有效限制,在极端情况下,他甚至可以退化为一个链表。而对树高进行限制以达到O(logn)高度的二叉搜索树,又称为平衡搜索树。AVL树是最先发明的自平衡二叉查找树,它的名字来源于它的发明者 G.M. Adelso
本文包含二叉树数据结构的完整实现以及简单演示,二叉树具有属性查看、连接、删除、遍历等多个接口,还增加直观显示接口。