二叉树的原理。

如题，二叉树的原理和实验内容。

Hongxiayanyy · 2018-4-30 01:12:44

【线索二叉树的原理】
聽聽通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。

聽聽因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。
聽聽记ptr指向二叉链表中的一个结点，以下是建立线索的规则：
聽聽（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；
聽聽（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；
聽聽显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

聽聽其中：
聽聽（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；
聽聽（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；
聽聽（3）因此对于上图的二叉链表图可以修改为下图的养子。

fosix46 · 2018-4-30 01:12:45

可以用一个数组来存储二叉树
1作为根节点，而左儿子为2，右儿子为3
以此类推，得出某个点n的左儿子为2n，右儿子为2n+1；
差不多是这样子啦，二叉树有许多应用，网上已经有许多教程了！！

297095637 · 2018-4-30 01:12:46

用一个结构体吧！

我是学计算机的，账号就是QQ号，可以加。

二叉树的原理。

3 个回复