Question

数据结构(树和二叉树)

Answer 1

树是n (n≥0) 个结点的有限集。 n=0 时称为空树。在任意一棵非空树中：

二叉树是n个结点所构成的集合，它或为空树（n=0），或为非空树，对于非空树T：

二叉树和树的区别：
＊ 二叉树每个结点至多只有两颗子树。
＊ 二叉树的子树有左右之分，其次序不能任意颠倒。

1.顺序存储结构：使用一组地址连续的存储单元来存储数据元素，将二叉树的结点依照自上而下，自左至右存储结点元素。

2.链式存储结构：结点包含3个域：数据域，左右指针。

遍历二叉树是指按某条搜索路径巡访树中每个结点，使的每个结点均被访问一次，而且仅被访问一次。遍历的实质是对二叉树进行线性化的过程。

RTag:
0->Rchild域指示结点的右孩子
1-> Rchild域指示结点的后继

由于线索二叉树构造的实质是将二叉链表中的空指针指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。

根结点因为没有双亲，我们约定根结点的位置域设置为-1，则每个结点都存有其双亲的位置。