数据结构试验教程-二叉树

博主：酱油瓶
发布时间：2021 年 11 月 15 日
1662 次浏览
暂无评论
6526字数
分类：学习软件工程

本文为本人按照书本要求所写作业，算法并非最优，仅供参考
</div>

书为：《数据结构实践教程》清华大学出版社 主编：徐慧
</div>

# 试验7.1 二叉树叶子结点个数计算

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

学号：2021.11.1

## 1.问题描述

已知一棵二叉树，求该二叉树中叶子结点的个数

## 2.数据结构设计

### 2.1 存储设计

二叉树采用二叉链表为存储设计

```c++
template<class T>
struct BTNode
{
	T data;			//数据域
	BTNode* lchild;		//指向左子树的指针
	BTNode* rchild;		//指向右指针的指针
};
```

### 2.2 函数设计

需要用到的操作:构造函数，创建二叉树，图形显示，计算叶子节点个数，获取根节点

```c++
template<class T>
class BinaryTree
{
	BTNode<T>* BT;
public:
	BinaryTree() { BT = NULL; }				//构造函数
	void CreateBiTree(T end);				//输入先序序列创建二叉树
	void DisplayBTree(BTNode<T>* bt, int level = 1);	//图形显示二叉树
	void CountLeaf(BTNode<T>* root, int& count);		//二叉树叶子节点个数
	BTNode<T>* GetRoot();					//获取二叉树的根节点
};
```

## 3.算法设计

### 3.1 构造函数，创建二叉树，图形显示，获取根节点均按照书本实践操作

```c++
template<class T>
void BinaryTree<T>::CreateBiTree(T end)		//用先序序列创建二叉树，end为空指针标识
{
	cout << "请按先序序列的顺序输入二叉树，"<<end<<"为空指针域标志：" << endl;
	BTNode<T>* p;
	T x;
	cin >> x;
	if (x == end)return;
	p = new BTNode<T>;
	if (!p)
	{
		cout << "申请内存失败！" << endl;
		exit(-1);
	}
	p->data = x;
	p->lchild = NULL;
	p->rchild = NULL;
	BT = p;
	create(p, 1, end);
	create(p, 2, end);
}

template<class T>
void BinaryTree<T>::DisplayBTree(BTNode<T>* bt, int level)	//图形显示二叉树
{
	if (bt)
	{
		DisplayBTree(bt->rchild, level + 1);
		cout << endl;
		for (int i = 0; i < level - 1; i++)
			cout << "\t";
		cout << bt->data;
		DisplayBTree(bt->lchild, level + 1);
	}
}

template<class T>
BTNode<T>* BinaryTree<T>::GetRoot()	//获取根节点
{
	return BT;
}

### 3.2 计算叶子结点数量

#### Step 1

函数参数1.二叉树的根节点`BTNode<T>* root`2.计数器`count`

```c++
void BinaryTree<T>::CountLeaf(BTNode<T>* root, int& count) {}
```

#### Step 2

##### Step 2.1

判断树是否为空

```c++
if (root)
```

##### Step 2.2

判断是否为叶子结点，若是则增加计数器

```c++
if (root->lchild == NULL && root->rchild == NULL)
		count++;
```

##### Step 2.3

累计左子树上的叶子和右子树上的叶子

```c++
CountLeaf(root->lchild, count);
CountLeaf(root->rchild, count);
```

### 3.3 主函数

实现二叉树的输入和叶子节点的计算

```c++
BinaryTree<char> tree;				//创建树
tree.CreateBiTree('#');				//以#为空指针表示输入而擦函数
cout << "下面显示的一棵左转了90度的树";
tree.DisplayBTree(tree.GetRoot());		//图形输出树
int count = 0;					//声明计数器
tree.CountLeaf(tree.GetRoot(), count);		//计算叶子结点数量
cout << '\n' << "二叉树叶子结点的个数是：";
cout << count << endl;
```

## 4.测试运行

测试1：

(1)输入二叉树: a b ## c ## ## d ## ##

![](https://snz04pap001files.storage.live.com/y4mjimhcLpcX76P9AY9nkaYLlUUhom4FSRngeUYDLChjTqGVTl5mWp7M2_I3W0mxDMJLndADrIMgL_CChy5YmvnLm7B94cGI4q1-kHT7C1A35sKjHQbRV0Qmhe0_JBCPKRu4_Ic3Tbu4gw13V4yVccffxf5qoGC5tORMpfZ-rZP7FugMCjoswGqoq8Ix2Y0GqX3?width=1734&height=951&cropmode=none "输入")

(2)输出：

![输出](https://snz04pap001files.storage.live.com/y4mPjufLtSoQChfI0PR_V_hOqOXH-GpMv1dAavP1Duank41quKcfvy-bwPxrD86MPx9KFFjLVrjanODKQmf1cFJSlnFVUa-_GbMWy98rdCO6AyM27uDT55tEihoON3zsUigHIfjYumacpdmGC6F6S75XEvHKFXu1xAdw7g796YW4QF1tW6cnMvEyLygn3NoqAny?width=1734&height=951&cropmode=none)

测试2：

输入：a ## ## s d ## ## f ## ##

输出：

![输出](https://snz04pap001files.storage.live.com/y4mx5D3kXq3Uy_xA1JXZ8g74gWryy4N6Ux36lJaJv-vaQUmjkH32dFO94E-ZUYk-SYoUGjql1wBCk_8oFX3jnV1sMRFAKsKcNlM1dT7AHt-rSND_lTCAZoYjPzpMwvm_d8SeDDN0diWs375KiPnoESQ1rMwnLRAiQMh5kj0hcEEUWNz51KLU0AsRJNxrNXQfFF8?width=1734&height=951&cropmode=none)

## 5.调试记录与收获

1. 头文件`BiTree.h`
   ```c++
   #pragma once
   #include<iostream>
   using namespace std;

