二叉树

在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为节点）按分支关系组织起来的结构。二叉树(Binary Tree)是每个节点最多有两个子树的有序树。通常子树被称作"左子树"(left subtree)和"右子树"(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点后，每个顶点定义了唯一的根节点，和最多2个子节点。然而，没有足够的信息来区分左节点和右节点。

二叉树的存储结构

二叉树常用链式存储。如下图;

最常用的是图a的二叉链表法。

代码实现

下面的代码中我们提供了如下操作：

1. 查找 find()，获取父节点 parent()，左孩子 lchild()，右孩子 rchild()。
2. 各种遍历：前序、中序、后序、层次。
3. 获取树的高度，节点总数。

类定义

#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
using namespace std;
typedef int ElemType;
//二叉树节点
class BTNode   //Binary Tree Node
{
public:
	ElemType data;
	BTNode* lchild;   //左孩子
	BTNode* rchild;   //右孩子
	BTNode(ElemType d, BTNode* left=NULL, BTNode* right=NULL) :data(d), lchild(left), rchild(right){}
};
//二叉树
class BinaryTree
{
private:
	//根节点指针
	BTNode* Root;
	//节点个数
	int size;
public:
	//构造函数
	BinaryTree();
	BTNode* buildTree();
	//析构函数
	~BinaryTree();
	//求树的高度
	int height();
	//获取节点个数
	int getSize()
	{return size;}
	void getHeight(BTNode*, int, int&);
	//指定遍历方式
	void traverse();
	//前序遍历
	void preOrder();
	void preorder(BTNode*);
	//中序遍历
	void inOrder();
	void inorder(BTNode*);
	//后序遍历
	void postOrder();
	void postorder(BTNode*);
	//层次遍历
	void levelOrder();
	//判断树是否为空
	bool empty()
	{return Root == NULL;}
	//获取根节点
	BTNode* root()
	{return Root;}
	//查找指定节点
	bool find(ElemType);
	//获取父节点
	BTNode* parent(ElemType);
	//获取左孩子
	BTNode* lchild(ElemType);
	//获取右孩子
	BTNode* rchild(ElemType);
};

//构造函数
BinaryTree::BinaryTree()
{
	size = 0;
	cout << "输入根节点 ";
	Root = buildTree();
}
BTNode* BinaryTree::buildTree()
{
	ElemType data;
	BTNode* p = NULL;
	cin >> data;
	//输入0结束
	if (data =http://www.mamicode.com/= 0)>
主函数
int main()
{
	cout << "******二叉树******" << endl;
	BinaryTree tree;
	cout << "树的高度是 " << tree.height() << endl;
	cout << "树中共有节点个数 " << tree.getSize() << endl;
	tree.traverse();
	ElemType data = http://www.mamicode.com/2;>
运行：


遍历算法的非递归实现
//前序遍历非递归算法
void BinaryTree::preOrderWithoutRecursion()
{
	if (!empty())
	{
		stack<BTNode*> s;
		BTNode* p = Root;
		s.push(p);
		while (!s.empty())
		{
			cout << setw(4) << p->data;
			if (p->rchild)
				s.push(p->rchild);
			if (p->lchild)
				p = p->lchild;
			else
			{//左子树访问完了，访问右子树
				p = s.top();
				s.pop();
			}
		}
		cout << endl;
	}
}

//中序遍历的非递归实现
void BinaryTree::inOrderWithoutRecursion()
{
	if (!empty())
	{
		stack<BTNode*> s;
		BTNode* p = Root;
		while (!s.empty() || p)
		{
			if (p)
			{//一直下降到最左边
				s.push(p);
				p = p->lchild;
			}
			else
			{
				p = s.top();
				s.pop();
				cout << setw(4) << p->data;
				p = p->rchild;
			}
		}
		cout << endl;
	}
}


完整代码下载：二叉树
转载请注明出处：http://blog.csdn.net/zhangxiangdavaid/article/details/36634411
若有所帮助，顶一个哦！
专栏目录：数据结构与算法目录