二叉查找树的效率
在二叉查找树中执行的基本操作的时间与树的高度成正比。最坏情况,
树的高度是N,像链表一样,而较好情况高度是lgN。因此,树的高度是关键。
下一章将要学习的红黑树是对二叉查找树的改进,通过保持树的高度从而
保证红黑树上的操作有很好的效率。
各种遍历算法
中序遍历算法:子树根的关键字在输出时介于左子树和右子树的关键字之间。
即按排列顺序输出树中的所有关键字。
相应的,前序遍历就是子树根的关键字在左右子树之前输出。
在后面的基数树中,前序遍历(而非中序遍历)是二进制串的排序输出。
用递归方式可以很轻松地实现二叉树的遍历。
// 包含卫星数据的二叉树结点定义
struct _BSTNode {
struct _BSTNode *parent, *left, *right;
int key;
char *value;
};
typedef struct _BSTNode BSTNode;
// 中序遍历
void bst_inorder_walk(BSTNode *node)
{
if (node != NULL) {
bst_inorder_walk(node->left);
printf("key: %d, val: %s\n", node->key, node->value);
bst_inorder_walk(node->right);
}
}
非递归实现中序遍历
沿着二叉树的最左结点遍历,逐个入栈,到最左结点后开始出栈。
打印弹出栈的结点的值,并以该结点的右孩子为根结点,继续沿其最左结点处理。
void bst_inorder_walk(BSTNode *node)
{
BSTNode *stack[20];
int top = 0;
while (node || top != 0) {
// Push most-left children to stack
while (node) {
stack[top++] = node;
node = node->left;
}
// Print and continue to handle right child
node = stack[--top];
printf("%d, %s\n", node->key, node->value);
node = node->right;
}
}
分享到:
相关推荐
将有双亲域的二叉链表进行中序遍历的递推式算法
根据算法导论第12章二叉查找树内容编写,有详细的注释和测试程序
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
二叉查找树的插入、删除、遍历和查找等操作的C++实现,二叉查找树采用泛型结构
最近在研究数据结构这本书,自己动手实现的一个二叉查找排序树的类BinSortTree,实现数据的插入,查找,删除,层序遍历,中序遍历等操作,熟悉数据结构的朋友都知道,根据二叉排序树的定义,中序遍历后得到的序列...
算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案
该算法成功解决了二叉排序树的查找(递归和非递归),节点删除,括号表示法输出的问题,算法基本按照数据结构课本的内容来编写,比较适合初学者对二叉排序树的学习,当然改进的空间还很大
科大算法实验2红黑树和二叉查找树 支持彩色打印
在学习算法过程中自己的代码实现,与大家分享交流。版权所有:miracledan
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
设计一个算法程序,使得该程序从二叉检索树中删除一个结点,并仍然保持二叉检索树的特性不变 实验要求: 创建一棵二叉检索树,然后用中序遍历查找要删除的结点的后继结点
运用c语言,贪心算法构造最优二叉查找树。
使用C++实现最优二叉查找树,对正在学习算法的同学应该挺有帮助的
C++编写的查找算法,用二叉排序树查找,是在VC++6.0上实现的
使用链表存储二叉排序树并实现遍历算法 实现CreateTree函数函数原型:btnode *CreateTree (int n)形参说明:n: 节点个数返回值说明:返回树的根节点指针函数功能:构建有n个节点的二叉排序树,第一个节点为根节点,...
最优二叉查找树,包含习题15.5-1算法,为算法导论上的习题。
C#,自平衡二叉查找树(AVL Tree)的算法与源代码 自平衡二叉查找树(AVL Tree)中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL...
单链表的基本操作,二叉树的遍历,折半查找和二叉排序树,内部排序等共四个实验的实现过程。
代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法