面试+简历制作专题

树与树的表示

• 客观世界中许多事物存在层次关系
  • 人类社会家谱
  • 社会组织结构
  • 图书信息管理

什么是树

1. 分层次组织在管理上具有更高的效率!
2. 数据管理的基本操作之一：查找

查找（Searching）

查找：根据某个给定关键字K ，从集合R中找出关键字与K相同的记录

1. 静态查找：集合中记录是固定的
   • 没有插入和删除操作，只有查找
2. 动态查找：集合中记录是动态变化的
   • 除查找，还可能发生插入和删除
     

     方法2：二分查找（Binary Search)

     

     假设n个数据元素的关键字满足有序（比如：小到大）a1 < a2 <… an 并且是连续存放（数组），那么可以进行二分查找。

     讨论 ：黄金分割查找？

     在二分查找中，我们是取mid等于left和right的中间值，即用等分的方法进行查找。
     那为什么一定要等分呐？能不能进行“黄金分割”？也就是mid=left+0.618(right-left),当然mid要取整数。如果这样查找，时间复杂性是多少？也许你还可以编程做个试验，比较一下二分法和“黄金分割”法的执行效率。

• 二分法更快。因为分割两端的不均等会导致效率的下降。考虑一个极端的例子，假如有100个元素，每次分割成1:99，那就基本与顺序查找等价，效率就远比二分法低了。

树的定义

树（Tree）: n（n≥0）个结点构成的有限集合。

• 当n=0时，称为空树；
• 对于任一棵非空树（n> 0），它具备以下性质：
  • 树中有一个称为“根（Root）”的特殊结点，用 r 表示；
  • 其余结点可分为m(m>0)个互不相交的有限集T1，T2，… ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”

讨论: 森林及表示老师参与

树的集合称为森林。是否也可以使用“儿子-兄弟”表示法存储森林？如何实现？
详情

typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */
    ElementType Data; /* 结点数据 */
    BinTree Left;     /* 指向左子树 */
    BinTree Right;    /* 指向右子树 */
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1210331079@qq.com