主要的二叉树

领导二叉树或线索二叉树实际上就是遍历二叉树. 遍历期间，请检查当前节点的左右指针字段是否为空. 如果为空，则将其更改为指向前一节点或后继节点的线索.

当使用二进制链表作为存储结构时，只能找到左子信息和右子信息，并且不能直接获得任何顺序的节点的前任和后继信息. 该信息只能在动态遍历过程中获得. 解决此问题的最简单方法是向每个节点添加两个指针字段fwd和bkwd后续线索二叉树，并指示节点以任何顺序遍历时都获取前驱和后继信息. 显然，结构的存储密度大大降低了. 另一方面，二进制列表中必须有n + 1个具有n个节点的空链域. 因此，设想是否可以将这些空链域用于存储前任和后继信息.

尝试以下规则: 如果节点具有左子树，则其lchild字段指向其左子节点；否则，该字段指示其前任子节点；如果节点具有右子树，则其rchild字段指示其右子节点；否则让里德尔指示他的继任者. 为了避免混淆后续线索二叉树，必须更改节点结构并添加两个标志字段.

lchild LTag数据RTag rchild

位置:

LTag=0  lchild域指示结点的左孩子
LTag=1  lchild域指示结点的前驱
RTag=0  rchild域指示结点的右孩子
RTag=1  rchild域指示结点的后继

由该节点结构组成的二进制列表用作二进制树的存储结构，称为线索链接列表，指向该节点的前任和后继的指针称为线索. 具有线索的二叉树称为线索二叉树. 按一定顺序将二叉树遍历为二叉树的过程称为线程化.

头文件:

/***************************************************************************************************** 
 *Copyright: Yue Workstation 
 * 
 *FileName: IndexTree.h 
 * 
 *Function: 线索二叉树数据结构定义 
 * 
 *Author: Abel Lee 
 * 
 *CreateOn: 2012-2-19 
 * 
 *Log: 2012-2-19 由Abel Lee创建 
 *****************************************************************************************************/ 
#ifndef INDEX_TREE_H 
#define INDEX_TREE_H 
#include "global.h" 
typedef enum{Link,Thread} PointerTag;     //指针标志 
typedef int DataType; 
typedef struct BiThreTree 
{               //定义结点元素 
    PointerTag LTag,RTag; 
    DataType data; 
    struct BiThreTree *lchild,*rchild; 
}BiThreTree; 
BiThreTree *pre;                     //全局变量，用于二叉树的线索化 
BiThreTree *CreateTree(void); 
void InThread(BiThreTree *T); 
BiThreTree *InOrderThrTree(BiThreTree *T); 
void InThrTravel(BiThreTree *Thre); 
#endif

源文件:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-276303-1.html