levelc1.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 92 行

#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"

typedef struct {
   BELEM info;
   int ltag, rtag;   
} levelNode;

typedef BinNode* ELEM;

#include "..\include\link.h"
#include "..\include\lqueue.h"

void level_create(BinNode* &rt, levelNode* tree, int n) {
   BinNode *p, *p1;
   Queue qu;

   p = new BinNode;   // 建立根结点
   rt = p;
   for (int i=0; i<n-1; i++) {
      p->element = tree[i].info;  // 当前结点已经被申请过，只需要添加信息
      if (tree[i].ltag == 0)
         qu.enqueue(p);
      else p->right = 0;
      p1 = new BinNode;    // 准备下一个结点
      if (tree[i].rtag == 0)
         p->right = p1;    // 下一个表项是本结点的右子结点
      else {
         p->right = NULL;
         qu.dequeue()->left = p1;
      }
      p = p1;
   }
  p->element = tree[n-1].info;  // 处理最后一个结点
  p->left = p->right = NULL;
}


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;
        levelNode *tree;

	int n;

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

	tree = new levelNode[n];

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

	cout << "input " << n << " integers as ltag\n";
	for (i=0; i < n; i++)
		cin >> tree[i].ltag;

	cout << "input " << n << " integers as rtag\n";
	for (i=0; i < n; i++)
		cin >> tree[i].rtag;

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