依据先序、中序序列建立二叉树

include <stdio.h>

 #include<stdlib.h>
 #include<stdbool.h>
 typedef int TElemtype;

typedef struct BiTNode
{
	TElemtype Data;
	int IfVisited;
	struct BiTNode* Lchild, * Rchild;

    }BiTNode;
    typedef BiTNode* BiTree;
int array_length;
int Search(TElemtype ps, TElemtype* in)
{
	for (int i = 0; i < array_length; i++) {
		if (in[i] == ps)return i;
	}
	return -1;
}

void Pre_And_IN(BiTree& T, TElemtype* pre, TElemtype* in, TElemtype ps, TElemtype is, int n)//先序中序建树
{
	if (n == 0) T = NULL;
	else {
		int k = Search(pre[ps], in);
		if (k == -1) {
			T = NULL;
			return;
		}
		else {
			T = (BiTree)malloc(sizeof(BiTNode));
			T->Data = in[k];
			if (k - is == 0) T->Lchild = NULL;
			else Pre_And_IN(T->Lchild, pre, in,ps+1,is,k-is );
			if (n - 1 - k + is == 0)T->Rchild = NULL;
			else Pre_And_IN(T->Rchild, pre, in,ps+k-is+1,k+1,n-1-k+is );

		}
	}

}

int main()
{
	BiTree  N[9];

	for (int i = 0; i < 9; i++) { N[i] = CreateNode(i); N[i]->IfVisited = 0; }
	N[0]->Lchild = N[1]; N[0]->Rchild = N[2];
	N[1]->Lchild = N[3];
	N[2]->Lchild = N[4]; N[2]->Rchild = N[5];
	N[3]->Rchild = N[6];
	N[6]->Lchild = N[7]; N[6]->Rchild = N[8];
        int pre[7] = { 23,54,2,6,8,9,13 };
	int in[7] = { 2,54,6,23,8,13,9 };
	array_length = 7;
        BiTree T1, T2;

	Pre_And_IN(T1, pre, in, 0, 0, 7);
            PostOrder(T1, PrintTree); printf("\n");

}

上一篇:数据结构-二叉树编程


下一篇:已知先序遍历和中序遍历求后序遍历