數(shù)據(jù)結(jié)構(gòu)上機實驗

1.要求

?? 建立一棵二叉樹，試編程實現(xiàn)二叉樹的如下基本操作。
?? 1.創(chuàng)建一棵一棵二叉算法。
?? 2.對這棵二叉樹進(jìn)行遍歷：先序或中序或后序，分別輸出結(jié)點的遍歷序列。
?? 3.求二叉樹的深度/節(jié)點數(shù)目/葉節(jié)點數(shù)目。（選做一個）
?? 4.計算二叉樹中度為1 的結(jié)點數(shù)；
?? 5.計算二叉樹中度為2 的結(jié)點數(shù)。
?? 6.判斷2棵二叉樹是否相似，若相似返回1，否則返回0

????????????

2.二叉樹的實現(xiàn)

??二叉樹的介紹

??

2.1創(chuàng)建一顆二叉樹

??我們現(xiàn)在可以簡單實現(xiàn)一個二叉樹的結(jié)構(gòu)，其中包括一個二叉樹節(jié)點（BNode）和一個二叉樹（BTree）類。

??我們定義了一個名為BNode的結(jié)構(gòu)體，它代表二叉樹的節(jié)點。每個節(jié)點包含一個數(shù)據(jù)元素（data，其類型為int）和兩個指向其左右子節(jié)點的指針（left和right）。

??然后定義了一個名為BTree的類，它包含一個私有成員變量_root，這是一個指向BNode的指針。這個指針表示了樹的根節(jié)點。這個類還包含一個默認(rèn)的構(gòu)造函數(shù)，該構(gòu)造函數(shù)將_root初始化為nullptr，即沒有初始的根節(jié)點。

#define BTDataType int

//定義二叉樹節(jié)點
typedef struct BTreeNode
{
	BTDataType data;
	struct BTreeNode* left;
	struct BTreeNode* right;
}BNode;

//定義二叉樹
class BTree
{
public:
	//構(gòu)造函數(shù)
	BTree()
	{
		_root = nullptr;
	}
	
private:
	BNode* _root;
};

??
輸入字符遞歸創(chuàng)建二叉樹：
??我們先使用引用接受一個 BNode*類型的參數(shù) root。這樣我們就可以在函數(shù)內(nèi)部，直接對 root 進(jìn)行操作，最后返回給tmp，再賦給_root。

??這個函數(shù)首先從標(biāo)準(zhǔn)輸入讀取一個字符 val。如果 val 是 . ，則 root 被設(shè)置為 nullptr，表示該節(jié)點為空。如果 val 不是 .，則創(chuàng)建一個新的 BNode 對象，其 data 成員的值為 val 減去字符 ‘0’ 的 ASCII 值（這樣可以獲得一個整數(shù)），然后遞歸地創(chuàng)建這個新節(jié)點的左子樹和右子樹。最后，_BTCreate 返回，控制權(quán)回到調(diào)用該函數(shù)的代碼。

//遞歸創(chuàng)建二叉樹
void _BTCreate(BNode*& root)
{
	char val;
	cin >> val;
	if (val == '.') root = nullptr;
	else
	{
		root = new BNode(val - '0');
		_BTCreate(root->left);
		_BTCreate(root->right);
	}
}

//遞歸創(chuàng)建二叉樹
void BTCreate()
{
	BNode* tmp;
	_BTCreate(tmp);
	_root = tmp;
}

??

2.2對這棵二叉樹進(jìn)行遍歷

前序遍歷：

??我們創(chuàng)建_PreOrder(BNode* root)這個函數(shù)是用來前序遍歷。它的順序是：先訪問根節(jié)點，然后訪問左子樹，最后訪問右子樹。

??如果 root 是 nullptr（即當(dāng)前節(jié)點為空），它將輸出 “NULL” 并返回。如果 root 非空，它會輸出當(dāng)前節(jié)點的數(shù)據(jù)（root->data），然后遞歸地對左子樹和右子樹進(jìn)行前序遍歷。

??由于二叉樹的前序遍歷是一個遞歸算法，為了可以將根節(jié)點不斷的更新，并且遞歸。 我們需要封裝一下，對于后面需要遞歸的函數(shù)，我們都需要將根節(jié)點作為參數(shù)，進(jìn)行遞歸操作。

//前序遍歷
void _PreOrder(BNode* root)
{
	if (root == nullptr)
	{
		cout << "NULL" << " ";
		return;
	}

	cout << root->data << " ";
	_PreOrder(root->left);
	_PreOrder(root->right);
}

