main.cpp

浙江工商大学 计算机与信息工程学院实验报告

#include <queue>
#include <stack>
#include <iostream>
using namespace std;

typedef struct BT
{
	int data;
	BT * left_child;
	BT * right_child;
}BTree;
typedef BTree * PBinTree;

class BinTree
{
private:
public:
	BinTree(PBinTree bt)
	{
		bt = NULL;
	}

	~BinTree() {}

	PBinTree Create(void)
	{
		int n;
		PBinTree bt ;

		cin >> n;
		if (n <= 0)
			bt = NULL;
		else
		{
			bt = new BTree;
			bt->data = n;
			bt->left_child = Create();
			bt->right_child = Create();
		}

		return bt;
	}

	bool re_inorder(PBinTree bt)
	{
		if (bt)
		{
			re_inorder(bt->left_child);
			cout << bt->data << ' ';
			re_inorder(bt->right_child);
		}
		return true;
	}

	bool left_to_right(PBinTree bt)
	{
		PBinTree tmp;
		if (bt)
		{
			left_to_right(bt->left_child);
			left_to_right(bt->right_child);

			tmp = bt->left_child;
			bt->left_child = bt->right_child;
			bt->right_child = tmp;
		}

		return true;
	}

	bool leave(PBinTree bt, int &count)
	{
		if (bt->left_child)
			leave(bt->left_child, count);
		if (bt->right_child)
			leave(bt->right_child, count);
		if (! (bt->left_child || bt->right_child))
			count++;

		return true;
	}

	bool traverse(PBinTree bt)
	{
		PBinTree p;
		queue <PBinTree> q;

		for (q.push(bt) ; !q.empty() ; q.pop())
		{
			p = q.front();
			cout << p->data << ' ' ;
			if (p->left_child)
				q.push(p->left_child);
			if (p->right_child)
				q.push(p->right_child);
		}

		return true;
	}

	bool inorder(PBinTree bt)
	{
		stack <PBinTree> s;
		
		s.push(NULL);
		for (; ;)
		{
			for (; bt ; bt = bt->left_child)
				s.push(bt);
			bt = s.top();
			s.pop();
			if (!bt) break;
			printf("%d ", bt->data);
			bt = bt->right_child;
		}

		return true;
	}
};

int main(void)
{
	int count = 0;
	PBinTree bt = NULL;
	BinTree BTree(bt);

	bt = BTree.Create();
	BTree.inorder(bt);
	cout << endl;
	BTree.left_to_right(bt);
	BTree.inorder(bt);
	cout << endl;
	BTree.leave(bt, count);
	cout << count << endl;
	BTree.traverse(bt);
	cout << endl;

	return 0;
}