template<class T>
   struct BTNode
   {
   	T data;				//数据域
   	BTNode* lchild;		//指向左子树的指针
   	BTNode* rchild;		//指向右指针的指针
   };

template<class T>
   class BinaryTree
   {
   	BTNode<T>* BT;
   public:
   	BinaryTree() { BT = NULL; }							//构造函数
   	void CreateBiTree(T end);							//输入先序序列创建二叉树
   	void DisplayBTree(BTNode<T>* bt, int level = 1);	//图形显示二叉树
   	void CountLeaf(BTNode<T>* root, int& count);		//二叉树叶子节点个数
   	BTNode<T>* GetRoot();								//获取二叉树的根节点
   };

template<class T>
   void BinaryTree<T>::CreateBiTree(T end)
   {
   	cout << "请按先序序列的顺序输入二叉树，"<<end<<"为空指针域标志：" << endl;
   	BTNode<T>* p;
   	T x;
   	cin >> x;
   	if (x == end)return;
   	p = new BTNode<T>;
   	if (!p)
   	{
   		cout << "申请内存失败！" << endl;
   		exit(-1);
   	}
   	p->data = x;
   	p->lchild = NULL;
   	p->rchild = NULL;
   	BT = p;
   	create(p, 1, end);
   	create(p, 2, end);
   }

template<class T>
   void BinaryTree<T>::DisplayBTree(BTNode<T>* bt, int level)
   {
   	if (bt)
   	{
   		DisplayBTree(bt->rchild, level + 1);
   		cout << endl;
   		for (int i = 0; i < level - 1; i++)
   			cout << "\t";
   		cout << bt->data;
   		DisplayBTree(bt->lchild, level + 1);
   	}
   }

template<class T>
   void BinaryTree<T>::CountLeaf(BTNode<T>* root, int& count)
   {
   	if (root)
   	{
   		if (root->lchild == NULL && root->rchild == NULL)
   			count++;
   		CountLeaf(root->lchild, count);
   		CountLeaf(root->rchild, count);
   	}
   }

template<class T>
   BTNode<T>* BinaryTree<T>::GetRoot()
   {
   	return BT;
   }

template<class T>
   static int create(BTNode<T>* p, int k, T end)
   {
   	BTNode<T>* q;
   	T x;
   	cin >> x;
   	if (x != end)
   	{
   		q = new BTNode<T>;
   		q->data = x;
   		q->lchild = NULL;
   		q->rchild = NULL;
   		if (k == 1)p->lchild = q;
   		if (k == 2)p->rchild = q;
   		create(q, 1, end);
   		create(q, 2, end);
   	}
   	return 0;
   }
   ```
2. 主函数`main.cpp`
   ```c++
   #include<iostream>
   #include"BiTree.h"
   using namespace std;

int main()
   {
   	BinaryTree<char> tree;
   	tree.CreateBiTree('#');
   	cout << "下面显示的一棵左转了90度的树";
   	tree.DisplayBTree(tree.GetRoot());
   	int count = 0;
   	tree.CountLeaf(tree.GetRoot(), count);
   	cout << '\n' << "二叉树叶子结点的个数是：";
   	cout << count << endl;
   }
   ```

# 试验7.2 二叉树相似问题

## 1.问题描述

两棵二叉树相似，指要么他们都为空或都只有以个根节点，要么它们的左右子树均相似。本问题是：设计一个算法，判断两棵二叉树是否相似。

## 2.数据结构设计

### 2.1 存储设计

使用二叉树的二叉链表存储

```c++
template<class T>
struct BTNode
{
	T data;				//数据域
	BTNode* lchild;			//指向左子树的指针
	BTNode* rchild;			//指向右指针的指针
};
```

### 2.2 函数设计

需要用到的操作:构造函数，创建二叉树，获取根节点，判断两棵二叉树是否相似

```c++
template<class T>
class BinaryTree
{
	BTNode<T>* BT;
public:
	BinaryTree() { BT = NULL; }				//构造函数
	void CreateBiTree(T end);				//输入先序序列创建二叉树
	BTNode<T>* GetRoot();					//获取二叉树的根节点
	int Like(BTNode<T>* A, BTNode<T>* B);			//判断两棵二叉树是否相似
};
```

## 3.算法设计

### 3.1 构造函数，创建二叉树，获取根节点

```c++
//从键盘输入先序序列创建一个二叉树
template<class T>
void BinaryTree<T>::CreateBiTree(T end)		//end为空指针标识
{
	cout << "请按先序序列的顺序输入二叉树，" << end << "为空指针域标志：" << endl;
	BTNode<T>* p;
	T x;
	cin >> x;
	if (x == end)return;
	p = new BTNode<T>;
	if (!p)
	{
		cout << "申请内存失败！" << endl;
		exit(-1);
	}
	p->data = x;
	p->lchild = NULL;
	p->rchild = NULL;
	BT = p;
	create(p, 1, end);
	create(p, 2, end);
}

