二叉树的链式存储实现

2018-07-15

二叉链表

数组表示法用于完全二叉树的存储表示非常有效，但表示一般二叉树则不是很理想。此外，在一棵树中进行插入和删除操作时，为了反应结点层次的变动，可能需要移动许多的结点，这样降低了算法的效率，而使用了链表表示可以克服这样的缺点。
根据二叉树的定义，可以设计出二叉树节点的构造。二叉树的每一个结点至少应该包括三个域：数据、左孩子、右孩子。这种链表结构一般被叫做二叉链表。使用这种链表可以很方便的表示和找到它的子女，但找到它的双亲却很困难。为了便于查找双亲，我们还可以增加一个双亲指针域，这种结构被称为三叉链表。
结构如下：

这里写图片描述

二叉链表的类定义

三叉链表和二叉链表类似，本文只讨论二叉链表。下面给出二叉链表的类定义。

#ifndef _HEAD_
#define _HEAD_

#include <iostream>
typedef int  DataType;
typedef struct BinTreeNode
{
	DataType data;
	BinTreeNode *leftchild, *righutchild;
}Binarynode;

class BinaryTree
{
public:
	BinaryTree()
		:root(NULL){}
	BinaryTree(BinaryTree& s);
	~BinaryTree();
	void creatBinTree(Binarynode*&subTree);
	void ceratBinTree();
	bool IsEmpty()
	{
		return root == NULL ? 1 : 0;
	}
	Binarynode *find();//搜索
	void PreOrder();
	void PreOrder(Binarynode *subTree);//前序遍历
	void InOrder();
	void InOrder(Binarynode *subTree);//中序
	void PostOrder();
	void PostOrder(Binarynode *subTree);//后序
	int count(Binarynode* subTree);//统计节点个数
	int count();
	int Hight();
	int Hight(Binarynode* subTree);//求树高度
	void copy();
	BinaryTree* copy(Binarynode*&Tree);//复制二叉树
private:
	Binarynode *root;
};

#endif

二叉链表的实现

#include <iostream>
using namespace std;
typedef char  DataType;
DataType RefValue = '#';//输入结束符
typedef struct BinTreeNode
{
	DataType data;
	BinTreeNode *leftchild, *rightchild;
}Binarynode;

class BinaryTree
{
public:
	BinaryTree()
		:root(NULL){}
	BinaryTree(BinaryTree& s);
	~BinaryTree();
	bool IsEmpty();
	Binarynode *find(DataType &item);//搜索
	void creatBinTree();
	void creatBinTree(Binarynode*&subTree);
	void PreOrder();
	void PreOrder(Binarynode *subTree);//前序遍历
	void InOrder();
	void InOrder(Binarynode *subTree);//中序
	void PostOrder();
	void PostOrder(Binarynode *subTree);//后序
	int count(Binarynode* subTree);//统计节点个数
	int count();
	int Hight();
	int Hight(Binarynode* subTree);//求树高度
	void copy();
	Binarynode* copy(Binarynode*&Tree);//复制二叉树
	void destory(Binarynode*&Tree);//销毁
private:
	Binarynode *root;
};
bool BinaryTree::IsEmpty()
{
	return root == NULL ? 1 : 0;
}
Binarynode* BinaryTree::find(DataType& item)
{
	if (item != NULL)
	{
		Binarynode *tmp = root;
		Binarynode*tmpl = tmp->leftchild;
		Binarynode*tmpr = tmp->rightchild;
		DataType temp = root->data;
		while (tmpl)
		{
			if (temp != item)
			{
				tmpl = tmpl->leftchild;
			}
			cout << "i find it";
			return tmpl;
		}
		while (tmpr)
		{
			if (temp != item)
			{
				tmpr = tmpr->rightchild;
			}
			cout << "i find it ";
			return tmpr;
		}


	}
	cout << "can't find it";
	return  NULL;
}
void BinaryTree::PreOrder()
{
	PreOrder(root);
}
void BinaryTree::PreOrder(Binarynode*subTree)
{
	if (subTree != NULL)
	{
		cout << subTree->data;
		PreOrder(subTree->leftchild);
		PreOrder(subTree->rightchild);
	}
}
void BinaryTree::InOrder()
{
	InOrder(root);
}
void BinaryTree::InOrder(Binarynode* subTree)
{
	if (subTree != NULL)
	{
		InOrder(subTree->leftchild);
		cout << subTree->data;
		InOrder(subTree->rightchild);
	}
}void BinaryTree::PostOrder()
{
	PostOrder(root);
}
void BinaryTree::PostOrder(Binarynode*subTree)
{
	if (subTree != NULL)
	{
		PostOrder(subTree->leftchild);
		PostOrder(subTree->rightchild);
		cout << subTree->data;
	}
}
int BinaryTree::Hight()
{
	return Hight(root);
}
int BinaryTree::Hight(Binarynode* subTree)
{
	if (subTree == NULL)
	{
		return 0;
	}
	else
	{
		int dep1 = Hight(subTree->leftchild);
		int dep2 = Hight(subTree->rightchild);
		if (dep1>dep2)
		{
			return dep1 + 1;
		}
		else
		{
			return dep2 + 1;
		}
	}
}
int BinaryTree::count()
{
	return count(root);
}
int BinaryTree::count(Binarynode*subTree)
{
	if (subTree != NULL)
	{
		return 1 + count(subTree->leftchild) + count(subTree->rightchild);
	}
	return 0;
}

void BinaryTree::copy()
{
	copy(root);
}
Binarynode* BinaryTree::copy(Binarynode*&Tree)
{
	if (Tree == NULL)
	{
		return NULL;

	}
	else
	{
		Binarynode *tmp = new Binarynode;
		tmp->data = Tree->data;
		tmp->leftchild = copy(Tree->leftchild);
		tmp->rightchild = copy(Tree->rightchild);
		return tmp;
	}
}
void BinaryTree::creatBinTree(Binarynode*&subTree)
{
	DataType item;

	cin >> item;
	if (item != RefValue)
	{
		subTree = new Binarynode;
		subTree->data = item;
		if (subTree == NULL)
		{
			cout << "存储分配错误";
			exit(1);

		}
		creatBinTree(subTree->leftchild);
		creatBinTree(subTree->rightchild);

	}
	else
	{
		subTree = NULL;
	}
}
void BinaryTree::creatBinTree()
{
	creatBinTree(root);
}


void BinaryTree::destory(Binarynode*&Tree)
{

	if (Tree != NULL)
	{
		return;
	}
	destory(Tree->leftchild);
	destory(Tree->rightchild);
	delete Tree;
}

BinaryTree::~BinaryTree()
{
	destory(root);
}


BinaryTree::BinaryTree(BinaryTree &s)
{
	root = copy(s.root);
}
int main()
{
	BinaryTree subTree;
	cout << "输入节点，空结点以#代替:";
	subTree.creatBinTree();
	cout << "前序遍历：";
	subTree.PreOrder();
	cout << endl<<"中序遍历：";
	subTree.InOrder();
	cout << endl << "后序遍历：";
	subTree.PostOrder();
	cout<<endl<<"结点个数："<<subTree.count()<<endl;
	cout << "树的高度："<<subTree.Hight()<<endl;
	system("pause");
	return 0;
}

运行结果

关于链表的输入

这里写图片描述

本文总阅读量次