//前序遍歷
void PreOrder()
{
	_PreOrder(_root);
	cout << endl;
}

??
中序遍歷：

??我們創(chuàng)建 _InOrder(BNode* root) 來進(jìn)行中序遍歷，它的順序是：先訪問左子樹，然后訪問根節(jié)點，最后訪問右子樹。

??如果 root 是 nullptr，表示當(dāng)前節(jié)點為空，輸出 “NULL” 并返回。如果 root 非空，先遞歸地遍歷左子樹，然后輸出當(dāng)前節(jié)點的數(shù)據(jù) root->data，最后遞歸地遍歷右子樹。

//中序遍歷
void _InOrder(BNode* root)
{
	if (root == nullptr)
	{
		cout << "NULL" << " ";
		return;
	}

	_InOrder(root->left);
	cout << root->data << " ";
	_InOrder(root->right);
}

//中序遍歷
void InOrder()
{
	_InOrder(_root);
	cout << endl;
}

??
后序遍歷：

??我們創(chuàng)建 _PostOrder(BNode* root) 函數(shù)來進(jìn)行進(jìn)行后序遍歷，它的順序是：先訪問左子樹，然后訪問右子樹，最后訪問根節(jié)點。

??如果 root 是 nullptr，表示當(dāng)前節(jié)點為空，輸出 “NULL” 并返回。如果 root 非空，先遞歸地遍歷左子樹，然后遞歸地遍歷右子樹，最后輸出當(dāng)前節(jié)點的數(shù)據(jù) root->data。

//后序遍歷
void _PostOrder(BNode* root)
{
	if (root == nullptr)
	{
		cout << "NULL" << " ";
		return;
	}

	_PostOrder(root->left);
	_PostOrder(root->right);
	cout << root->data << " ";
}

//后序遍歷
void PostOrder()
{
	_PostOrder(_root);
	cout<<endl;
}

??

2.3求二叉樹的深度/節(jié)點數(shù)目/葉節(jié)點數(shù)目

計算二叉樹深度：

??我們使用遞歸的方式來實現(xiàn)計算二叉樹的深度。二叉樹的深度可以定義為左子樹和右子樹深度的最大值加1。

??函數(shù)接受的參數(shù)root 是 NULL，即當(dāng)前節(jié)點為空，那么返回深度為0。否則，遞歸地計算左子樹和右子樹的深度，并返回其中較大的一個，并加上1（當(dāng)前節(jié)點的深度）。

//計算二叉樹深度
int _BTDepth(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		int left_Height = _BTDepth(root->left) + 1;
		int right_Height = _BTDepth(root->right) + 1;
		if (left_Height >= right_Height) return left_Height;
		else return right_Height;
	}
}

//計算二叉樹深度
int	BTDepth()
{
	return _BTDepth(_root);
}

??
計算二叉樹節(jié)點數(shù)目：

??我們遞歸實現(xiàn)_Num_Of_TreeNode來計算二叉樹的節(jié)點數(shù)目。

??首先我們接收一個指向二叉樹節(jié)點的指針 root 作為參數(shù)。如果 root 是 NULL（也就是說，當(dāng)前節(jié)點不存在），函數(shù)返回0。否則，則說明該二叉樹的節(jié)點存在，函數(shù)返回1（對于當(dāng)前節(jié)點） 加上左子樹和右子樹的節(jié)點數(shù)目。這是通過遞歸調(diào)用 _Num_Of_TreeNode 函數(shù)得到的。

//計算二叉樹節(jié)點數(shù)目
int _Num_Of_TreeNode(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		return 1 + _Num_Of_TreeNode(root->left) + 
		_Num_Of_TreeNode(root->right);
	}
}

//計算二叉樹節(jié)點數(shù)目
int Num_Of_TreeNode()
{
	return _Num_Of_TreeNode(_root);
}

??
計算二叉樹葉子節(jié)點的數(shù)目:

??我們同樣創(chuàng)建遞歸函數(shù) _Num_Of_LeafNode來計算二叉樹的葉子節(jié)點。

??我們接收一個指向二叉樹節(jié)點的指針 root 作為參數(shù)。如果 root 是 NULL（也就是說，當(dāng)前節(jié)點不存在），函數(shù)返回0。否則，函數(shù)首先遞歸地計算左子樹和右子樹的葉子節(jié)點數(shù)量，分別存儲在 left_Num 和 right_Num 中。

