由前序和中序遍历结果构建二叉树 #include #include #include #define N 50 struct Node /* 树结点类型 */ { char info; /* 数据域 */ struct Node* parent; /* 父结点 */ struct Node* lchild; /* 左孩子结点 */ struct Node* rchild; /* 右孩子结点 */ }; typedef struct Node* PNode; struct Stack /* 栈结点类型 */ { char* pre; char* in; int n; PNode parent; }; int myIndex(char seq[],char c) /* 查找c 在seq 中的位置，不存在则返回-1 */ { int i; for (i = 0;seq[i]
= '\0';i++) { if (seq[i] == c) { return i; } } return -1; } /* 创建一棵树，其中 pre 是前序遍历的结果，in 是中序遍历的结果，n 是结点总数,parent 是所建的树的父结点 */ /* 如果结点数大于 0，则创建一个结点并返回指向这个结点的指针，如果等于 0，则返回 NULL */ /* 具体算法请参照二叉树的前序遍历的非递归算法 */ PNode creattree(char pre[],char in[],int n,PNode parent) { PNode p; struct Stack s[N],t; /* 用来存储参数的栈 */ int top = 0; /* 栈顶指针，值为 0 的时候，栈为空 */ int i; PNode head = NULL; /* 用来返回的根结点 */ int done = 0
