由前序和中序遍历结果构建二叉树 #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; /* 标记树有没有完全建立起来，初始化为假 */ while (!done) /* 如果树没有建立起来，则要继续进入建立 */ { while (n != 0) /* n 的值不为 0，也就是 pre 和 in 中都至少还有一个元素的时候 */ { i = myIndex(in,pre[0]); /* 确定 pre 的第一个元素，就是父结点在中序遍历结果中的位置 */ p = (PNode)(malloc(sizeof(struct Node))); /* 建立一个结点 */ p->info = pre[0]; p->parent = parent; p->lchild = NULL; p->rchild = NULL; if (parent != NULL) /* 当结点的父结点不是空值时，就把 parent 的左孩子值改成 p */ { parent->lchild = p; } else /* 如果为空时 */ { head = p; /* 那么这个结点就是根结点 */ } if (n - i - 1 != 0) /* 只有前序遍历和中序遍历结果都有元素时，才入栈 */ { t.pre = pre + i + 1; /* 右子树的前序遍历的结果 */ t.in = in + i + 1; /* 右子树的中序遍历的结...