template<class T>
static int create(BTNode<T>* p, int k, T end)
{
	BTNode<T>* q;
	T x;
	cin >> x;
	if (x != end)
	{
		q = new BTNode<T>;
		q->data = x;
		q->lchild = NULL;
		q->rchild = NULL;
		if (k == 1)p->lchild = q;
		if (k == 2)p->rchild = q;
		create(q, 1, end);
		create(q, 2, end);
	}
	return 0;
}
//获取二叉树的根节点
template<class T>
BTNode<T>* BinaryTree<T>::GetRoot()
{
	return BT;
}
```

### 3.2 判断两棵二叉树是否有相似性

#### Step 1

设计判断相似方法`Like(BTNode<T>* A, BTNode<T>* B)`，该算法功能是若A与B相似，函数返回1，否则返回0。

```c++
int Like(BTNode<T>* A, BTNode<T>* B) {}		//Like(二叉树A的根节点，二叉树B的根节点)
```

#### Step 2

##### Step 2.1

若A=B=NULL，则A与B相似，即Like(A,B)=1

```c++
if (A == NULL && B == NULL) 
{
	return 1;
}
```

##### Step 2.2

若A与B中有一个为NULL，另一个不为NULL，则A与B不相似，即Like(A,B)=0

```c++
else if (A == NULL || B == NULL)
{
	return 0;
}
```

##### Step 2.3

采用递归方法，进一步判断A的左子树和B的左子树，A的右子树和B的右子树是否相似

```c++
Like(A->lchild, B->lchild);
Like(A->rchild, B->rchild);
```

### 3.3 主函数

实现二叉树的输入和相似比较

```c++
BinaryTree<char>tree1;//创建二叉树tree1
BinaryTree<char>tree2;//创建二叉树tree2
cout << "输入二叉树A：" << endl;
tree1.CreateBiTree('#');//输入二叉树tree1
cout << "输入二叉树B：" << endl;
tree2.CreateBiTree('#');//输入二叉树tree2
if (tree1.Like(tree1.GetRoot(), tree2.GetRoot()))//判断相似性
{
	cout << "A与B相似" << endl;
}
else
{
	cout << "A与B不相似" << endl;
}
```

## 4.运行测试

### 4.1 测试1

1. 运行程序
   ![](https://snz04pap001files.storage.live.com/y4mEAtMvzlab9hyeHR9dpWu6hyIioMsM8pXhK1JNn8eS-hTg3EXgfQaRgG_WZ1n1oGz5rqIHoA6NhVaSuEEH775LfCfD781smlay1B5dVlyb2EKv9Z_EPpRMazyjo-BiybPvOMal9iYudtxATbL7KkDdvseCK1wxT7dXRxv40YW4MD8qz0gLalHXaoWa6m1nQAX?width=1734&height=951&cropmode=none "运行")
2. 输入二叉树A
   ![](https://snz04pap001files.storage.live.com/y4mgvPoLJimxedqI6njzW98XXj7QmNWGI6VxCoM28fme8oVagAAKM-nQKmm_2txcFFs6MwLUI53aOl6GxpFJW6v-4LfvNEo0_6ev8uaEBi35vZFj5kNnnawBe3Yg-PceyKWN1BwI7ef3Cc5bxqi93USouQNlCXP_7OTO4FVHMv0uXGz4dsqV_OEfpTQwuurqAKS?width=1734&height=951&cropmode=none "输入二叉树")
3. 输入二叉树B
   ![](https://snz04pap001files.storage.live.com/y4mxBNFtIfFdiaEsm-LMP8Xz0lFzGo4WsGY0Pv_I3RoMtxpglR2L28vHbkd3vnKElJ1sW6inWo27LdGh7eJKb_1F_MGJz9qiKmFdtdgSPupjq0KRhhZrhyrcEbTbmdyD6pNmX_4J7VsH3petkfuwdI2xMZtlUwd1PI1PF_oiJXkmxNLIkJF-LI59sn2AQ8DmrL0?width=1734&height=951&cropmode=none "输入二叉树")
4. 输出
   ![](https://snz04pap001files.storage.live.com/y4mpTh1dRvbWN4f1dZGvyMPU_YgvPOW0ni6btdWtNItmh5lSqjfOteoKv_rTR2ptKhqfB-dDMmztQVCDqiiT7czQm2vBrxeFNEvtVNS7GLNRq2Pp2LFwQr9znge41BP0DftXlc2PihzRa6uF8eNfhtVamoUrpzMwgefSnodeHAjFBMqKxqMTARVrA-TZ8jEHjWk?width=1734&height=951&cropmode=none "输出")

### 4.2 测试2

输出：

![](https://snz04pap001files.storage.live.com/y4mjg3NZVYKTXm2dgycw7UoMBZESzykn8MtzeVZxkSETx2wgxi22wlxHTbCPhZ-QGBt4rLM8r0JQwvPXPPUbtgOL-PwHitUxnxoKoJq-SvDDz3c7GA3Zychxyk5pX4rMbvwrkXJxxVlJshafAur1BjLNdHy7TVql43xi9HXsYon2xlz2uLYyg3Xa7cEc5FwGm6N?width=1734&height=951&cropmode=none "输出")

## 5.调试记录与收获

代码清单：

1. 头文件`BinaryTree.h`

```c++
   #pragma once
   #include<iostream>
   using namespace std;

template<class T>
   struct BTNode
   {
   	T data;				//数据域
   	BTNode* lchild;			//指向左子树的指针
   	BTNode* rchild;			//指向右指针的指针
   };

template<class T>
   class BinaryTree
   {
   	BTNode<T>* BT;
   public:
   	BinaryTree() { BT = NULL; }			//构造函数
   	void CreateBiTree(T end);			//输入先序序列创建二叉树
   	BTNode<T>* GetRoot();				//获取二叉树的根节点
   	int Like(BTNode<T>* A, BTNode<T>* B);		//判断两棵二叉树是否相似
   };

template<class T>
   void BinaryTree<T>::CreateBiTree(T end)
   {
   	cout << "请按先序序列的顺序输入二叉树，" << end << "为空指针域标志：" << endl;
   	BTNode<T>* p;
   	T x;
   	cin >> x;
   	if (x == end)return;
   	p = new BTNode<T>;
   	if (!p)
   	{
   		cout << "申请内存失败！" << endl;
   		exit(-1);
   	}
   	p->data = x;
   	p->lchild = NULL;
   	p->rchild = NULL;
   	BT = p;
   	create(p, 1, end);
   	create(p, 2, end);
   }

template<class T>
   BTNode<T>* BinaryTree<T>::GetRoot()
   {
   	return BT;
   }

