发自简书

小结

树由边(直线)连接的节点(圆)组成。

根是树中最顶端的节点;它没有父节点。

二叉树中,节点最多有两个子节点。

二叉搜索树中,所有A节点左边子孙节点的关键字值都比A小;所有右边子孙节点的关键字值都大于(或等于)A。

树执行査找、插入、删除的时间复杂度都是O(logN)。

节点表示保存在树中的数据对象。

程序中通常用节点到子节点的引用来表示边(有时也用到节点的父节点的引用)。

遍历树是按某种顺序访问树中所有的节点。

最简单的遍历方法是前序、中序和后序。

非平衡树是指根左边的后代比右边多,或者相反,右边的后代比左边多。

查找节点需要比较要找的关键字值和节点的关键字值,如果要找节点关键值小就转向那个点的左子节点,如果大就转向右子节点。

插入需要找到要插入新节点的位置并改变它父节点的子字段来指向它
中序遍历按照关键值的升序访问节点。

前序和后序遍历对解析代数表达式是有用的。

如果一个节点没有子节点,删除它只要把它的父节点的子字段置为null即可。

如果一个节点有一个子节点,把它父节点的子字段置为它的子节点就可以删除它。

如果一个节点有两个子节点,删除它要用它的后继来代替它。

A节点的后继是以A的右子节点为根的子树中关键值最小的那个节点。

删除操作中,如果节点有两个子节点,会根据后继是被删节点的右子节点还是被删节点右子节点的左子孙节点出现两种不同的情况。

数组中重复关键字值的节点会产生一些问题,因为只有第一个能被查找到
在计算机存储时可以用数组表示树,不过基于引用的方法更常用。

哈夫曼树是二叉树(但不是二叉搜索树),用于数据压缩算法,这种方法称为哈夫曼编码。

哈夫曼编码中,最经常出现的字符的编码位数最少,很少出现的字符编码位数要多一些。