??注意：如果 left_Num 和 right_Num 的和為0，這意味著當(dāng)前節(jié)點是葉子節(jié)點，因此返回1。 如果 left_Num 和 right_Num 的和不為0，這意味著當(dāng)前節(jié)點不是葉子節(jié)點，因此返回 left_Num 和 right_Num 的和。

//計算二叉樹葉子節(jié)點的數(shù)目
int _Num_Of_LeafNode(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		int left_Num = _Num_Of_LeafNode(root->left);
		int right_Num = _Num_Of_LeafNode(root->right);
		if (left_Num + right_Num == 0)
		{
			return 1;
		}
		else
		{
			return left_Num + right_Num;
		}
	}
}

//計算二叉樹葉子節(jié)點的數(shù)目
int Num_Of_LeafNode()
{
	return _Num_Of_LeafNode(_root);
}

??

2.4計算二叉樹中度為 1 或 2 的結(jié)點數(shù)

??
計算度為1的節(jié)點個數(shù)：

??二叉樹的遞歸函數(shù)大差不差，我們對于求不同的節(jié)點，只要加以它們的性質(zhì)判斷即可。

??如果二叉樹的節(jié)點度為2，說明它們均有左右節(jié)點。 所以，此時函數(shù)返回的是左子樹和右子樹中1度節(jié)點的總和。

??只有右節(jié)點: 如果一個節(jié)點只有右子節(jié)點，那么它是1度節(jié)點。 因此，這個分支計算了右子樹中的1度節(jié)點數(shù)量，并加上1（表示當(dāng)前節(jié)點）。

??只有左節(jié)點: 與上述邏輯類似，如果一個節(jié)點只有左子節(jié)點， 那么它也是1度節(jié)點。這個分支計算了左子樹中的1度節(jié)點數(shù)量，并加上1（表示當(dāng)前節(jié)點）。

??無左右節(jié)點: 如果一個節(jié)點既沒有左子節(jié)點也沒有右子節(jié)點，那么它不是1度節(jié)點。函數(shù)返回0。

//計算度為1的節(jié)點個數(shù)
int _Num_Of_Degree_1(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right != NULL 
	|| root->left != NULL && root->right == NULL)
	{
		return 1 + _Num_Of_Degree_1(root->left) + 
		_Num_Of_Degree_1(root->right);
	}
	return  _Num_Of_Degree_1(root->left) + 
	_Num_Of_Degree_1(root->right);
}

//計算二叉樹節(jié)點數(shù)目
int Num_Of_TreeNode()
{
	return _Num_Of_TreeNode(_root);
}

??
計算度為2的節(jié)點個數(shù)：

??和上面一樣，我們實現(xiàn)計算一個二叉樹中度為2的節(jié)點的數(shù)量。度為2的節(jié)點是指有兩個子節(jié)點的節(jié)點。

??如果 root 的左右子節(jié)點都不為空(root->left != NULL and root->right != NULL)，則說明當(dāng)前節(jié)點的度為2，返回1（對于當(dāng)前節(jié)點）加上左子樹和右子樹的度為1的節(jié)點數(shù)量之和。

??只有右子節(jié)點不為空，則只返回右子樹的度為1的節(jié)點數(shù)量。

??只有左子節(jié)點不為空，則只返回左子樹的度為1的節(jié)點數(shù)量。

??左右子節(jié)點都為空，則當(dāng)前節(jié)點不是度為2的節(jié)點，返回0。

//計算度為2的節(jié)點個數(shù)
int _Num_Of_Degree_2(BNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if(root->left != NULL && root->right != NULL)//均有左右節(jié)點
	{
		return 1 + _Num_Of_Degree_2(root->left) 
		+ _Num_Of_Degree_2(root->right);
	}
	return _Num_Of_Degree_2(root->right)+ _Num_Of_Degree_2(root->left);
}

//計算度為2的節(jié)點個數(shù)
int Num_Of_Degree_2()
{
	return _Num_Of_Degree_2(_root);
}

??

2.5判斷2棵二叉樹是否相似，若相似返回1，否則返回0

??這個函數(shù)是用來判斷兩棵二叉樹是否相似的。相似二叉樹的定義是：如果兩棵二叉樹的結(jié)構(gòu)相同，即它們的左子樹和右子樹都是相似的，那么這兩棵二叉樹就是相似的。

??這個函數(shù)使用遞歸的方式進(jìn)行檢查。首先，如果兩個節(jié)點都為空，那么它們顯然是相似的。然后，如果兩個節(jié)點都不為空，并且它們的左子樹和右子樹都是相似的，那么這兩個節(jié)點也是相似的。 最后，如果以上條件都不滿足，那么這兩個節(jié)點就不相似。

