源码学院-算法与数据结构树二叉搜索

1、树、二叉树和二叉搜索树树的定义及相关术语二叉树目录二叉搜索树树的定义和术语树的定义(递归定义) ： 有n个节点的树有多少条边？(n-1)树是n(n0)个结点的有限集：若 n = 0，称为空树若 n 0，则有且仅有一个特定的称为根的结点；当n 1时，除根以外的其他结点划分为m(m0) 个互不相交的有限集T1, T2, Tm，其中每一个集合本身又是一棵树，并且称为根的子树结点的度：该结点的子树数目树的度：树中各结点度数的最大值叶子: 所有子树皆为空的节点父结点（从根到当前节点的路径上的离当前节点最近的节点）、儿子结点兄弟结点祖先结点：从根结点到该结点的路径上所有结点层次、高度：null为0, ma

2、x(subtree) + 1有序树：规定所有结点的儿子结点次序，否则为无序树森林： m = 0 棵互不相交树的集合ABCDEFGHIL 高度为 4 、度为 3 的树BELABCDEFGHILN个节点的树会有多少条边？N-1树的定义及相关术语二叉树目录二叉搜索树二叉树二叉树的定义(递归定义)空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树特点：每个结点至多只有两棵子树，子树有左右之分例：结点总数为 3 时的所有二叉树的树的形状 N个节点构成多少棵不同的二叉树？BCDEFL例： 二叉树 B二叉树的性质性质1：在二叉树的第 i 层上至多有 2i-1个结点BCDEFLA1层：结点个数 21-

