线索二叉树c语言代码中序

### C语言实现线索二叉树中序遍历 为了实现线索二叉树的中序遍历，在C语言中通常会扩展标准二叉树节点结构来存储额外的信息。具体来说，每个节点不仅包含指向其左右子节点的指针，还包含了两个标志位`left_type`和`right_type`以及前驱(`predecessor`)和后继(`successor`)节点的指针。 #### 结构体定义 ```c struct BiThrNode { int data; struct BiThrNode *lchild, *rchild; int ltag, rtag; /* 0表示指针，1表示线索 */ }; typedef struct BiThrNode* BiThrTree; ``` #### 初始化函数 创建一个新的二叉树节点，并设置初始状态为非线索化。 ```c BiThrTree CreateTreeNode(int value){ BiThrTree T; if (!(T = (BiThrTree)malloc(sizeof(struct BiThrNode)))) { printf("Out of memory!\n"); exit(1); } T->data = value; T->lchild = NULL; T->rchild = NULL; T->ltag = 0; T->rtag = 0; return T; } ``` #### 中序线索化过程 此部分负责按照中序方式访问整棵树的同时建立相应的线索连接[^1]。 ```c void InThread(BiThrTree &p, BiThrTree &pre){ if(p != NULL){ // 左子树递归处理 InThread(p->lchild, pre); // 当前节点操作 if(p->lchild == NULL){ p->ltag = 1; p->lchild = pre; } if(pre && pre->rchild==NULL){ pre->rtag=1; pre->rchild=p; } pre = p; // 右子树递归处理 InThread(p->rchild, pre); } } ``` #### 构建完整的中序线索二叉树 通过调用上述方法完成整个构建流程[^5]。 ```c void CreateInThread(BiThrTree Thrt,BiThrTree &T){ BiThrTree first,last; Thrt=(BiThrTree)malloc(sizeof(struct BiThrNode)); Thrt->ltag=0; Thrt->rtag=1; Thrt->rchild=T; if(!T){ Thrt->ltag=1; Thrt->lchild=Thrt; Thrt->rchild=Thrt; }else{ Thrt->lchild=T; last=NULL; InThread(T,last); while(T->ltag==0) T=T->lchild; first=T; Thrt->lchild=first; Thrt->rchild=last; first->lchild=Thrt; last->rchild=Thrt; } } ``` #### 遍历已线索化的二叉树 一旦完成了中序线索化，则可以利用这些线索快速地进行遍历而无需栈或队列辅助数据结构[^4]。 ```c void InOrderTraverse_Thr(BiThrTree T){ BiThrTree p=T->lchild; while(p!=T){ while(p->ltag==0)p=p->lchild; printf("%d ",p->data); while(p->rtag==1&&p->rchild!=T){ p=p->rchild; printf("%d ",p->data); } p=p->rchild; } } ```