//判斷二叉樹是否相似
int Is_Similar(BNode* t1, BNode* t2)
{
	if (t1 == NULL && t2 == NULL)
	{
		return 1;
	}
	else if (t1 && t2 && Is_Similar(t1->left, t2->left)
	 && Is_Similar(t1->right, t2->right))
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

????????????

3.全部源碼

測試：

??

BinaryTree.h

#pragma once

#define BTDataType int

//定義二叉樹節(jié)點
typedef struct BTreeNode
{
	BTDataType data;
	struct BTreeNode* left;
	struct BTreeNode* right;

	BTreeNode() 
	{
		data = -1;
		left = nullptr;
		right = nullptr;
	}

	BTreeNode(const int& _data)
	{
		data = _data;
		left = nullptr;
		right = nullptr;
	}
}BNode;

//定義二叉樹
class BTree
{
public:
	//構(gòu)造函數(shù)
	BTree()
	{
		_root = nullptr;

	}

	//析構(gòu)函數(shù)
	~BTree()
	{
		DestroyTree(_root);
	}

	//遞歸創(chuàng)建二叉樹
	void BTCreate()
	{
		BNode* tmp;
		_BTCreate(tmp);
		_root = tmp;
	}

	//前序遍歷
	void PreOrder()
	{
		_PreOrder(_root);
		cout << endl;
	}

	//中序遍歷
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	//后序遍歷
	void PostOrder()
	{
		_PostOrder(_root);
		cout<<endl;
	}

	//計算二叉樹深度
	int	BTDepth()
	{
		return _BTDepth(_root);
	}

	//計算二叉樹節(jié)點數(shù)目
	int Num_Of_TreeNode()
	{
		return _Num_Of_TreeNode(_root);
	}

	//計算二叉樹葉子節(jié)點的數(shù)目
	int Num_Of_LeafNode()
	{
		return _Num_Of_LeafNode(_root);
	}

	//計算度為1的節(jié)點個數(shù)
	int Num_Of_Degree_1()
	{
		return _Num_Of_Degree_1(_root);
	}

	//計算度為2的節(jié)點個數(shù)
	int Num_Of_Degree_2()
	{
		return _Num_Of_Degree_2(_root);
	}

	//判斷二叉樹是否相似
	int Is_Similar(BNode* t1, BNode* t2)
	{
		if (t1 == NULL && t2 == NULL)
		{
			return 1;
		}
		else if (t1 && t2 && Is_Similar(t1->left, t2->left) && Is_Similar(t1->right, t2->right))
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}

	//判斷二叉樹是否相等
	int Is_Same(BNode* t1, BNode* t2)
	{
		if (t1 == NULL && t2 == NULL)
		{
			return 1;
		}
		else if (t1 && t2 && (t1->data == t2->data) 
			&& Is_Same(t1->left, t2->left) && Is_Same(t1->right, t2->right))
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}

	//取根節(jié)點
	BNode*& GetRoot()
	{
		return _root;
	}

private:
	//遞歸創(chuàng)建二叉樹
	void _BTCreate(BNode*& root)
	{
		char val;
		cin >> val;
		if (val == '.') root = nullptr;
		else
		{
			root = new BNode(val - '0');
			_BTCreate(root->left);
			_BTCreate(root->right);
		}
	}

	//前序遍歷
	void _PreOrder(BNode* root)
	{
		if (root == nullptr)
		{
			cout << "NULL" << " ";
			return;
		}
	
		cout << root->data << " ";
		_PreOrder(root->left);
		_PreOrder(root->right);
	}

	//中序遍歷
	void _InOrder(BNode* root)
	{
		if (root == nullptr)
		{
			cout << "NULL" << " ";
			return;
		}

		_InOrder(root->left);
		cout << root->data << " ";
		_InOrder(root->right);
	}

	//后序遍歷
	void _PostOrder(BNode* root)
	{
		if (root == nullptr)
		{
			cout << "NULL" << " ";
			return;
		}

		_PostOrder(root->left);
		_PostOrder(root->right);
		cout << root->data << " ";
	}

	//計算二叉樹深度
	int _BTDepth(BNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		else
		{
			int left_Height = _BTDepth(root->left) + 1;
			int right_Height = _BTDepth(root->right) + 1;
			if (left_Height >= right_Height) return left_Height;
			else return right_Height;
		}
	}

	//計算二叉樹節(jié)點數(shù)目
	int _Num_Of_TreeNode(BNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		else
		{
			return 1 + _Num_Of_TreeNode(root->left) + _Num_Of_TreeNode(root->right);
		}
	}

	//計算二叉樹葉子節(jié)點的數(shù)目
	int _Num_Of_LeafNode(BNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		else
		{
			int left_Num = _Num_Of_LeafNode(root->left);
			int right_Num = _Num_Of_LeafNode(root->right);
			if (left_Num + right_Num == 0)
			{
				return 1;
			}
			else
			{
				return left_Num + right_Num;
			}
		}
	}

	//計算度為1的節(jié)點個數(shù)
	int _Num_Of_Degree_1(BNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		else if (root->left == NULL && root->right != NULL || root->left != NULL && root->right == NULL)
		{
			return 1 + _Num_Of_Degree_1(root->left) + _Num_Of_Degree_1(root->right);
		}
		return  _Num_Of_Degree_1(root->left) + _Num_Of_Degree_1(root->right);
	}

	//計算度為2的節(jié)點個數(shù)
	int _Num_Of_Degree_2(BNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		else if(root->left != NULL && root->right != NULL)//均有左右節(jié)點
		{
			return 1 + _Num_Of_Degree_2(root->left) + _Num_Of_Degree_2(root->right);
		}
		return  _Num_Of_Degree_2(root->left) + _Num_Of_Degree_2(root->right);
	}

	//銷毀二叉樹
	void DestroyTree(BNode*& root) 
	{
		if (root == NULL) 
		{
			return;
		}

		BNode* lroot = root->left;
		BNode* rroot = root->right;
		delete root;
		if (lroot != NULL)
		{
			DestroyTree(lroot);
		}
		if (rroot != NULL)
		{
			DestroyTree(rroot);
		}
	}

private:
	BNode* _root;
};

????????????文章來源地址http://www.zghlxwxcb.cn/news/detail-736452.html

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

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

void binary_Test()
{
	BTree bt1;
	BTree bt2;
	cout << "輸入第一棵樹的前序遍歷（空樹請用 . 代替）:";
	bt1.BTCreate();
	cout << "輸入第二棵樹的前序遍歷（空樹請用 . 代替）:";
	bt2.BTCreate(); 
	cout << "第一棵樹的前序遍歷為:";
	bt1.PreOrder();
	cout << "第一棵樹的中序遍歷為:"; 
	bt1.InOrder();	
	cout << "第一棵樹的后序遍歷為:"; 
	bt1.PostOrder();
	cout << "第一棵樹的深度為:" << bt1.BTDepth() << endl;
	cout << "第一棵樹中的節(jié)點數(shù):" << bt1.Num_Of_TreeNode() << endl;
	cout << "第一棵樹中的葉子節(jié)點數(shù):" << bt1.Num_Of_LeafNode() << endl;
	cout << "第一棵樹中度為1的節(jié)點數(shù):" << bt1.Num_Of_Degree_1() << endl;
	cout << "第一棵樹中度為2的節(jié)點數(shù):" << bt1.Num_Of_Degree_2() << endl;
	cout << endl;
	cout << "第二棵樹的前序遍歷為:";
	bt2.PreOrder();
	cout << "第二棵樹的中序遍歷為:";
	bt2.InOrder();
	cout << "第二棵樹的后序遍歷為:";
	bt2.PostOrder();
	cout << "第二棵樹的深度為:" << bt2.BTDepth() << endl;
	cout << "第二棵樹中的節(jié)點數(shù):" << bt2.Num_Of_TreeNode() << endl;
	cout << "第二棵樹中的葉子節(jié)點數(shù):" << bt2.Num_Of_LeafNode() << endl;
	cout << "第二棵樹中度為1的節(jié)點數(shù):" << bt2.Num_Of_Degree_1() << endl;
	cout << "第二棵樹中度為2的節(jié)點數(shù):" << bt2.Num_Of_Degree_2() << endl;
	cout << "兩棵樹是否相似:" << bt1.Is_Similar(bt1.GetRoot(), bt2.GetRoot());
	cout << "兩顆樹是否相等:" << bt1.Is_Same(bt1.GetRoot(), bt2.GetRoot());
}

int main()
{
	binary_Test();
	return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)上機實驗——二叉樹的實現(xiàn)、二叉樹遍歷、求二叉樹的深度/節(jié)點數(shù)目/葉節(jié)點數(shù)目、計算二叉樹度為1或2的節(jié)點數(shù)、判斷二叉樹是否相似的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！