二叉树先序线索化及先序线索二叉树找后继

#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-ltag0){ 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;pNextNode(p)){ printf(%d ,p-data); } } int main(){ ThreadTree T; create(T); createPreThread(T); PreOrder(T); return 0; }