create.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>

#include "..\include\book.h"


typedef char BELEM;
#include "..\include\bintree.h"

BELEM *inseq, *preseq;

void  btree_create(int m1, int m2, int n, BinNode* &t) {
// m1 : preseq的开始位置; m2 : inseq的开始位置;  n : 子树序列长 
    int i;
       
	if (n == 0)
		t = NULL;
	else {
		t = new BinNode;
		t->element = preseq[m1];
		i = m2;
		while (inseq[i] != preseq[m1]) 	 // 寻找中序中根位置 
			i++;
		btree_create(m1+1,m2,i-m2,t->left);     // 左子树 
		btree_create(m1+1+i-m2,i+1,n-(i-m2)-1,t->right);  // 右子树
	}
}


void pre_traverse(BinNode *rt) {      // Inorder traversal
  if (rt == NULL) return;            // Nothing to visit
  cout << rt->element << " ";
  pre_traverse(rt->left);
  pre_traverse(rt->right);
}

void in_traverse(BinNode *rt) {      // Inorder traversal
  if (rt == NULL) return;            // Nothing to visit
  in_traverse(rt->left);
  cout << rt->element << " ";
  in_traverse(rt->right);
}

void main() {
	BinNode *root;

	int n;	

	root = NULL;
	cout << "input the length\n";
    cin >> n;

	preseq = new BELEM[n];
	inseq = new BELEM[n];

	cout << "input n characters as preorder\n";
	for (int i=0; i < n; i++)
		cin >> preseq[i];

	cout << "input n characters as inorder\n";
	for (i=0; i < n; i++)
		cin >> inseq[i];

	btree_create(0,0,n,root);
	cout << "*** preorder recursive ***" << endl;
	pre_traverse(root);    cout << endl;
	cout << "*** inorder recursive ***" << endl;
	in_traverse(root);    cout << endl;
}