template<class T>
   int BinaryTree<T>::Like(BTNode<T>* A, BTNode<T>* B)
   {
   	if (A == NULL && B == NULL) 
   	{
   		return 1;
   	}
   	else if (A == NULL || B == NULL)
   	{
   		return 0;
   	}
   	Like(A->lchild, B->lchild);
   	Like(A->rchild, B->rchild);
   }

```
2. 主函数`main.cpp`

```c++
   #include<iostream>
   #include"BinaryTree.h"
   using namespace std;

int main()
   {
   	BinaryTree<char>tree1;//创建二叉树tree1
   	BinaryTree<char>tree2;//创建二叉树tree2
   	cout << "输入二叉树A：" << endl;
   	tree1.CreateBiTree('#');//输入二叉树tree1
   	cout << "输入二叉树B：" << endl;
   	tree2.CreateBiTree('#');//输入二叉树tree2
   	if (tree1.Like(tree1.GetRoot(), tree2.GetRoot()))//判断相似性
   	{
   		cout << "A与B相似" << endl;
   	}
   	else
   	{
   		cout << "A与B不相似" << endl;
   	}
   }
   ```

# 试验7.3 二叉树任一结点的特征计算

## 1.问题描述

给定二叉树中一结点，去欸的那个该结点在二叉树中的特征：即该结点的层次，从根到该结点的枝长（路径长度），子孙的个数及祖先的个数，每个结点在前序、中序、后序中访问的序号。

## 2.数据结构设计

### 2.1 存储设计

使用二叉树的二叉链表

* 结点设计
  ```c++
  template<class T>
  class BTNode
  {
  private:
  	BTNode<T>* lchild;					//左孩子
  	BTNode<T>* rchild;					//右孩子
  	T data;							//数据域
  	int n;							//层次
  public:
  	int Getn() const { return n; };				//得到层次数n
  	T Getdata() const {return data;};			//得到二叉树结点的数据值
  	BTNode<T>* Getleft() const { return lchild; };		//得到二叉树结点的左儿子地址
  	BTNode<T>* Getright() const { return rchild; };		//得到二叉树结点的右儿子地址
  	void Setdata(const T& item) { data = item; };		//设置二叉树结点的数据值
  	void SetLeft(BTNode<T>* L) { lchild = L; };		//设置二叉树结点的左儿子地址
  	void SetRight(BTNode<T>* R) { rchild = R; };		//设置二叉树结点的右儿子地址
  	void Setn(int i) { n = i; };				//设置层次数n
  	int PrintPreOrder(BTNode<T>* T, int& k);		//当前的结点在T结点为根的树的前序遍历中的序号
  	int PrintPostOrder(BTNode<T>* T, int& k);		//当前的结点在T结点为根的树的后序遍历中的序号
  	int PrintInOrder(BTNode<T>* T, int& k);			//当前的结点在T结点为根的树的中序遍历中的序号
  };
  ```
* 树设计
  ```c++
  template<class T>
  class BiTree
  {
  	BTNode<T>* root;
  public:
  	BiTree() { root = NULL; };				//构造函数
  	void CreateBinary(T end);				//创建二叉树
  	BTNode<T>* GetRoot();					//获取根结点
  	int Size(BTNode<T>* p);					//计算从以p为根的二叉树的结点数
  	BTNode<T>* SearchNode(BTNode<T>* root, T e);		//寻找到结点值为e的结点，返回指向结点的指针
  };
  ```

## 3.算法设计

### 3.1 结点

* 当前的结点在T结点为根的树的前序遍历中的序号
  ```c++
  //前序遍历序号
  template<class T>
  int BTNode<T>::PrintPreOrder(BTNode<T>* T, int& k)
  {
  	if (!T || k > 0)return 0;
  	else
  	{
  		if (k > 0)return 0;
  		k--;
  		if (T->Getdata() == data)
  			k = -k;
  		PrintPreOrder(T->Getleft(), k);
  		PrintPreOrder(T->Getright(), k);
  	}
  	return 0;
  }
  ```
* 当前的结点在T结点为根的树的后序遍历中的序号
  ```c++
  //后序遍历序号
  template<class T>
  int BTNode<T>::PrintPostOrder(BTNode<T>* T, int& k)
  {
  	if (!T || k > 0)return 0;
  	else
  	{
  		PrintPostOrder(T->Getleft(), k);
  		PrintPostOrder(T->Getright(), k);
  		if (k > 0)return 0;
  		k--;
  		if (T->Getdata() == data)
  			k = -k;
  	}
  	return 0;
  }
  ```
* 当前的结点在T结点为根的树的中序遍历中的序号
  ```c++
  //中序遍历序号
  template<class T>
  inline int BTNode<T>::PrintInOrder(BTNode<T>* T, int& k)
  {
  	if (!T || k > 0)return 0;
  	else
  	{
  		PrintInOrder(T->Getleft(), k);
  		if (k > 0)return 0;
  		k--;
  		if (T->Getdata() == data)
  			k = -k;
  		PrintInOrder(T->Getright(), k);
  	}
  	return 0;
  }

```

### 3.2 树

* 使用先序序列创建二叉树
  ```c++
  //先序序列创建二叉树
  template<class T>
  void BiTree<T>::CreateBinary(T end)
  {
  	cout << "Please input nodes:";
  	BTNode<T>* p;
  	T x;
  	cin >> x;
  	if (x == end)return;
  	p = new BTNode<T>;
  	if (!p)
  	{
  		cout << "申请内存失败！" << endl;
  		exit(-1);
  	}
  	p->Setdata(x);
  	p->SetLeft(NULL);
  	p->SetRight(NULL);
  	p->Setn(1);
  	root = p;
  	create(p, 1, end);
  	create(p, 2, end);
  }

