我们知道二叉树有先序，中序，后序之分。线索二叉树是为了加速遍历，对于不同的二叉树有不同的实现。
这个线索二叉树是中序的。
#include<stdio.h> #include<malloc.h> typedef struct data { int value; }EData,*Data; typedef struct tree { int rtag; //为0时，右子树是孩子，是1时，是后续树 Data data; struct tree* ltree; struct tree* rtree; }ETree,*Tree; typedef struct node { Tree tree; struct node * next; }ENode,*Node; //stack为了将二叉树转化为线索二叉树 typedef struct stack { Node head; int length; }EStack,*Stack; void push(Stack stack,Tree tree) { Node node = (Node)malloc(sizeof(ENode)); node->tree=tree; node->next=stack->head; stack->head=node; stack->length++; } Tree pop(Stack stack) { if(stack->length<=0) return NULL; Tree tree = stack->head->tree; stack->head=stack->head->next; stack->length--; return tree; } bool isEmpty(Stack stack) { return stack->length<=0; } //转化为线索二叉树的递归函数 void initialRound(Tree root,Stack stack) { if(root->ltree) { if(root->rtree) { push(stack,root->rtree); initialRound(root->ltree,stack); } else { if(!isEmpty(stack)) root->rtree=pop(stack); initialRound(root->ltree,stack); if(root->rtree) initialRound(root->rtree,stack); } } else if(root->rtree) { initialRound(root->rtree,stack); } else { if(!isEmpty(stack)) { root->rtree=pop(stack); initialRound(root->rtree,stack); } } } void initialXSTree(Tree root) { Stack stack = (Stack)malloc(sizeof(EStack)); stack->length=0; stack->head=NULL; initialRound(root,stack); } void print(Tree root) { if(!root) return; printf("%d/n",root->data->value); print(root->ltree); print(root->rtree); } void print2(Tree root) { Tree temp=root; while(temp) { printf("%d/n",temp->data->value); if(temp->ltree) temp=temp->ltree; else temp=temp->rtree; } } void main() //测试 { EData data1,data2,data3,data4,data5,data6; data1.value=1; data2.value=3; data3.value=6; data4.value=4; data5.value=7; data6.value=9; ETree tree1,tree2,tree3,tree4,tree5,tree6; tree1.rtag=0;tree1.ltree=NULL;tree1.rtree=NULL; tree2.rtag=0;tree2.ltree=NULL;tree2.rtree=NULL; tree3.rtag=0;tree3.ltree=NULL;tree3.rtree=NULL; tree4.rtag=0;tree4.ltree=NULL;tree4.rtree=NULL; tree5.rtag=0;tree5.ltree=NULL;tree5.rtree=NULL; tree6.rtag=0;tree6.ltree=NULL;tree6.rtree=NULL; tree1.data=&data1; tree2.data=&data2; tree3.data=&data3; tree4.data=&data4; tree5.data=&data5; tree6.data=&data6; tree1.ltree=&tree2; tree2.ltree=&tree3; tree2.rtree=&tree4; tree1.rtree=&tree5; tree5.ltree=&tree6; initialXSTree(&tree1); print2(&tree1); }
在测试中二叉树图形