3、1=20 个2层：结点个数 22-1=21 个3层：结点个数 23-1=22 个性质2：高度为 k 的二叉树至多有2 k- 1 个结点 （sum(20 + 21 + + 2(k-1)性质3：二叉树的叶子结点数 n0 等于度为 2 的结点数 n2 + 1 ?完全二叉树BCDEFLAPSQRUBCDEFLAPSQRXUWV满二叉树: 每层结点 数最多完全二叉树: 1、满二叉树 2、从满二叉树最底层从右向左依次去掉若干结点形成的性质4：具有 n 个结点的完全二叉树高度为 log2n + 1完全二叉树性质5：对一棵有 n 个结点的完全二叉树按照从第一层（根所在的层次到最后一层，并且 每一层都按照从左到

4、右的次序进行编号。根结点的编号为 1，最后一个结点的编号 为 n。 1：对任何一个编号为 i 的结点而言，它的左儿子的编号为 2i( 若 2i = n) ,而右儿子的 编号为 2i+1(若 2i +1 = n)。 2：对任何一个编号为 j 的结点而言，它的父亲结点的的编号为 j/2 。根结点无父结 点。BCDEFLAPSQRU121110987654321i:左子树的编号：2i右子树：2i+1二叉树的顺序存储ABCDEFGHILA 1 -1 B 9 2 C 5 3 D 6 -1 E -1 -1 F -1 -1 G 8 7 H -1 -1I -1 -1L -1 4 0123456789right

5、 leftdata 应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。二叉树的顺序存储 特殊情况：完全二叉树 应用范围：适用于完全二叉树，且结点个数已知。DCGEFBAHILA B CD E F G HI 0123456789L二叉树的顺序存储 特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示： 考虑浪费空间最多的情况，是一种什么情况？ 浪费 2k - 1 k 个单元A B D HI 0123456789DBAHI二叉树的链接存储仅定义结点的类型即可结点之间的关系通过指针实现ABCDEFGHILdata left right标准形式：（二叉链表）广义标准形式

6、：（三叉链表）data left right Parent二叉树的链接存储例：AB/ CDEFGGFDCBAE二叉树遍历设 N 代表根节点，L 代表左子树，R 代表右子树。 a. 前序（或先序）：如果二叉树为空，则操作为空：否则访问根结点；前序遍历左子树； 前序遍历右子树。记为：NLR。 b. 中序： 如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点； 中序遍历右子树。记为：LNR。 c. 后序： 如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子 树；访问根结点。记为：LRN。(非递归，只用一个Stack)前序：A、L、B、E、 C、D、W、XBCDELAXWLRLRRL

7、R中序：B、L、E、A、 C、W、X、D后序：B、E、L、X、 W、D、C、ABCDELAXWBCDELAXWALCDWXBE42713Result: 4, 2, 1,3, 7preorder(4): preorder(2): preorder(1): preorder(null) preorder(null) preorder(3) : preorder(null) preorder(null) preorder(7): preorder(null) preorder(null)42713Result: 2 5curr 74 523142713Result: 5层次遍历Queue Size:

8、 2427135二叉树与递归统计二叉树中叶子结点的数目求树的最大高度求树的节点数量层次遍历树(递归与非递归的方法）树的定义及相关术语二叉树目录二叉搜索树符号 表存储数据Get(Key): 根据Key获得ValueInsert (key, value)Delete(Key)HashMap有序符号 表Key是可比较的，Comparable1. 基于数组实现： 查找时间O(n)，插入O(n)，删除O(n)2.基于有序数组实现：查找O(lgn)，插入O(n), 删除O(n)3.更好的实现? Binary Search Tree 二叉搜索树二叉搜索树 Binary Search Tree（BST）定义：

9、或者是一棵空树；是具有下列性质的二叉树：对于任何一个结点，设其值为K则该结点的 左子树(若不空)的任意一个结点的值都 小于 K；该结点的 右子树(若不空)的任意一个结点的值都 大于 K； 而且它的左右子树也分别为BST性质: 中序遍历是正序的（由小到大的排列）如何判断一个树是不是二叉搜索树？ （自己写写）二叉搜索树 搜索若二叉排序树为空，则查找不成功；否则，若给定值等于根结点的关键字，则查找成功若给定值小于根结点的关键字，则继续在左子树上进行查找若给定值大于根结点的关键字，则继续在 右子树上进行查找 查找37？1， 2， 3， 4， 5：平衡二叉树： AVL、红黑树二叉搜索树 插入首先执行查找

10、算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子将被插结点作为叶子结点插入若二叉树为空。则首先单独生成根结点e.g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结点的关键字值，生成二叉排序树。1223001102809912212299122250991222501109912225030011099输入顺序不同所建立的不同二叉排序树注意122、 99 、 250 、110、300、280 122122999925025011011030028099， 110， 122、 250 、280、300Lgn - n 12299250110300280

11、平衡二叉搜索树lgn红黑树AVL树二叉搜索树 删除 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分为3种情况： 被删除的结点是叶子； 被删除的结点只有左子树或者只有右子树； 被删除的结点既有左子树，也有右子树；503080908540358832（1）被删除的结点是叶子结点例如:被删关键字 = 2088其双亲结点中相应指针域的值改为“空”直接删去该节点。结论：二叉搜索树 删除208850308020908540358832（2）被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。被

12、删关键字 = 4080用其左子树或者右子树代替它。结论：二叉搜索树 删除503080201008540358832（3）被删除的结点既有左子树，也有右子树以其中序遍历的后继替代之，然后再删除该后继结点。后继是右子树中最小的节点。被删关键字 = 90二叉搜索树 删除901101962 The.Hibbard最小值：左子为空，为自己否则在左子树上20 30 32 35 40 50 80 85 88 90 100 110503080100854035833290110noderoot95929693实现用前驱代替被删除节点的删除算法判断一根树是不是二叉搜索树144 Binary Tree Preor

13、der Traversal 94 Binary Tree Inorder Traversal145 Binary Tree Postorder Traversal 102Binary Tree Level Order Traversal 107Binary Tree Level Order Traversal II 103Binary Tree Zigzag Level Order Traversal 105Construct Binary Tree from Preorder and Inorder Traversal 889Construct Binary Tree from Preorder and Postorde