template<class T>
  static int create(BTNode<T>* p, int k, T end)
  {
  	BTNode<T>* q;
  	T x;
  	cin >> x;
  	if (x != end)
  	{
  		q = new BTNode<T>;
  		q->Setdata(x);
  		q->SetLeft(NULL);
  		q->SetRight(NULL);
  		if (k == 1) { p->SetLeft(q);q->Setn(p->Getn()+1); }
  		if (k == 2) { p->SetRight(q);q->Setn(p->Getn()+1); }
  		create(q, 1, end);
  		create(q, 2, end);
  	}
  	return 0;
  }
  ```
* 获取根节点
  ```c++
  //获取根结点
  template<class T>
  BTNode<T>* BiTree<T>::GetRoot()
  {
  	return root;
  }
  ```
* 计算从以p为根的二叉树的结点数
  ```c++
  //获取结点数
  template<class T>
  int BiTree<T>::Size(BTNode<T>* p)
  {
  	if (p == NULL)
  		return 0;
  	return 1 + Size(p->Getleft()) + Size(p->Getright());

}
  ```
* 寻找到结点值为e的结点，返回指向结点的指针
  ```c++
  template<class T>
  BTNode<T>* BiTree<T>::SearchNode(BTNode<T>* root, T e)
  {
  	BTNode<T>* t;
  	if (root)
  	{
  		if (root->Getdata() == e) { return root; }
  		t = SearchNode(root->Getleft(), e);
  		if (t) return t;
  		t = SearchNode(root->Getright(), e);
  		if (t) return t;
  	}
  	return NULL;
  }
  ```

### 3.3 主函数

根据题目，主函数需要做到求路径长，求层次，求子孙，祖先的个数，前序、中序、后序遍历中的序号

* 创建二叉树
  ```c++
  cout << "Please input a tree by inputing its nodes one by one (-1 means NULL)" << endl;
  BiTree<int> t1;
  t1.CreateBinary(-1);	//创建树
  ```
* 按值寻找结点
  ```c++
  int e;
  cout << "Input a data of a node, and its information will be printed.";
  cin >> e;	//输入值
  BTNode<int>* p = new BTNode<int>;
  p=t1.SearchNode(t1.GetRoot(), e);	//查找该结点并赋为p
  ```
* 输出路径长、层次、子孙数量、祖先数量
  ```c++
  cout << "The level of the node is:" << p->Getn() << endl;//层次
  cout << "The length from the root the node is:" << p->Getn()-1 << endl;//路径长
  cout << "The num of its offsprings is:" << t1.Size(p)-1 << endl;//子孙数
  cout << "The num of its ancestors is:" << p->Getn() - 1 << endl;//祖先数
  ```
* 输出前序、中序、后序遍历中的序号
  ```c++
  int num_pre, num_in, num_post;//初始化序号为0
  num_pre = num_in = num_post = 0;
  p->PrintPreOrder(t1.GetRoot(), num_pre);//前序
  p->PrintInOrder(t1.GetRoot(), num_in);//中序
  p->PrintPostOrder(t1.GetRoot(), num_post);//后序
  cout << "The preorder of the node is:" << num_pre << endl;
  cout << "The inorder of the node is:" << num_in << endl;
  cout << "The postorder of the node is:" << num_post << endl;
  ```

## 4.运行测试

⚠书上测试用例有误，无法创建二叉树，故使用此二叉树：5 2 3 -1 -1 4 9 -1 -1 8 -1 -1 -1

### 测试1：

* 运行程序
  ![](https://snz04pap001files.storage.live.com/y4mjEsvNGhmkkw-wusEJC92tOOOoyblUILVHVTispwLIqoUMlac0cMIOcIuGxcDwQfv-B-MEK_IeyjIO5awMCXtSEJdZvmFLNIZZJFcdCpSQ6_ATCDASpfyOQd42ljVNOqlCXgslSYuyDqL3AI3m3bRQ4ev3-ln2aSv-bzij0edlgWSqRqWo_VjmVBplH77af6o?width=1734&height=951&cropmode=none "运行")
* 输入二叉树
  ![](https://snz04pap001files.storage.live.com/y4mXxUZhqH6h3eg-j52jT4oRVI7aq-f1aT-aa5gT-2WNrhJEIKyLfejfQW-NIjNkWryJIfRXk9KtojjX9ZtGsrtfkB643ZrZSTgqAAHV_eE_buNrxMbJTFGwtdlnCSEiXM4VjkYS9pURvZRgkmzGtUFGlChw_x8gWK4DUv9XQViJuVpBqEYAZRS-_vwrnmpn9PU?width=1734&height=951&cropmode=none "输入")
* 输入查找的值4
  ![](https://snz04pap001files.storage.live.com/y4mzvnHGfJ4f1JCkq1ksVFTok8aTD9GaeENGY437uLogMD_mpO01hABvovwtXts5t0oSOaX47dxXOwinqXkrVrpGAuif1NaIsTnMNalgumw2YkDMXSFXNkteb2ZkrbEiHjfdfgsblDG3h7iSuUaobrUWUx7eg_0C-wEhARQBKqMDEaJUF45p5xZzt91cLbMRpe5?width=1734&height=951&cropmode=none "查找")
* 输出
  ![](https://snz04pap001files.storage.live.com/y4mo3lp4UmKVHkeYrpcMjnh-4vhMo-C-i6U9qBuEp0vo3KBCIV8hGijEAGc_bJdqsMnuXvO9yz63LSq-fC-2e6ZqlSDZdijm1VighIf66O3__Un1wVybsh4NatSO06rzz57ymMQwFOqWrVY164_DnPrRNripzWkOYD1ppJwdTXaKmJgPU4DFDliBkM2IQU8X56f?width=1734&height=951&cropmode=none "输出")

### 测试2

* 输入值9
  ![](https://snz04pap001files.storage.live.com/y4m_8NJAkTl60iT32CAbHkkyKNi5ARdPw9DndFlh3DD7gkRynDIrHWP9H4-_CxlIVzoSGn7MDBdxIrkwsY4jZgnI9Yz44ikHtONZPKjqrHbvzX7A11CqDcbXf-0YTWMOA7xZSYk6m705ncTRyXSJCA3JiwyKJxLOoq20SYmYe3SuuB-6_j7RJbbfj1KkzY1Kf3I?width=1734&height=951&cropmode=none "输入9")
* 输出
  ![](https://snz04pap001files.storage.live.com/y4mBeKUOrspQtUoGBWJ5EPrpTm21yTE3cljILSF4eBf2MtTuMc0d_DB29J_ZCvlEKuCd26U1b0J6OqG_EYky_FnwPoeOJp20_tGdsSLQmJosJt1-K66sgupnP7m63ysAqxaLvtnhEcM_fLSluystaFU3bA2VZVwPlWveTRUMfZ4bzUEIxpXAztRV6E_CwoYBT67?width=1734&height=951&cropmode=none "输出")

## 5.调试记录与收获

1. 源程序清单
   * `BTNode.h`结点
     ```c++
     #pragma once
     #include<iostream>
     #include"BiTree.h"
     using namespace std;

