Loading... ## 预备知识 ```mermaid graph TB A((A)) B((B)) C((C)) D((D)) E((E)) F((F)) G((G)) H((H)) I((I)) J((J)) K((K)) L((L)) M((M)) N((N)) P((P)) Q((Q)) A---B A---C A---D A---E A---F A---G D---H E---I E---J F---K F---L F---M G---N J---P J---Q ``` 一棵树是N个节点和N-1条边的集合 没有子节点的节点称为叶节点 两节点之间路径的长为该路径上边的条数 任意节点的深度为根节点到该节点路径的长 任意节点的高为该节点到一个叶结点的最长路径的长 ### 数的实现 一般使用一个链表存储子节点 下图为上图的兄弟表示法 ![树的兄弟表示法](https://img.iovee.com/blog/2022/08/08/62f1264cec2e2.jpg) ### 树的遍历及应用 #### 先序遍历 考察到一个节点后,即刻输出该节点的值,并继续遍历其左右子树。(根左右) #### 中序遍历 考察到一个节点后,将其暂存,遍历完左子树后,再输出该节点的值,然后遍历右子树。(左根右) #### 后序遍历 考察到一个节点后,将其暂存,遍历完左右子树后,再输出该节点的值。(左右根) ## 二叉树 二叉树(binary tree)是一棵树,其中每个节点都不能有多于两个的子节点。 二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多。其平均深度为$O(\sqrt{N})$,而对于特殊类型的二叉树,即二叉查找树(binary search tree),其深度的平均值为$O(\log N)$ ### 实现 因为一个二叉树节点最多有两个子节点,所以我们可以保存直接链接到它们的链 ### 表达式树 ## 查找树ADT——二叉查找树 性质:对于树中的每个节点X,它的左子树中所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项 平均深度:$O(\log N)$ 最后修改:2023 年 06 月 05 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用,请随意赞赏