首页 / 算法 / 树,二叉树和算法总结
树,二叉树和算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了树,二叉树和算法总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1360字,纯文字阅读大概需要2分钟。
内容图文
一.思维导图
二.概念笔记
树的存储结构
双亲表示法:当算法中需要在树结构中频繁地查找某结点的父结点时,使用双亲表示法最合适
孩子表示法:适用于查找某结点的孩子结点
孩子兄弟表示法:可以用孩子兄弟表示法将普通树转化为二叉树
二叉树的性质
性质一: 在二叉树的第k层上最多有2^(k-1)个结点
性质二: 高度为k的二叉树至多有2^k-1个结点,最少有k个结点
性质三: 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1
性质四: 有n个结点的完全二叉树的高度为 $log_2{n}+1$
查找的时间复杂度
顺序查找: O(n)
二分查找: O($log_2{n}$)
前者为线性查找,后者需要线性表是有序的,时间复杂度降低了一个数量级,效率更高
二叉排序树的删除:
- 当所删除的节点为叶子节点时,直接删除即可
- 当仅有左或右子树的节点时,只需要上移其子树,取代被删除结点的位置
- 当节点为左右子树都有的节点,删除节点的直接前驱或者直接后继来替换当前节点,调整直接前驱或者直接后继的位置
哈夫曼树
路径:在一棵树中,一个结点到另一个结点之间的通路
路径长度:在一条路径中,每经过一个结点,路径长度都要加1
结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权
结点的带权路径长度:指从根结点到该结点之间的路径长度与该结点的权的乘积
哈夫曼编码就是在哈夫曼树的基础上构建的,这种编码方式最大的优点就是用最少的字符包含最多的信息内容。
哈希表
优点:能够在常数级的时间复杂度上进行查找,并且插入数据和删除数据简单。
缺点:不支持排序,一般比用线性表存储需要更多时间,并且记录的关键字不能重复,当关键字重复就会产生数据冲突。
冲突处理
线性探测法:使用算术取余的方法计算余数,当产生冲突时就通过线性递增的方法进行探测,一直到数组的位置为空再插入数据项
链地址法:把所有的冲突关键字存储在一个线性链表中,这个链表的散列地址是唯一的
疑难问题及解决方案
当二叉树存在左右孩子结点时的二叉树删除操作,通过百度查找到一下伪代码
DeleteBST(T, key) {
if (T为空) return 0;//空树删除失败
else {
if (key<T->data) {//删除在左子树为key的结点
return DeleteBST(T->lchild, key);
}
else if (key>T->data) {//删除在右子树为key的结点
return DeleteBST(T->rchild, key);
}
else {
if (T->lchild为空) {//只有右子树
p = T;
T = T->rchild;
free(p);
}
else if (T->rchild为空) {//只有左子树
p = T;
T = T->lchild;
free(p);
}
else {//左右子树都有
Delete(T, T->lchild);//调用Delete函数删除结点T
}
}
}
}
原文:https://www.cnblogs.com/bob3000/p/12776440.html
内容总结
以上是互联网集市为您收集整理的树,二叉树和算法总结全部内容,希望文章能够帮你解决树,二叉树和算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。