基于C++类和指针实现二叉树

1、二叉树的定义

  二叉树(Binary Tree)是一种特殊的树型结构,每个节点至多有两棵子树,且二叉树的子树有左右之分,次序不能颠倒。

  由定义可知,二叉树中不存在度(结点拥有的子树数目)大于2的节点。二叉树形状如下下图所示:基于C++类和指针实现二叉树

2、二叉树的性质

(1)在二叉树中的第i层上至多有2^(i-1)个结点(i>=1)。备注:^表示此方

(2)深度为k的二叉树至多有2^k-1个节点(k>=1)。

(3)对任何一棵二叉树T,如果其终端结点数目为n0,度为2的节点数目为n2,则n0=n2+1。

满二叉树:深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。

完全二叉树:深度为k具有n个结点的二叉树,当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。

可以得到一般结论:满二叉树和完全二叉树是两种特殊形态的二叉树,满二叉树肯定是完全二叉树,但完全二叉树不不一定是满二叉树。

举例如下图是所示:

基于C++类和指针实现二叉树

(4)具有n个节点的完全二叉树的深度为log2n + 1。

3、二叉树的存储结构

  可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法,因为其非常灵活,方便二叉树的操作。二叉树的二叉链表存储结构如下所示:

1 typedef struct binary_tree_node
2 {
3     int elem;
4     struct binary_tree_node *left;
5     struct binary_tree_node *right;
6 }binary_tree_node,*binary_tree;

举例说明二叉链表存储过程,如下图所示:

基于C++类和指针实现二叉树

从图中可以看出:在还有n个结点的二叉链表中有n+1个空链域。

4、遍历二叉树

  遍历二叉树是按照指定的路径方式访问书中每个结点一次,且仅访问一次。由二叉树的定义,我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行,因此可以得到如下最基本的三种遍历方法:

(1)先根遍历(先序遍历):如果二叉树为空,进行空操作;否则,先访问根节点,然后先根遍历左子树,最后先根遍历右子树。采用递归形式实现代码如下:

基于C++类和指针实现二叉树
1 void preorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         printf("%d\t",root->elem);
6         preorder_traverse_recursive(root->left);
7         preorder_traverse_recursive(root->right);
8     }
9 }
基于C++类和指针实现二叉树

具体过程如下图所示:

基于C++类和指针实现二叉树

(2)中根遍历(中序遍历):如果二叉树为空,进行空操作;否则,先中根遍历左子树,然后访问根结点,最后中根遍历右子树。递归过程实现代码如下:

基于C++类和指针实现二叉树
1 void inorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         inorder_traverse_recursive(root->left);
6         printf("%d\t",root->elem);
7         inorder_traverse_recursive(root->right);
8     }
9 }
基于C++类和指针实现二叉树

具体过程如下图所示:

基于C++类和指针实现二叉树

(3)后根遍历(后序遍历):如果二叉树为空,进行空操作;否则,先后根遍历左子树,然后后根遍历右子树,最后访问根结点。递归实现代码如下:

基于C++类和指针实现二叉树
1 void postorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         postorder_traverse_recursive(root->left);
6         postorder_traverse_recursive(root->right);
7         printf("%d\t",root->elem);
8     }
9 }
基于C++类和指针实现二叉树

具体过程如下图所示:

基于C++类和指针实现二叉树

用类和指针实现的二叉树:

#include<iostream>
using namespace std;
struct tree
{
	int data;
	tree *left,*right;
};
class Btree
{
	static int n;
	static int m;
public:
	tree *root;
	Btree()
	{
		root=NULL;
	}
	void create_Btree(int);
	void Preorder(tree *);                  //先序遍历
	void inorder(tree *);                   //中序遍历
	void Postorder(tree *);                 //后序遍历
	void display1() {Preorder(root); cout<<endl;}
	void display2() {inorder(root);cout<<endl;}
	void display3() {Postorder(root); cout<<endl;}  
	int count(tree *);                      //计算二叉树的个数
	int findleaf(tree *);                   //求二叉树叶子的个数
	int findnode(tree *);                   //求二叉树中度数为1的结点数量,这是当初考数据结构时候的最后一道题目
};                                          
int Btree::n=0;
int Btree::m=0;
void Btree::create_Btree(int x)
{
	tree *newnode=new tree;
	newnode->data=x;
	newnode->right=newnode->left=NULL;
	if(root==NULL)
		root=newnode;
	else
	{
		tree *back;
		tree *current=root;
		while(current!=NULL)
		{
			back=current;
			if(current->data>x)
				current=current->left;
			else
				current=current->right;
		}
		if(back->data>x)
			back->left=newnode;
		else
			back->right=newnode;
	}
}
int Btree::count(tree *p)
{
	if(p==NULL)
		return 0;
	else
		return count(p->left)+count(p->right)+1;      //这是运用了函数嵌套即递归的方法。
}
void Btree::Preorder(tree *temp)    //这是先序遍历二叉树,采用了递归的方法。
{
	if(temp!=NULL)
	{
		cout<<temp->data<<" ";
		Preorder(temp->left);
		Preorder(temp->right);
	}
}
void Btree::inorder(tree *temp)      //这是中序遍历二叉树,采用了递归的方法。
{
	if(temp!=NULL)
	{
		inorder(temp->left);
		cout<<temp->data<<" ";
		inorder(temp->right);
	}
}
void Btree::Postorder(tree *temp)     //这是后序遍历二叉树,采用了递归的方法。
{
	if(temp!=NULL)
	{
		Postorder(temp->left);
		Postorder(temp->right);
		cout<<temp->data<<" ";
	}
}
int Btree::findleaf(tree *temp)
{
	if(temp==NULL)return 0;
	else
	{
		if(temp->left==NULL&&temp->right==NULL)return n+=1;
		else
		{
			findleaf(temp->left);
			findleaf(temp->right);
		}
		return n;
	}
}
int Btree::findnode(tree *temp)
{
	if(temp==NULL)return 0;
	else
	{
		if(temp->left!=NULL&&temp->right!=NULL)
		{
			findnode(temp->left);
			findnode(temp->right);
		}
		if(temp->left!=NULL&&temp->right==NULL)
		{
			m+=1;
			findnode(temp->left);
		}
		if(temp->left==NULL&&temp->right!=NULL)
		{
			m+=1;
			findnode(temp->right);
		}
	}
	return m;
}


void main()
{
	Btree A;
	int array[]={100,4,2,3,15,35,6,45,55,20,1,14,56,57,58};
	int k;
	k=sizeof(array)/sizeof(array[0]);
	cout<<"建立排序二叉树顺序: "<<endl;
	for(int i=0;i<k;i++)
	{
		cout<<array[i]<<" ";
		A.create_Btree(array[i]);
	}
	cout<<endl;
	cout<<"二叉树节点个数: "<<A.count(A.root)<<endl;
	cout<<"二叉树叶子个数:"<<A.findleaf(A.root)<<endl;
	cout<<"二叉树中度数为1的结点的数量为:"<<A.findnode(A.root)<<endl;
	cout<<endl<<"先序遍历序列: "<<endl;
	A.display1();
	cout<<endl<<"中序遍历序列: "<<endl;
	A.display2();
	cout<<endl<<"后序遍历序列: "<<endl;
	A.display3();
}

基于C++类和指针实现二叉树

基于C++类和指针实现二叉树,布布扣,bubuko.com

基于C++类和指针实现二叉树

上一篇:js中通用随机洗牌方法


下一篇:htpasswd命令的使用