二叉树中序线索化及中序线索二叉树找前驱/后继

#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 InThread(ThreadTree T) { if (T ! NULL) { InThread(T-lchild); visit(T); InThread(T-rchild); } } //中序线索化二叉树T void createInThread(ThreadTree T) { pre NULL; if (T ! NULL) { InThread(T); if (pre-rchild NULL) { pre-rtag 1; // 最后一个节点后继为空标记为线索 } } } //中序线索二叉树找后继 //找到以p为根的子树中第一个被中序遍历的结点 ThreadNode *Firstnode(ThreadNode *p) { while (p-ltag 0) p p-lchild;//循环找到最左下的结点 return p; } //在中序线索二叉树中找到结点p的后继结点 ThreadNode *Nextnode(ThreadNode *p) { if (p-rtag 1) return p-rchild; // 有线索直接找后继 else return Firstnode(p-rchild); // 有右孩子找右子树最左下的节点 } //对中序线索二叉树进行中序遍历利用线索实现的非递归算法) void InOrder(ThreadTree T) { if (T NULL) return; for (ThreadNode *p Firstnode(T); p ! NULL; p Nextnode(p)) printf(%d , p-data); } //中序线索找前驱 //找到以p为根的子树中最后一个被中序遍历的结点 ThreadNode *Lastnode(ThreadNode *p){ while (p-rtag 0) p p-rchild;//循环找到最右下结点 return p; } //在中序线索二叉树中找到p结点的前驱结点 ThreadNode *Prenode(ThreadNode *p){ if(p-ltag 1) return p-lchild;//有线索直接找前驱 else return Lastnode(p-lchild);//有左孩子找左子树最右下的结点 } //对中序线索二叉树进行逆序的中序遍历 void RevInorder(ThreadNode *T){ for(ThreadNode *p Lastnode(T);p!NULL;p Prenode(p)) printf(%d ,p-data); } int main() { ThreadTree T NULL; create(T); createInThread(T); InOrder(T); RevInorder(T); return 0; }