template<class T>
     class BTNode
     {
     private:
     	BTNode<T>* lchild;
     	BTNode<T>* rchild;
     	T data;
     	int n;
     public:
     	int Getn() const { return n; };//得到n
     	T Getdata() const {return data;};				//得到二叉树结点的数据值
     	BTNode<T>* Getleft() const { return lchild; };	//得到二叉树结点的左儿子地址
     	BTNode<T>* Getright() const { return rchild; };	//得到二叉树结点的右儿子地址
     	void Setdata(const T& item) { data = item; };	//设置二叉树结点的数据值
     	void SetLeft(BTNode<T>* L) { lchild = L; };		//设置二叉树结点的左儿子地址
     	void SetRight(BTNode<T>* R) { rchild = R; };	//设置二叉树结点的右儿子地址
     	void Setn(int i) { n = i; };//设置n
     	int PrintPreOrder(BTNode<T>* T, int& k);			//得到T指向的结点在当前结点为根的树的前序遍历中的序号
     	int PrintPostOrder(BTNode<T>* T, int& k);			//得到T指向的结点在当前结点为根的树的后序遍历中的序号
     	int PrintInOrder(BTNode<T>* T, int& k);			//得到T指向的结点在当前结点为根的树的中序遍历中的序号
     };

//前序遍历序号
     template<class T>
     int BTNode<T>::PrintPreOrder(BTNode<T>* T, int& k)
     {
     	if (!T || k > 0)return 0;
     	else
     	{
     		if (k > 0)return 0;
     		k--;
     		if (T->Getdata() == data)
     			k = -k;
     		PrintPreOrder(T->Getleft(), k);
     		PrintPreOrder(T->Getright(), k);
     	}
     	return 0;
     }
     //后序遍历序号
     template<class T>
     int BTNode<T>::PrintPostOrder(BTNode<T>* T, int& k)
     {
     	if (!T || k > 0)return 0;
     	else
     	{
     		PrintPostOrder(T->Getleft(), k);
     		PrintPostOrder(T->Getright(), k);
     		if (k > 0)return 0;
     		k--;
     		if (T->Getdata() == data)
     			k = -k;
     	}
     	return 0;
     }
     //中序遍历序号
     template<class T>
     inline int BTNode<T>::PrintInOrder(BTNode<T>* T, int& k)
     {
     	if (!T || k > 0)return 0;
     	else
     	{
     		PrintInOrder(T->Getleft(), k);
     		if (k > 0)return 0;
     		k--;
     		if (T->Getdata() == data)
     			k = -k;
     		PrintInOrder(T->Getright(), k);
     	}
     	return 0;
     }

```
   * `BiTree`树
     ```c++
     #pragma once
     #include<iostream>
     #include"BTNode.h"
     using namespace std;

template<class T>
     class BiTree
     {
     	BTNode<T>* root;
     public:
     	BiTree() { root = NULL; };						//构造函数
     	void CreateBinary(T end);						//创建二叉树
     	BTNode<T>* GetRoot();							//获取根结点
     	int Size(BTNode<T>* p);							//计算从以p为根的二叉树的结点数
     	//void PreTraBiTree();							//先序遍历
     	//void InTraBiTree();							//中序遍历
     	//void PostTraBiTree();							//后序遍历
     	BTNode<T>* SearchNode(BTNode<T>* root, T e);	//寻找到结点值为e的结点，返回指向结点的指针
     };
     //先序序列创建二叉树
     template<class T>
     void BiTree<T>::CreateBinary(T end)
     {
     	cout << "Please input nodes:";
     	BTNode<T>* p;
     	T x;
     	cin >> x;
     	if (x == end)return;
     	p = new BTNode<T>;
     	if (!p)
     	{
     		cout << "申请内存失败！" << endl;
     		exit(-1);
     	}
     	p->Setdata(x);
     	p->SetLeft(NULL);
     	p->SetRight(NULL);
     	p->Setn(1);
     	root = p;
     	create(p, 1, end);
     	create(p, 2, end);
     }
     //获取根结点
     template<class T>
     BTNode<T>* BiTree<T>::GetRoot()
     {
     	return root;
     }

//获取结点数
     template<class T>
     int BiTree<T>::Size(BTNode<T>* p)
     {
     	if (p == NULL)
     		return 0;
     	return 1 + Size(p->Getleft()) + Size(p->Getright());

}

