#include <stdio.h> #include <stdlib.h> // 线索二叉树结点 typedef struct ThreadNode { int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; } ThreadNode, *ThreadTree; ThreadNode *pre = NULL; void create(ThreadTree &T) { T = (ThreadNode *)malloc(sizeof(ThreadNode)); T->data = 1; T->ltag = T->rtag = 0; ThreadNode *T2 = (ThreadNode *)malloc(sizeof(ThreadNode)); T2->data = 2; T2->ltag = T2->rtag = 0; T->lchild = T2; ThreadNode *T3 = (ThreadNode *)malloc(sizeof(ThreadNode)); T3->data = 3; T3->ltag = T3->rtag = 0; T->rchild = T3; ThreadNode *T4 = (ThreadNode *)malloc(sizeof(ThreadNode)); T4->data = 4; T4->lchild = T4->rchild = NULL; T4->ltag = T4->rtag = 0; T2->lchild = T4; ThreadNode *T5 = (ThreadNode *)malloc(sizeof(ThreadNode)); T5->data = 5; T5->lchild = T5->rchild = NULL; T5->ltag = T5->rtag = 0; T2->rchild = T5; ThreadNode *T6 = (ThreadNode *)malloc(sizeof(ThreadNode)); T6->data = 6; T6->lchild = T6->rchild = NULL; T6->ltag = T6->rtag = 0; T3->lchild = T6; ThreadNode *T7 = (ThreadNode *)malloc(sizeof(ThreadNode)); T7->data = 7; T7->lchild = T7->rchild = NULL; T7->ltag = T7->rtag = 0; T3->rchild = T7; } void visit(ThreadNode *q){ if(q->lchild == NULL){ q->lchild = pre; q->ltag =1; } if(pre!=NULL && pre->rchild == NULL){ pre->rchild = q; pre->rtag = 1; } pre = q; } void PreThread(ThreadTree T){ if(T!=NULL){ visit(T); if(T->ltag==0){ PreThread(T->lchild); } PreThread(T->rchild); } } //前序线索化二叉树T void createPreThread(ThreadTree T){ pre = NULL; if(T!=NULL){ PreThread(T); if(pre->rchild == NULL){ pre->rtag = 1; } } } //前序线索化二叉树找后继r ThreadNode *NextNode(ThreadNode *p){ //1.如果右孩子是线索，直接返回后继 if(p->rtag == 1){ return p->rchild; } //2.如果右边不是线索(说明必有右孩子) //根据"根-左-右"，如果有左孩子，后继就是左孩子 if(p->ltag == 0){ return p->lchild; } return p->rchild; } void PreOrder(ThreadNode *T){ for(ThreadNode *p = T;p!=NULL;p=NextNode(p)){ printf("%d ",p->data); } } int main(){ ThreadTree T; create(T); createPreThread(T); PreOrder(T); return 0; }
