首页 > 代码库 > 【数据结构】二叉树(c++)

【数据结构】二叉树(c++)

头文件:


#include <iostream>
using namespace std;

template<class Type>
class Bintree;

//结点类
template<class Type>
class BintreeNode
{
	friend class Bintree<Type>;
public:
	BintreeNode() :data(Type()), leftchild(NULL), rightchild(NULL)
	{}
	BintreeNode(Type d, BintreeNode<Type> *l = NULL, BintreeNode<Type> *r = NULL) : data(d), leftchild(l), rightchild(r)
	{}
private:
	BintreeNode<Type> *leftchild;
	BintreeNode<Type> *rightchild;
	Type              data;
};

//二叉树类
template<class Type>
class Bintree
{
public:
	Bintree() :Ref(Type()), root(NULL)
	{}
	Bintree(Type re, BintreeNode<Type> *r = NULL) : Ref(re), root(r)
	{}
	~Bintree()
	{
		Destory();
	}
public:
	//提供接口
	void CreatBintree()
	{
		Creat(root);
	}

	void PreOrder()
	{
		PreOrder(root);
	}

	void InOrder()
	{
		InOrder(root);
	}

	void PostOrder()
	{
		PostOrder(root);
	}

	int Height()
	{
		return Height(root);
	}

	int Size()
	{
		return Size(root);
	}

	BintreeNode<Type> *Search(Type key)
	{
		return Search(root, key);
	}

	BintreeNode<Type> *PreOrder_Find(Type key)
	{
		return PreOrder_Find(root, key);
	}

	BintreeNode<Type> *InOrder_Find(Type key)
	{
		return InOrder_Find(root, key);
	}

	BintreeNode<Type> *PostOrder_Find(Type key)
	{
		return PostOrder_Find(root, key);
	}

	BintreeNode<Type> *Parent(BintreeNode<Type> *q)
	{
		return Parent(root, q);
	}

	BintreeNode<Type> *Leftchild(Type key)
	{
		return Leftchild(root, key);
	}

	BintreeNode<Type> *Rightchild(Type key)
	{
		return Rightchild(root, key);
	}

	Type Root()
	{
		return Root(root);
	}

	void Destory()
	{
		return Destory(root);
	}

	bool IsEmpty()
	{
		return IsEmpty(root);
	}
	
	void quit_system(int &x)
	{
		x = 0;
	}
protected:
	//创建二叉树
	void Creat(BintreeNode<Type> *&t)
	{
		Type input;
		cin >> input;
		if (input == Ref)
		{
			t = NULL;
		}
		else
		{
			t = new BintreeNode<Type>(input);
			Creat(t->leftchild);
			Creat(t->rightchild);
		}
	}

	// 前序遍历
	void PreOrder(const BintreeNode<Type> *t)
	{
		if (t == NULL)
		{
			return;
		}
		else
		{
			cout << t->data << "  ";
			PreOrder(t->leftchild);
			PreOrder(t->rightchild);
		}
	}

	// 中序遍历
	void InOrder(const BintreeNode<Type> *t)
	{
		if (t == NULL)
		{
			return;
		}
		else
		{
			InOrder(t->leftchild);
			cout << t->data << "  ";
			InOrder(t->rightchild);
		}
	}

	// 后序遍历
	void PostOrder(const BintreeNode<Type> *t)
	{
		if (t == NULL)
		{
			return;
		}
		else
		{
			PostOrder(t->leftchild);
			PostOrder(t->rightchild);
			cout << t->data << "  ";
		}
	}