////先序遍历
     //template<class T>
     //void BiTree<T>::PreTraBiTree()
     //{
     //	cout << "先序遍历二叉树";
     //	BTNode<T>* p;
     //	p = root;
     //	PreTraverse(p);
     //	cout << endl;
     //}
     ////中序遍历
     //template<class T>
     //void BiTree<T>::InTraBiTree()
     //{
     //	cout << "中遍历二叉树";
     //	BTNode<T>* p;
     //	p = root;
     //	InTraverse(p);
     //	cout << endl;
     //}
     ////后续遍历
     //template<class T>
     //void BiTree<T>::PostTraBiTree()
     //{
     //	cout << "后序遍历二叉树";
     //	BTNode<T>* p;
     //	p = root;
     //	PostTraverse(p);
     //	cout << endl;
     //}
     //
     //template<class T>
     //static int PreTraverse(BTNode<T>* p)
     //{
     //	if (p != NULL)
     //	{
     //		cout << p->Getdata() << " ";
     //		PreTraverse(p->Getleft());
     //		PreTraverse(p->Getright());
     //	}
     //	return 0;
     //}
     //
     //template<class T>
     //static int InTraverse(BTNode<T>* p)
     //{
     //	if (p != NULL)
     //	{
     //		InTraverse(p->Getleft());
     //		cout << p->Getdata() << " ";
     //		InTraverse(p->Getright());
     //	}
     //	return 0;
     //}
     //
     //template<class T>
     //static int PostTraverse(BTNode<T>* p)
     //{
     //	if (p != NULL)
     //	{
     //		PostTraverse(p->Getleft());
     //		PostTraverse(p->Getright());
     //		cout << p->Getdata() << " ";
     //	}
     //	return 0;
     //}
     //在以root为根结点的二叉树中搜索值为e的结点
     template<class T>
     BTNode<T>* BiTree<T>::SearchNode(BTNode<T>* root, T e)
     {
     	BTNode<T>* t;
     	if (root)
     	{
     		if (root->Getdata() == e) { return root; }
     		t = SearchNode(root->Getleft(), e);
     		if (t) return t;
     		t = SearchNode(root->Getright(), e);
     		if (t) return t;
     	}
     	return NULL;
     }

template<class T>
     static int create(BTNode<T>* p, int k, T end)
     {
     	BTNode<T>* q;
     	T x;
     	cin >> x;
     	if (x != end)
     	{
     		q = new BTNode<T>;
     		q->Setdata(x);
     		q->SetLeft(NULL);
     		q->SetRight(NULL);
     		if (k == 1) { p->SetLeft(q);q->Setn(p->Getn()+1); }
     		if (k == 2) { p->SetRight(q);q->Setn(p->Getn()+1); }
     		create(q, 1, end);
     		create(q, 2, end);
     	}
     	return 0;
     }
     ```
   * `main.cpp`主函数
     ```c++
     #include<iostream>
     #include"BiTree.h"
     #include"BTNode.h"
     using namespace std;

int main()
     {
     	cout << "Please input a tree by inputing its nodes one by one (-1 means NULL)" << endl;
     	BiTree<int> t1;
     	t1.CreateBinary(-1);
     	int e;
     	cout << "Input a data of a node, and its information will be printed.";
     	cin >> e;
     	BTNode<int>* p = new BTNode<int>;
     	p=t1.SearchNode(t1.GetRoot(), e);
     	cout << "The level of the node is:" << p->Getn() << endl;
     	cout << "The length from the root the node is:" << p->Getn()-1 << endl;
     	cout << "The num of its offsprings is:" << t1.Size(p)-1 << endl;
     	cout << "The num of its ancestors is:" << p->Getn() - 1 << endl;
     	int num_pre, num_in, num_post;
     	num_pre = num_in = num_post = 0;
     	p->PrintPreOrder(t1.GetRoot(), num_pre);
     	p->PrintInOrder(t1.GetRoot(), num_in);
     	p->PrintPostOrder(t1.GetRoot(), num_post);
     	cout << "The preorder of the node is:" << num_pre << endl;
     	cout << "The inorder of the node is:" << num_in << endl;
     	cout << "The postorder of the node is:" << num_post << endl;
     } 
     ```

最后修改：2022 年 06 月 03 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数据结构试验教程-二叉树

酱油瓶 • 2021 年 11 月 15 日

本文为本人按照书本要求所写作业，算法并非最优，仅供参考
</div>

书为：《数据结构实践教程》清华大学出版社 主编：徐慧
</div>

# 试验7.1 二叉树叶子结点个数计算

姓名：郁闷的酱油瓶

班级：软嵌

学号：114514

学号：2021.11.1

## 1.问题描述

已知一棵二叉树，求该二叉树中叶子结点的个数

## 2.数据结构设计

### 2.1 存储设计

二叉树采用二叉链表为存储设计

```c++
template<class T>
struct BTNode
{
	T data;			//数据域
	BTNode* lchild;		//指向左子树的指针
	BTNode* rchild;		//指向右指针的指针
};
```

### 2.2 函数设计

需要用到的操作:构造函数，创建二叉树，图形显示，计算叶子节点个数，获取根节点

## 3.算法设计

### 3.1 构造函数，创建二叉树，图形显示，获取根节点均按照书本实践操作

template<class T>
BTNode<T>* BinaryTree<T>::GetRoot()	//获取根节点
{
	return BT;
}

### 3.2 计算叶子结点数量

#### Step 1

函数参数1.二叉树的根节点`BTNode<T>* root`2.计数器`count`

```c++
void BinaryTree<T>::CountLeaf(BTNode<T>* root, int& count) {}
```

#### Step 2

##### Step 2.1

判断树是否为空

```c++
if (root)
```

##### Step 2.2

判断是否为叶子结点，若是则增加计数器

```c++
if (root->lchild == NULL && root->rchild == NULL)
		count++;
```

##### Step 2.3

累计左子树上的叶子和右子树上的叶子

```c++
CountLeaf(root->lchild, count);
CountLeaf(root->rchild, count);
```

### 3.3 主函数

实现二叉树的输入和叶子节点的计算

## 4.测试运行

测试1：

(1)输入二叉树: a b ## c ## ## d ## ##

(2)输出：

测试2：

输入：a ## ## s d ## ## f ## ##

输出：

## 5.调试记录与收获

1. 头文件`BiTree.h`
   ```c++
   #pragma once
   #include<iostream>
   using namespace std;

