苏州OJ c005: 二叉树遍历

港控/mmm° 2022-08-14 04:56 167阅读 0赞

【问题描述】  
　　小明学完了树的基本知识，想做二叉树遍历的程序设计练习.根据二叉树的深度从数据文件中读入n个整数生成顺序存储的二叉树，做各种遍历的输出。小明发现输出的数据中有不少重复的，为此他先将重复的数据过滤掉，然后再生成二叉树的结构。现在要求你从数据文件中读取若干个整数，生成一个满二叉树，然后输出一个二叉树遍历的序列。  
【输入】  
　　输入文件bintree.in包含2行；  
　　第一行是两个整数h和p，h是二叉树的深度，h<=8。p=1时先序输出，p=2时中序输出，p=3时后序输出。  
　　第二行若干个整数（数字小于等于1000），读入数据前，先要计算二叉树的结点个数n，然后在数据中顺序读取n个不重复的整数。例如深度为3的二叉树结点有7个。  
 注意：数据以文件形式给出，在上机练习文件夹中有数据文件。  
【输出】  
输出文件bintree.out只有一行，是二叉树遍历的序列。  
【输入输出样例】  
输入  
3 2  
277 248 494 88 277 371 387 88 494 216 227……  
输出

88 248 371 277 387 494 216

题目的意思也是读了很多遍才读懂- -，就是先读入h和p，然后从文件中读取2^h-1个数字进入二叉树，然后先序或中序或后序遍历。

我觉得难点应该在于怎么把这2^h-1个树按顺序插入二叉树吧，之前写过的都是二叉查找树什么的，有自己的排序特色，突然来个按顺序排进去的真有点不知所措，思考了一会之后采用了递归的方式把vector里面的元素全排进二叉树里。

题目中要求不要有重复的数字，我用了set来检查。

\--其实我觉得这题我的代码写的不够好，希望有大神指正！

#include <iostream>
    #include <set>
    #include <vector>
    #include <math.h>
    using namespace std;
    
    typedef vector<int>::iterator VecIntIter;
    
    struct BinaryNode {
    	int data;
    	BinaryNode* left;
    	BinaryNode* right;
    
    	BinaryNode(int val, BinaryNode* lt = NULL, BinaryNode* rt = NULL)
    		:data(val), left(lt), right(rt) {}
    };
    
    class BinaryTree {
    private:
    	BinaryNode* root;
    
    public:
    	BinaryTree() { root = NULL; }
    	~BinaryTree() { destroy(); }
    
    	// 用vector填满二叉树，iter传入的是ivec.begin(), n传入1，sz传入ivec.size()
    	void fillTree(const VecIntIter& iter, int n, int& sz) {
    		fillTree(root, iter, n, sz);
    	}
    
    	void destroy()		{ destroy(root);	}
    
    	void preOrder()		{ preOrder(root);	}
    	void inOrder()		{ inOrder(root);	}
    	void postOrder()	{ postOrder(root);	}
    
    private:
    	// node是需要new的结点，*(iter+n)是给当前结点的值，当然n如果大于sz-1就return了
    	void fillTree(BinaryNode*& node, const VecIntIter& iter, int n, int& sz) {
    		
    		if (n > sz-1) return;
    
    		node = new BinaryNode(*(iter + n));
    		fillTree(node->left, iter, 2 * n, sz);
    		fillTree(node->right, iter, 2 * n + 1, sz);
    	}
    
    	void destroy(BinaryNode* node) {
    		if (node == NULL) return;
    		destroy(node->left);
    		destroy(node->right);
    		delete node;
    	}
    
    	void preOrder(BinaryNode* node) {
    		if (NULL == node) return;
    		cout << node->data << " ";
    		preOrder(node->left);
    		preOrder(node->right);
    	}
    	void inOrder(BinaryNode* node) {
    		if (NULL == node) return;
    		inOrder(node->left);
    		cout << node->data << " ";
    		inOrder(node->right);
    	}
    	void postOrder(BinaryNode* node) {
    		if (NULL == node) return;
    		postOrder(node->left);
    		postOrder(node->right);
    		cout << node->data << " ";
    	}
    };
    
    int main()
    {
    	int h, p, data;
    
    	cin >> h >> p;
    	// 共要读入num个数
    	int num = (int)(pow(2, h) - 1);
    
    	set<int> iSet;
    	vector<int> ivec;
    
    	// 先push_back进去一个无用的，让下标从1开始，方便计算(参照堆的构造)
    	ivec.push_back(0);
    	
    	while (cin >> data) {
    		if (!iSet.count(data)) {
    			iSet.insert(data);
    			ivec.push_back(data);
    		}
    		if (ivec.size() == num + 1) {
    			break;
    		}
    	}
    
    	BinaryTree bt;
    	VecIntIter iter = ivec.begin();
    	int sz = ivec.size();
    	bt.fillTree(iter, 1, sz);
    	// 输出
    	switch (p) {
    	case 1:
    		bt.preOrder();
    		break;
    	case 2:
    		bt.inOrder();
    		break;
    	case 3:
    		bt.postOrder();
    		break;
    	}
    
    	return 0;
    }