hnsfdxyc

用户名：00000152

访问量：24623

签　名：

等　　级
排　　名	362
经　　验	5240
参赛次数	0
文章发表	24
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

快速排序的原理你真正了解多少？
浏览：927

栈的基本操作（附有完整代码）
浏览：1089

树了解一下（c++）
浏览：362

你可能喜欢

树了解一下（c++）

　　作者: hnsfdxyc　　　　发表时间：2019-08-09 13:23:13 浏览：362　|　评论：0　

### 树的种类
一起来看看树的种类吧

------------

#### 何为二叉树
**定义：**二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
**用途：**二叉树常被用于实现二叉查找树和二叉堆。
#### 何为满二叉树
**定义**：一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。
**特点：**这种树的特点是每一层上的节点数都是最大节点数。
#### 何为完全二叉树
**定义：**在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。
**特点：**具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子节点，至多有2k-1个节点。

## 树的遍历
**树的遍历共分为3种：**
先序遍历、中序遍历、后序遍历（这里的“序”为根节点的遍历顺序），故而遍历顺序可理解为：

------------

**先序遍历：**
根节点 →左子树 → 右子树，在子树中继续应用左子树 → 根节点 → 右子树；
**中序遍历：**
左子树 → 根节点 → 右子树，同理
**后序遍历：**
左子树 → 右子树 → 根节点，同理
```cpp
#include <iostream>
#include <iomanip>
#include <queue>
#define OK 1
#define False 0
#define ll long long
using namespace std;
typedef int Status ;
typedef int Datatype;

typedef struct node
{
	Datatype data;//数据
	struct node *lchild,*rchild;//指向左右孩子的指针 
}BitNode,*Bitree; //Bitree是node结构指针的别名，代表指向BitNode结构体类型的指针

//初始化，构造空二叉树 
Status Init_Bitree(Bitree &T)
{
	T=NULL;
	return OK;
}

//销毁二叉树   
Status Destory_Bitree(Bitree &T)
{
	if(T)
	{
		if(T->lchild)
			Destory_Bitree(T->lchild);
		if(T->rchild)
			Destory_Bitree(T->rchild); 
		free(T);
		T=NULL; 
	}
	return OK;
}

//创建二叉树 
void Create_Bitree(Bitree &T)
{
	char ch;
	cin>>ch;
	if(ch==' ') T=NULL;
	else
	{
		T=(BitNode*)malloc(sizeof(BitNode));
		T->data=ch;
		Create_Bitree(T->lchild);
		Create_Bitree(T->rchild);		
	}
}

//清空二叉树
Status Clear_Bitree(Bitree &T)
{
	if(T==NULL)
	{
		return OK;
	}
	Clear_Bitree(T->lchild);
	Clear_Bitree(T->rchild);
	free(T);
}

//判断二叉树是否为空
Status Empty_Bitree(Bitree &T)
{
	if(T==NULL) return OK;
	else return False;
}

//二叉树的深度
Status Depth_Bitree(Bitree T)
{
	int hl=0,hr=0;
	if(T==NULL) return 0;
	else
	{
		hl=Depth_Bitree(T->lchild); 
		hr=Depth_Bitree(T->rchild);//递归，先左后右 
		return max(hl,hr)+1;
	}
}

//Root_ 返回T的根
Datatype Root_Bitree(Bitree T)
{
	if(T==NULL) return 0;
	else return T->data;
}

//返回某个结点的值
Datatype Value_Bitree(Bitree p)
{
	return p->data;
}

//结点总数 
int Count_Bitree(Bitree T)
{
	if(T)
	{
		return Count_Bitree(T->lchild)+Count_Bitree(T->rchild)+1;
	}else return 0;
 } 
 
//叶子结点
int Leaves_Bitree(Bitree T)
{
	if(T==NULL) return 0;
	if(T->lchild==NULL&&T->rchild==NULL)
		return 1;
	else return Leaves_Bitree(T->lchild)+Leaves_Bitree(T->rchild);
 } 
 
//返回节点的双亲
Datatype Parent_Bitree(Bitree T,Datatype e)
{
	if(T)
	{
		queue<Bitree> q;
		while(!q.empty()) q.pop();//清空
		q.push(T);//根 入队 
		while(!q.empty()) 
		{
			Bitree temp=q.front();//取出队首 
			q.pop();
			if((temp->lchild&&temp->lchild->data==e)||(temp->rchild&&temp->rchild->data==e))
				return temp->data;
			else 
			{
				if(temp->lchild)
					q.push(temp->lchild);
				if(temp->rchild)
					q.push(temp->rchild);
			}
		 } 
	}
    return False;	
}

//返回某个值在数中的节点的指针 
Bitree NodePoint_Bitree(Bitree T,Datatype e)
{
	if(T==NULL) return False;
	Bitree P;
	queue<Bitree> q;
	while(!q.empty()) q.pop();
	P=T;
	q.push(P);
	while(!q.empty())
	{
		Bitree temp=q.front();
		q.pop();
		if(temp->data==e) return temp;
		if(temp->lchild) q.push(temp->lchild);
		if(temp->rchild) q.push(temp->rchild);
	}
	return False;//说明没找到 
}

//左孩子 
Datatype LeftChild_Bitree(Bitree p)
{
	if(p->lchild)
	{
		return p->lchild->data;
	}
	else return False;
}

//右孩子 
Datatype RightChild_Bitree(Bitree p)
{
	if(p->rchild)
	{
		return p->rchild->data;
	}
	else return False;
}

//左兄弟 
Datatype LeftSibing_Bitree(Bitree T,Datatype e)
{
	Bitree P;
	Init_Bitree(P);
	if(T)
	{
		P=NodePoint_Bitree(T,Parent_Bitree(T,e));
		if(P->lchild&&P->rchild&&P->rchild->data==e)
		 return P->lchild->data;
	}else return False;
}

//右兄弟
Datatype RightSibing_Bitree(Bitree T,Datatype e)
{
	Bitree P;
	Init_Bitree(P);
	if(T)
	{
		P=NodePoint_Bitree(T,Parent_Bitree(T,e));
		if(P->lchild&&P->rchild&&P->lchild->data==e)
			return P->rchild->data;
	}else return False;
 } 
 
//结点赋值
void Assign_Bitree(Bitree p,Datatype value)
{
	p->data=value;
}

//先序遍历 
void PreOrderTraverse(Bitree T,int level)
{
	if(T)
	{
		cout<<T->data<<" "<<level<<endl;//访问根节点 
		PreOrderTraverse(T->lchild,level+1);//先遍历左子树
		PreOrderTraverse(T->rchild,level+1);//最后再遍历右子树 
	}
}
//中序遍历 
void InOrderTraverse(Bitree T,int level)
{
	if(T)
	{
		InOrderTraverse(T->lchild,level+1);//先遍历左子树 
		cout<<T->data<<" "<<level<<endl;//再访问根节点
		InOrderTraverse(T->rchild,level+1);//最后遍历右子树 
	}
}
//后序遍历
void  PostOrderTraverse(Bitree T,int level)
{
	if(T)
	{
		PostOrderTraverse(T->lchild,level+1);//先访问左子树 
		PostOrderTraverse(T->rchild,level+1);//再访问右子树 
		cout<<T->data<<" "<<level<<endl;//最后访问根节点 
	}
}

//删除子树
/*LR==0 代表 左子树 LR==1 代表右子树*/ 
Status DeleteChild_Bitree(Bitree P,int LR)
{
	if(LR==0)
	{
		if(P->lchild)
		{
			Destory_Bitree(P->lchild);
			return OK;
		}
	}else if(LR==1)
	{
		if(P->rchild)
		{
			Destory_Bitree(P->rchild);
			return OK;
		}
	}return False;
 } 
 
//插入子树
Status InsertChild_Bitree(Bitree P,int LR,Bitree c)
{
	if(P)
	{
		if(LR==0)
		{
			c->rchild=P->lchild;
			P->lchild=c;
		}else if(LR==1)
		{
			c->rchild=P->rchild;
			P->rchild=c;
		}
		return OK;
	}else return False;
 } 
void Menu()
{
	cout<<"                   二叉树基本操作                  "<<endl; 
	cout<<"***************************************************"<<endl;
	cout<<"*********        1.建立二叉树         *************"<<endl;
	cout<<"*********        2.清空二叉树         *************"<<endl;
	cout<<"*********        3.销毁二叉树         *************"<<endl;
	cout<<"*********        4.先序遍历二叉树     *************"<<endl;
	cout<<"*********        5.中序遍历二叉树     *************"<<endl;
	cout<<"*********        6.后序遍历二叉树     *************"<<endl;
	cout<<"*********        7.二叉树的高度       *************"<<endl;
	cout<<"*********        8.二叉树结点数       *************"<<endl;
	cout<<"*********        9.二叉树叶子数       *************"<<endl;
	cout<<"*********        10.结点的左右孩子    *************"<<endl;
	cout<<"*********        11.结点的左右兄弟    *************"<<endl;
	cout<<"*********        12.结点的双亲        *************"<<endl;
	cout<<"*********        13.退出              *************"<<endl; 
	cout<<"***************************************************"<<endl; 
 } 
int main()
{
	
	Bitree Tree;
	Init_Bitree(Tree);
	int option;
	Menu(); 
	do
	{
		cout<<"请输入你想进行的操作：";
		cin>>option; 
		switch(option)
		{
			case 1://创建
				cout<<"创建二叉树："; 
				Create_Bitree(Tree); 
				cout<<"创建成功"<<endl;
				break;
			case 2://清空 
				if(Clear_Bitree(Tree))
					cout<<"清空成功"<<endl;
				else cout<<"清空失败"<<endl; 
				break;
			case 3://销毁 
				if(Destory_Bitree(Tree))
					cout<<"销毁成功"<<endl;
				else cout<<"销毁失败"<<endl; 
				break;
			case 4://先序 
				cout<<"先序遍历："<<endl;
				PreOrderTraverse(Tree,1);
				cout<<endl;
				break;
			case 5://中序 
				cout<<"中序遍历："<<endl;
				InOrderTraverse(Tree,1);
				cout<<endl;
				break;
			case 6://后序 
				cout<<"后序遍历："<<endl; 
				PostOrderTraverse(Tree,1); 
				cout<<endl;
				break;
			case 7://高度 
				cout<<"高度： ";
				cout<<Depth_Bitree(Tree)<<endl;
				break;
			case 8:
				cout<<"结点数： ";
				cout<<Count_Bitree(Tree)<<endl;
				break;
			case 9:
				cout<<"叶子结点数： ";
				cout<<Leaves_Bitree(Tree)<<endl;
				break; 
			case 10://左右孩子 
				cout<<"输入你想查找的结点值：";
				Datatype e;
				cin>>e;
				Bitree p;
				Init_Bitree(p);
				p=NodePoint_Bitree(Tree,e); 
				if(LeftChild_Bitree(p))
				{
					cout<<"左子树："<<LeftChild_Bitree(p)<<endl; 
				}else cout<<"左子树："<<"不存在"<<endl;
				if(RightChild_Bitree(p))
				{
					cout<<"右子树："<<RightChild_Bitree(p)<<endl; 
				}else cout<<"右子树："<<"不存在"<<endl;
				break;
			case 11:
				cout<<"输入你想查找的结点值：";
				Datatype val;
				cin>>val;
				if(LeftSibing_Bitree(Tree,val))
				{
					cout<<"左兄弟："<<LeftSibing_Bitree(Tree,val)<<endl;
				 } else cout<<"左兄弟："<<"不存在"<<endl;
				if(RightSibing_Bitree(Tree,val))
				{
					cout<<"右兄弟："<<RightSibing_Bitree(Tree,val)<<endl;
				}else cout<<"右兄弟："<<"不存在"<<endl;
			case 12://双亲 
				Datatype c;
				cout<<"输入你想查找的结点：";
				cin>>c; 
				if(Parent_Bitree(Tree,c))
				{
					cout<<Parent_Bitree(Tree,c)<<endl;
				}else cout<<"不存在"<<endl;
				break;
			case 13:
				cout<<"退出！！！"<<endl;
				return 0;
		}
			system("pause");
	 }while(1); 
	return 0;
}
//abc##de#g##f### 
/*
      a
     / \
    b  
   / \
  c  d
  	/ \
   e  f 
	\
	g
*/
/*abc##d##efgh#####*/
/*
         a
       /   \
	  b     e
	 / \    /
	c  d   f 
          /
   		 g
		/
	   h

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

hnsfdxyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

Hello, world! （Java代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

C二级辅导-计负均正（C语言代码）

树了解一下（c++）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-printf基础练习2 （C++代码）

用筛法求之N内的素数。（C语言代码）

1128题解（返回值为数组的情况）

罗列完美数（C语言代码）

C二级辅导-计负均正（C语言代码）

输出九九乘法表（C语言代码）

hnsfdxyc

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

Hello, world! （Java代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

C二级辅导-计负均正 （C语言代码）

树了解一下（c++）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-printf基础练习2 （C++代码）

用筛法求之N内的素数。 （C语言代码）

1128题解（返回值为数组的情况）

罗列完美数 （C语言代码）

C二级辅导-计负均正 （C语言代码）

输出九九乘法表 （C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

C二级辅导-计负均正（C语言代码）

　　评论区

用筛法求之N内的素数。（C语言代码）

罗列完美数（C语言代码）

C二级辅导-计负均正（C语言代码）

输出九九乘法表（C语言代码）