template<class T>
   struct BTNode
   {
   	T data;				//数据域
   	BTNode* lchild;		//指向左子树的指针
   	BTNode* rchild;		//指向右指针的指针
   };

template<class T>
   BTNode<T>* BinaryTree<T>::GetRoot()
   {
   	return BT;
   }

# 试验7.2 二叉树相似问题

## 1.问题描述

两棵二叉树相似，指要么他们都为空或都只有以个根节点，要么它们的左右子树均相似。本问题是：设计一个算法，判断两棵二叉树是否相似。

## 2.数据结构设计

### 2.1 存储设计

使用二叉树的二叉链表存储

```c++
template<class T>
struct BTNode
{
	T data;				//数据域
	BTNode* lchild;			//指向左子树的指针
	BTNode* rchild;			//指向右指针的指针
};
```

### 2.2 函数设计

需要用到的操作:构造函数，创建二叉树，获取根节点，判断两棵二叉树是否相似

## 3.算法设计

### 3.1 构造函数，创建二叉树，获取根节点

template<class T>
static int create(BTNode<T>* p, int k, T end)
{
	BTNode<T>* q;
	T x;
	cin >> x;
	if (x != end)
	{
		q = new BTNode<T>;
		q->data = x;
		q->lchild = NULL;
		q->rchild = NULL;
		if (k == 1)p->lchild = q;
		if (k == 2)p->rchild = q;
		create(q, 1, end);
		create(q, 2, end);
	}
	return 0;
}
//获取二叉树的根节点
template<class T>
BTNode<T>* BinaryTree<T>::GetRoot()
{
	return BT;
}
```

### 3.2 判断两棵二叉树是否有相似性

#### Step 1

设计判断相似方法`Like(BTNode<T>* A, BTNode<T>* B)`，该算法功能是若A与B相似，函数返回1，否则返回0。

```c++
int Like(BTNode<T>* A, BTNode<T>* B) {}		//Like(二叉树A的根节点，二叉树B的根节点)
```

#### Step 2

##### Step 2.1

若A=B=NULL，则A与B相似，即Like(A,B)=1

```c++
if (A == NULL && B == NULL) 
{
	return 1;
}
```

##### Step 2.2

若A与B中有一个为NULL，另一个不为NULL，则A与B不相似，即Like(A,B)=0

```c++
else if (A == NULL || B == NULL)
{
	return 0;
}
```

##### Step 2.3

采用递归方法，进一步判断A的左子树和B的左子树，A的右子树和B的右子树是否相似

```c++
Like(A->lchild, B->lchild);
Like(A->rchild, B->rchild);
```

### 3.3 主函数

实现二叉树的输入和相似比较

## 4.运行测试

### 4.1 测试1

### 4.2 测试2

输出：

## 5.调试记录与收获

代码清单：

1. 头文件`BinaryTree.h`

```c++
   #pragma once
   #include<iostream>
   using namespace std;

template<class T>
   struct BTNode
   {
   	T data;				//数据域
   	BTNode* lchild;			//指向左子树的指针
   	BTNode* rchild;			//指向右指针的指针
   };

template<class T>
   void BinaryTree<T>::CreateBiTree(T end)
   {
   	cout << "请按先序序列的顺序输入二叉树，" << end << "为空指针域标志：" << endl;
   	BTNode<T>* p;
   	T x;
   	cin >> x;
   	if (x == end)return;
   	p = new BTNode<T>;
   	if (!p)
   	{
   		cout << "申请内存失败！" << endl;
   		exit(-1);
   	}
   	p->data = x;
   	p->lchild = NULL;
   	p->rchild = NULL;
   	BT = p;
   	create(p, 1, end);
   	create(p, 2, end);
   }

template<class T>
   BTNode<T>* BinaryTree<T>::GetRoot()
   {
   	return BT;
   }

```
2. 主函数`main.cpp`

```c++
   #include<iostream>
   #include"BinaryTree.h"
   using namespace std;

# 试验7.3 二叉树任一结点的特征计算

## 1.问题描述

## 2.数据结构设计

### 2.1 存储设计

使用二叉树的二叉链表

## 3.算法设计

### 3.1 结点

```

### 3.2 树

### 3.3 主函数

根据题目，主函数需要做到求路径长，求层次，求子孙，祖先的个数，前序、中序、后序遍历中的序号

## 4.运行测试

⚠书上测试用例有误，无法创建二叉树，故使用此二叉树：5 2 3 -1 -1 4 9 -1 -1 8 -1 -1 -1

### 测试1：

### 测试2

## 5.调试记录与收获

1. 源程序清单
   * `BTNode.h`结点
     ```c++
     #pragma once
     #include<iostream>
     #include"BiTree.h"
     using namespace std;

```
   * `BiTree`树
     ```c++
     #pragma once
     #include<iostream>
     #include"BTNode.h"
     using namespace std;

//获取结点数
     template<class T>
     int BiTree<T>::Size(BTNode<T>* p)
     {
     	if (p == NULL)
     		return 0;
     	return 1 + Size(p->Getleft()) + Size(p->Getright());

}

template<class T>
     static int create(BTNode<T>* p, int k, T end)
     {
     	BTNode<T>* q;
     	T x;
     	cin >> x;
     	if (x != end)
     	{
     		q = new BTNode<T>;
     		q->Setdata(x);
     		q->SetLeft(NULL);
     		q->SetRight(NULL);
     		if (k == 1) { p->SetLeft(q);q->Setn(p->Getn()+1); }
     		if (k == 2) { p->SetRight(q);q->Setn(p->Getn()+1); }
     		create(q, 1, end);
     		create(q, 2, end);
     	}
     	return 0;
     }
     ```
   * `main.cpp`主函数
     ```c++
     #include<iostream>
     #include"BiTree.h"
     #include"BTNode.h"
     using namespace std;

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构试验教程-二叉树

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款