0%

二叉树学习笔记(未完待续)

摘要

二叉树学习笔记(未完待续)。

博客

IT老兵驿站

前言

昨天(2019-11-07)复习红黑树,发现红黑树和二叉树密不可分,所以这里再复习一下二叉树。

在大学的时候,这块我很认真地学习了一遍。
大学毕业后,因为找工作的缘故,我又多次对这块进行过认真的学习,对于这块,心里还是比较清楚的。

现在这个笔记呢,既复习一下知识和概念,也回顾总结一下很多经历过的事情。

正文

定义

参考维基百科

二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:


若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。

对于定义,这里面会隐含一些理解上需要打通的问题,例如树的高度和叶子的关系,这也是经常出现在面试题里面的一个问题。今天事情有点多,先不做这块的总结了。

遍历

二叉树的遍历分为前序遍历、中序遍历、后序遍历,这个前中后是以输出根结点关键字的顺序来区别的。

note:二叉树的遍历涉及到了一个很关键的计算机算法,递归算法,对这个算法,原本一直有点畏惧,一直没有搞清楚。在05年去OpenTV面试的时候,被这个算法给难住了,痛定思痛,那次面试失利之后,对这个算法进行了深度的学习和研究,后来在实际工作中,在合理的时机,也尝试使用了这个算法,现在算是基本掌握了,所以很多事情,躲是躲不开的。

每个结点的内容(摘抄自《算法导论》,这里用的是“结点”):

其中每个结点就是一个对象。除了 key 和卫星数据之外,每个结点还包含属性 left、right 和 p,它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在,则相应属性的值为 NIL。

在这里插入图片描述
发现《算法导论》这里居然印错了,不知道家里面那个纸版的,是不是也是这样,这是第三版了,还会有这样的错误,不应该。

总结

今天暂时写到这里,未完待续……

参考

https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9