栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。

树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。

1. 树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：

• 有且仅有一个特定的称为根（Root）的结点；

• 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3,...Tm，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。

例如，（a）是只有一个根结点的树；（b）是有13个结点的树，其中A是根，其余结点分成3个互不相交的子集：T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子树，且本身也是一棵树。

1. 树的结点包含一个数据元素及若干指向其子树的分支。

结点拥有的子树数称为结点的度（Degree）。例如，（b）中A的度为3，C的度为1，F的度为0。度为0的结点称为叶子（Leaf）或者终端结点。度不为0的结点称为非终端结点或分支结点。

树的度是树内各结点的度的最大值。（b）的树的度为3。结点的子树的根称为该结点的孩子（Child）。相应的，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

1. 结点的层次（Level）从根开始定义起，根为第一层，跟的孩子为第二层。若某结点在第层，则其子树的根就在第l+1层。其双亲在同一层的结点互为堂兄弟。例如，结点G与E，F,H,I,J互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。（b）的树的深度为4。

1. 如果将树中结点的各子树看成从左至右是有次序的（即不能交换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。

2. 森林（Forest）是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分（其次序不能任意颠倒。）

• 在二叉树的第 i 层上至多有个结点(i>=1)。

• 深度为k的二叉树至多有个结点，(k>=1)。

• 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1;

• 1个结点的二叉树称为满二叉树。

• 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

1. 完全二叉树的两个特性：

• 具有n个结点的完全二叉树的深度为;

• 如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第，每层从左到右），则对任一结点（1<=i<=n）有：

7. 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用遍历次序是（）

这题顾名思义了：后序遍历为左右根，因此左孩子<右孩子<根节点，满足题目条件

8. 若二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（ ）。

9. 在二叉树结点的先序序列、中序序列和后序序列中 ，所有叶子结点的先后顺序相同吗？

A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同。

一样拿上面图来说呗 加上后序 自己去对比HIK在三种情况下是不是相同的

10. 下述编码中哪一个不是前缀码()

11. 引入线索二叉树的目的

百度：引入线索二叉树的目的是找一个节点的前驱后继的时候，比非二叉线索树方便快捷。按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。

　　当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

12. n个结点的线索二叉树上含有的线索数为 。

2. 试找出满足下列条件的二叉树：

试找出满足下列条件的二叉树：
1）先序序列与后序序列相同； 2）中序序列与后序序列相同；
3）先序序列与中序序列相同； 4）中序序列与层次序列相同；

【答案】先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根”，根据以上原则，解答如下：
1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。
（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
（4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树

2.画出这棵二叉树的后序线索二叉树

3.将这棵二叉树转换成对应的树（或森林）

三维数组A[n][m][k]，n,m,k三个分量分别称之为行，列，页。
假设A[0][0][0]的存储地址为a，其中每个元素所占内存空间为b，那么计算A[x][y][z]的存储地址的公式为a+(xmk+yk+z)b

三位数组按行优先存储在内存空间中的存储方式为：

首先将第一行第一列的页存满，再存第一行第二列的页，直到第一行存满后再存下一行。

数组可看成线性结构的推广,因此与线性表一样可以对它进行 插入,删除等操作“ 这句话对还是错？

忽略效率，数组大小等是对的，但是数组一般是固定大小的，插入删除的话要重新分配空间

数据：数据是描述客观事物的数值、字符以及能输入给计算机且能被计算机处理的各种符号集合。
简单的来说，数据就是计算机化的信息。

数据元素：是组成数据的基本单位，在计算机中通常被作为一个整体进行考虑和处理。也被称为记录。

数据项：数据项是数据不可分割的最小单位。一个数据元素可由多个数据项组成。
比如我们的人类世界中，人、狗都能被称为数据元素，作为整体进行考虑。而眼、鼻、手等就是数据项。

数据对象：数据对象是性质相同的数据元素的集合，是数据的子集。
例如学籍表，每个人（数据元素）都有姓名、年龄等数据项，都属于同一个数据对象。

数据结构：我们现实世界中，不同的数据元素之间不是独立的，而是存在某些关系，这些关系就是结构。数据结构是指相互之间存在一种或多种特定关系的数据元素集合。
例如图书馆中的每本图书都是数据元素，但是图书馆并不是简单的所有图书都堆积在一起，而是按照某种结构组织图书。

逻辑结构是指元素之间的逻辑关系描述。逻辑结构分为四种。

• 集合结构：结构中的数据除了同属于一个集合的关系外，无任何其他关系。

• 线性结构：结构中的数据元素之间存在着一对一的线性关系。

• 树状结构：结构中的数据元素之间存在着一对多的关系。

• 图状结构（网状结构）：结构中的数据元素之间存在着多对多的任意关系。

物理结构：是指逻辑结构在计算机中真正的存储结构。

• 顺序存储结构：把数据元素存放在地址连续的存储单元里。类似于排队，每个人都按顺序站好。我们学习的高级程序语言中的数组就是顺序存储结构，计算机会帮你的数组在内存中找片连续的空间。

• 链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以不连续。只需要前一个元素记住下一个元素的内存地址，这样就像链条链在一起，如下图。

• 有穷性：有限步骤内正常结束，不能无限循环。
• 确定性：每个步骤都必须有确定的含义，无歧义。
• 可行性：原则上能精确进行，操作能通过有限次完成。
• 输入：有0或多个输入。
• 输出：至少有一个输出。

算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

算法是若干指令的有穷序列，满足性质：
(1)输入：由外部提供的量作为算法的输入。
(2)输出：算法产生至少一个量作为输出。
(3)确定性：组成算法的每条指令是清晰，无歧义的。
(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
(5)可行性：算法中所有的操作都必须足够基本，使算法的执行者或阅读者明确其含义以及如何执行。

程序是计算机指令的有序集合，是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。

(1)算法在描述上一般使用半形式化的语言，而程序是用形式化的计算机语言描述的。
(2) 程序是计算机指令的有序集合。
(3)程序并不都满足算法所要求的特征，例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
(4)一个算法可以用不同的编程语言编写出不同的程序。
(5)算法是解决问题的步骤；程序是算法的代码实现。
(6)算法要依靠程序来完成功能；程序需要算法作为灵魂。
(7)程序=算法+数据结构。

衡量一个算法的的标准主要有3个：算法的执行效率，算法的内存消耗和算法的稳定性。

往往和算法本身以及具体的数据有关系。通常会从3个维度的时间复杂度来衡量算法的的执行效率： 最好情况时间复杂度，最坏情况时间复杂度和平均情况时间复杂度。

算法的内存消耗：往往和算法本身有关系。可以通过调整算法，以空间换时间来提升算法的执行效率。

算法的稳定性：算法的执行效率随着数据规模增长的变化也是衡量算法的稳定性的一个因素；同时，算法的内存消耗和数据规模增长的变化也是衡量算法的稳定性的一个因素。