	// 求高度
	int Height(const BintreeNode<Type> *t)
	{
		if (t == NULL)
			return 0;
		return (Height(t->leftchild) > Height(t->rightchild)) ?

(Height(t->leftchild) + 1) : (Height(t->rightchild) + 1); } int Size(const BintreeNode<Type> *t) { if (t == NULL) return 0; return(Size(t->leftchild) + Size(t->rightchild) + 1); } // 查找一个节点返回其地址 BintreeNode<Type> *Search( BintreeNode<Type> *t,const Type key) { if (t == NULL) { return NULL; } if (t->data =http://www.mamicode.com/= key)"the node is not exist!" << endl; return NULL; } if (p->leftchild == NULL) { cout << "this node not has leftchild" << endl; return NULL; } else return p->leftchild; } // 求右孩子 BintreeNode<Type> *Rightchild(BintreeNode<Type> *t, const Type key) { BintreeNode<Type> *p = Search(t, key); if (p == NULL) { cout << "the node is not exist!" << endl; return NULL; } if (p->rightchild == NULL) { cout << "this node not has rightchild" << endl; return NULL; } else return p->rightchild; } // 求根 Type Root(const BintreeNode<Type> *t) { return t->data; } void Destory(const BintreeNode<Type> *t) { if (t != NULL) { Destory(t->leftchild); Destory(t->rightchild); delete t; } } // 看树是否为空 bool IsEmpty(const BintreeNode<Type> *t) { return t == NULL; } private: BintreeNode<Type> *root; Type Ref; };



页面设计:


#include "Bintree.h"

int main()
{
	Bintree<char> bt(‘#‘);
	int select = 1;
	char c;
	while (select)
	{
		cout << "******************************************************************" << endl;
		cout << "*     [1] creat           [2] PreOrder          [3] InOrder      *" << endl;
		cout << "*     [4] PostOrder       [5] Height            [6] Size         *" << endl;
		cout << "*     [7] search          [8] PreOrder_Find     [9] InOrder_Find *" << endl;
		cout << "*     [10] PostOrder_Find [11] parent           [12] leftchild   *" << endl;
		cout << "*     [13] rightchild     [14] root             [15] destory     *" << endl;
		cout << "*     [16] Isempty        [17] quit_system                       *" << endl;
		cout << "******************************************************************" << endl;
		cout << "pleae choose:";
		cin >> select;
		switch (select)
		{
			case 1:
				cout << "please enter:";
				bt.CreatBintree();
				break;
			case 2:
				bt.PreOrder();
				cout << endl;
				break;
			case 3:
				bt.InOrder();
				cout << endl;
				break;
			case 4:
				bt.PostOrder();
				cout << endl;
				break;
			case 5:
				cout << bt.Height() << endl;
				break;
			case 6:
				cout << bt.Size() << endl;
				break;
			case 7:
				cout << "please enter what u want to search:";
				cin >> c;
				cout << bt.Search(c) << endl;
				break;
			case 8:
				cout << "please enter what u want to search:";
				cin >> c;
				cout << bt.PreOrder_Find(c) << endl;
				break;
			case 9:
				cout << "please enter what u want to search:";
				cin >> c;
				cout << bt.InOrder_Find(c) << endl;
				break;
			case 10:
				cout << "please enter what u want to search:";
				cin >> c;
				cout << bt.PostOrder_Find(c) << endl;
				break;
			case 11:
				cout << "whose parent u wanna find:";
				cin >> c;
				cout << bt.Parent(bt.Search(c)) << endl;
				break;
			case 12:
				cout << "whose leftchild u wanna find:";
				cin >> c;
				cout << bt.Leftchild(c) << endl;
				break;
			case 13:
				cout << "whose rightchild u wanna find:";
				cin >> c;
				cout << bt.Rightchild(c) << endl;
				break;
			case 14:
				cout << bt.Root() << endl;
				break;
			case 15:
				bt.Destory();
				break;
			case 16:
				if (bt.IsEmpty())
				{
					cout << "it is an empty bintree" << endl;
				}
				else
				{
					cout << "it is not an empty bintree" << endl;
				}
				break;
			case 17:
				bt.quit_system(select);
				break;
			default:
				break;

		}
	}
	return 0;
}


求高度:


技术分享


中序遍历:


技术分享


中序遍历查找:


技术分享


推断是否为空树:


技术分享


求其父节点:


技术分享


后序遍历:


技术分享


前序遍历:


技术分享


退出系统:


技术分享


求其右孩子:


技术分享


求根:


技术分享


查找:


技术分享


求节点个数:


技术分享



【数据结构】二叉树(c++)