• 数据结构C++——二叉树的实现

    目录

    二叉树的实现（出错版）

    但是VS出现错误

    全部代码：

    运行结果：

    补充计算叶子结点的个数方法后： 

    结果： 

     补充计算二叉树深度方法：

    运行结果：

    补充计算二叉树结点个数方法：（R+L+D=结点个数）

    运行结果：

    二叉树相关方法大实现： 

    运行结果：

    二叉树的实现（出错版）

    1.  
    2. /*
    3. *    二叉树的使用
    4. */
    5.  
    6. /*
    7. *    二叉树的结点结构
    8. */
    9. struct BiNode {
    10. 	char data;
    11. 	BiNode* lchid,*rchid;
    12. };
    13.  
    14. /*
    15. *  二叉链表的实现
    16. */
    17.  
    18. class BiTree {
    19. private:
    20. 	BiNode* Creat();
    21. 	void Release(BiNode* bt);
    22. 	void PreOrder(BiNode* bt);
    23. 	void InOrder(BiNode* bt);
    24. 	void PostOrder(BiNode* bt);
    25. 	BiNode* root;//指向根结点的头指针
    26. public:
    27. 	BiTree(){}
    28. 	BiTree() {
    29. 		root = Creat();
    30. 	}
    31. 	~BiTree() {
    32. 		Release(root);
    33. 	}
    34.  
    35. 	//前序遍历二叉树
    36. 	void PreOrder() {
    37. 		PreOrder(root);
    38. 	}
    39.  
    40. 	//中序遍历二叉树
    41. 	void InOrder() {
    42. 		InOrder(root);
    43. 	}
    44.  
    45. 	//后序遍历二叉树
    46. 	void PostOrder() {
    47. 		PostOrder(root);
    48. 	}
    49. 	//层序二叉树
    50. 	void LevelOrder();
    51. };
    52.  
    53. //层序遍历二叉树
    54. void BiTree::LevelOrder() {
    55. 	BiNode* Q[100], * q = nullptr;
    56. 	int font = -1, rear = -1;//队列初始化
    57. 	if (root == nullptr)
    58. 		return;
    59. 	Q[++rear] = root;//根指针入队
    60. 	while (font!=rear)
    61. 	{
    62. 		q = Q[++font];//出队
    63. 		cout << q->data<<"\t";
    64. 		if (q->lchid != nullptr)
    65. 			Q[++rear] = q->lchid;
    66. 		if (q->rchid != nullptr)
    67. 			Q[++rear] = q->rchid;
    68. 	}
    69. }
    70.  
    71. //前序遍历
    72. void BiTree::PreOrder(BiNode* bt) {
    73. 	if (bt == nullptr)
    74. 		return;
    75. 	else {
    76. 		cout << bt->data;
    77. 		cout << endl;          //访问根结点bt的数据域
    78. 		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    79. 		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    80. 	}
    81. }
    82.  
    83. //中序遍历
    84. void BiTree::InOrder(BiNode*bt) {
    85. 	if (bt == nullptr)
    86. 		return;
    87. 	else
    88. 	{
    89. 		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    90. 		cout << bt->data;    //访问根结点bt的数据域
    91. 		InOrder(bt->rchid); //中序递归遍历bt的右子树
    92. 	}
    93. }
    94.  
    95. //后序遍历
    96. void BiTree::PostOrder(BiNode* bt) {
    97. 	if (bt == nullptr)
    98. 		return;
    99. 	else{
    100. 		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    101. 		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    102. 		cout << bt->data;     //访问根结点bt的数据域
    103. 	}
    104. }
    105.  
    106. //建立二叉树
    107. BiNode* BiTree::Creat() {
    108. 	BiNode* bt;
    109. 	char ch;
    110. 	cin >> ch;        //输入结点的数据信息，假设为字符
    111. 	if (ch == '#')   //建立一个空树
    112. 		bt = nullptr;
    113. 	else{
    114. 		bt = new BiNode;
    115. 		bt->data = ch;
    116. 		bt->lchid = Creat();//递归建立左子树
    117. 		bt->rchid = Creat();//递归建立右子树
    118. 	}
    119. 	return bt;
    120. }
    121. #include
    122. using namespace std;
    123. int mian() {
    124. 	BiTree T{};//定义对象变量 T
    125. 	cout << "该二叉树的前序遍历序列为：";
    126. 	T.PreOrder();
    127. 	cout << endl;
    128.  
    129. 	cout << "该二叉树的中序遍历序列为：";
    130. 	T.InOrder();
    131. 	cout << endl;
    132.  
    133. 	cout << "该二叉树的后序遍历序列为：";
    134. 	T.PostOrder();
    135. 	cout << endl;
    136.  
    137. 	cout << "该二叉树的层序遍历序列为：";
    138. 	T.LevelOrder();
    139. 	cout << endl;
    140.  
    141. 	system("pause");
    142. 	return 0;
    143. }

    但是VS出现错误

    全部代码：

    更改后： 

    1.  
    2. /*
    3. *    二叉树的使用
    4. */
    5.  
    6. #include
    7. #include
    8. using namespace std;
    9.  
    10. /*
    11. *    二叉树的结点结构
    12. */
    13. struct BiNode {
    14. 	char data;
    15. 	BiNode* lchid,*rchid;
    16. };
    17.  
    18. /*
    19. *  二叉链表的实现
    20. */
    21. class BiTree {
    22. private:
    23. 	BiNode* Creat();
    24. 	void Release(BiNode* bt);
    25. 	void PreOrder(BiNode* bt);
    26. 	void InOrder(BiNode* bt);
    27. 	void PostOrder(BiNode* bt);
    28. 	BiNode* root;//指向根结点的头指针
    29. public:
    30. 	BiTree() {
    31. 		root = Creat();
    32. 	}
    33. 	~BiTree() {
    34. 		Release(root);
    35. 	}
    36.  
    37. 	//前序遍历二叉树
    38. 	void PreOrder() {
    39. 		PreOrder(root);
    40. 	}
    41.  
    42. 	//中序遍历二叉树
    43. 	void InOrder() {
    44. 		InOrder(root);
    45. 	}
    46.  
    47. 	//后序遍历二叉树
    48. 	void PostOrder() {
    49. 		PostOrder(root);
    50. 	}
    51. 	//层序二叉树
    52. 	void LevelOrder();
    53. };
    54.  
    55. //建立二叉树
    56. BiNode* BiTree::Creat()
    57. {
    58. 	BiNode* bt;
    59. 	cout << "请依次输入二叉树序列：" << endl;
    60. 	char ch;
    61. 	cin >> ch;        //输入结点的数据信息，假设为字符
    62. 	if (ch == '#')   //建立一个空树
    63. 		bt = nullptr;
    64. 	else {
    65. 		bt = new BiNode;
    66. 		bt->data = ch;
    67. 		bt->lchid = Creat();//递归建立左子树
    68. 		bt->rchid = Creat();//递归建立右子树
    69. 	}
    70. 	return bt;
    71. }
    72.  
    73. //销毁二叉树
    74. void BiTree::Release(BiNode* bt) {
    75. 	if (bt == nullptr)
    76. 		return;
    77. 	else {
    78. 		Release(bt->lchid);  //释放左子树
    79. 		Release(bt->rchid); //释放右子树
    80. 		delete bt;         //释放根结点
    81. 	}
    82. }
    83. //层序遍历二叉树
    84. void BiTree::LevelOrder() {
    85. 	BiNode* Q[100], * q = nullptr;
    86. 	int font = -1, rear = -1;//队列初始化
    87. 	if (root == nullptr)
    88. 		return;
    89. 	Q[++rear] = root;//根指针入队
    90. 	while (font!=rear)
    91. 	{
    92. 		q = Q[++font];//出队
    93. 		cout << q->data<<"\t";
    94. 		if (q->lchid != nullptr)
    95. 			Q[++rear] = q->lchid;
    96. 		if (q->rchid != nullptr)
    97. 			Q[++rear] = q->rchid;
    98. 	}
    99. }
    100.  
    101. //前序遍历
    102. void BiTree::PreOrder(BiNode* bt) {
    103. 	if (bt == nullptr)
    104. 		return;
    105. 	else {
    106. 		std::cout << bt->data; //访问根结点bt的数据域
    107. 		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    108. 		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    109. 	}
    110. }
    111.  
    112. //中序遍历
    113. void BiTree::InOrder(BiNode*bt) {
    114. 	if (bt == nullptr)
    115. 		return;
    116. 	else
    117. 	{
    118. 		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    119. 		cout << bt->data;    //访问根结点bt的数据域
    120. 		InOrder(bt->rchid); //中序递归遍历bt的右子树
    121. 	}
    122. }
    123.  
    124. //后序遍历
    125. void BiTree::PostOrder(BiNode* bt) {
    126. 	if (bt == nullptr)
    127. 		return;
    128. 	else{
    129. 		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    130. 		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    131. 		cout << bt->data;     //访问根结点bt的数据域
    132. 	}
    133. }
    134.  
    135. int main() {
    136. 	BiTree T{};//定义对象变量 T
    137. 	std::cout << "该二叉树的前序遍历序列为：";
    138. 	T.PreOrder();
    139. 	std::cout << endl;
    140.  
    141. 	std::cout << "该二叉树的中序遍历序列为：";
    142. 	T.InOrder();
    143. 	std::cout << endl;
    144.  
    145. 	std::cout << "该二叉树的后序遍历序列为：";
    146. 	T.PostOrder();
    147. 	std::cout << endl;
    148.  
    149. 	std::cout << "该二叉树的层序遍历序列为：";
    150. 	T.LevelOrder();
    151. 	std::cout << endl;
    152.  
    153. 	system("pause");
    154. 	return 0;
    155. }

    运行结果：

    补充计算叶子结点的个数方法后： 

    1.  
    2. /*
    3. *    二叉树的使用
    4. */
    5.  
    6. #include
    7. #include
    8. using namespace std;
    9.  
    10. /*
    11. *    二叉树的结点结构
    12. */
    13. struct BiNode {
    14. 	char data;
    15. 	BiNode* lchid, * rchid;
    16. };
    17.  
    18. /*
    19. *  二叉链表的实现
    20. */
    21. class BiTree {
    22. private:
    23. 	BiNode* Creat();
    24. 	void Release(BiNode* bt);
    25. 	void PreOrder(BiNode* bt);
    26. 	void InOrder(BiNode* bt);
    27. 	void PostOrder(BiNode* bt);
    28.  
    29. 	int LeafCount(BiNode* bt);
    30. 	BiNode* root;//指向根结点的头指针
    31. public:
    32. 	BiTree() {
    33. 		root = Creat();
    34. 	}
    35. 	~BiTree() {
    36. 		Release(root);
    37. 	}
    38.  
    39. 	//前序遍历二叉树
    40. 	void PreOrder() {
    41. 		PreOrder(root);
    42. 	}
    43.  
    44. 	//中序遍历二叉树
    45. 	void InOrder() {
    46. 		InOrder(root);
    47. 	}
    48.  
    49. 	//后序遍历二叉树
    50. 	void PostOrder() {
    51. 		PostOrder(root);
    52. 	}
    53. 	//层序二叉树
    54. 	void LevelOrder();
    55.  
    56. 	//计算二叉树叶子结点个数
    57. 	void LeafCount() {
    58. 		cout<<LeafCount(root);
    59.  
    60. 	}
    61. };
    62.  
    63. //建立二叉树
    64. BiNode* BiTree::Creat()
    65. {
    66. 	BiNode* bt;
    67. 	//cout << "请依次输入二叉树序列：" << endl;
    68. 	char ch;
    69. 	cin >> ch;        //输入结点的数据信息，假设为字符
    70. 	if (ch == '#')   //建立一个空树
    71. 		bt = nullptr;
    72. 	else {
    73. 		bt = new BiNode;//开辟空间
    74. 		bt->data = ch;  //树根
    75. 		bt->lchid = Creat();//递归建立左子树
    76. 		bt->rchid = Creat();//递归建立右子树
    77. 	}
    78. 	return bt;
    79. }
    80.  
    81. //销毁二叉树(后序消除法)
    82. void BiTree::Release(BiNode* bt) {
    83. 	if (bt == nullptr)
    84. 		return;
    85. 	else {
    86. 		Release(bt->lchid);  //释放左子树
    87. 		Release(bt->rchid); //释放右子树
    88. 		delete bt;         //释放根结点
    89. 	}
    90. }
    91. //层序遍历二叉树
    92. void BiTree::LevelOrder() {
    93. 	BiNode* Q[100], * q = nullptr;
    94. 	int font = -1, rear = -1;//队列初始化
    95. 	if (root == nullptr)
    96. 		return;
    97. 	Q[++rear] = root;//根指针入队
    98. 	while (font != rear)
    99. 	{
    100. 		q = Q[++font];//出队
    101. 		cout << q->data << "\t";
    102. 		if (q->lchid != nullptr)
    103. 			Q[++rear] = q->lchid;
    104. 		if (q->rchid != nullptr)
    105. 			Q[++rear] = q->rchid;
    106. 	}
    107. }
    108.  
    109. //前序遍历
    110. void BiTree::PreOrder(BiNode* bt) {
    111. 	if (bt == nullptr)
    112. 		return;
    113. 	else {
    114. 		std::cout << bt->data; //访问根结点bt的数据域
    115. 		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    116. 		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    117. 	}
    118. }
    119.  
    120. //中序遍历
    121. void BiTree::InOrder(BiNode* bt) {
    122. 	if (bt == nullptr)
    123. 		return;
    124. 	else
    125. 	{
    126. 		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    127. 		cout << bt->data;    //访问根结点bt的数据域
    128. 		InOrder(bt->rchid); //中序递归遍历bt的右子树
    129. 	}
    130. }
    131.  
    132. //后序遍历
    133. void BiTree::PostOrder(BiNode* bt) {
    134. 	if (bt == nullptr)
    135. 		return;
    136. 	else {
    137. 		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    138. 		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    139. 		cout << bt->data;     //访问根结点bt的数据域
    140. 	}
    141. }
    142.  
    143. //计算该二叉树的叶子结点个数
    144. int BiTree::LeafCount(BiNode* bt) {
    145. 	if (bt == nullptr)
    146. 		return 0;
    147. 	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    148. 		return 1;
    149. 	}
    150. 	else
    151. 	{
    152. 		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    153. 	}
    154. }
    155.  
    156. int main() {
    157.  
    158. 	//试验：输入A B # D # # C # #
    159. 	cout << "请依次输入二叉树序列：" << endl;
    160. 	BiTree T{};//定义对象变量 T
    161. 	std::cout << "该二叉树的前序遍历序列为：";
    162. 	T.PreOrder();
    163. 	std::cout << endl;
    164. 	std::cout << "叶子结点的个数为：";
    165. 	T.LeafCount();
    166. 	cout << endl;
    167. 	system("pause");
    168. 	return 0;
    169. }

    结果： 

     补充计算二叉树深度方法：

    1.  
    2. /*
    3. *    二叉树的使用
    4. */
    5.  
    6. #include
    7. #include
    8. using namespace std;
    9.  
    10. /*
    11. *    二叉树的结点结构
    12. */
    13. struct BiNode {
    14. 	char data;
    15. 	BiNode* lchid, * rchid;
    16. };
    17.  
    18. /*
    19. *  二叉链表的实现
    20. */
    21. class BiTree {
    22. private:
    23. 	BiNode* Creat();
    24. 	void Release(BiNode* bt);
    25. 	void PreOrder(BiNode* bt);
    26. 	void InOrder(BiNode* bt);
    27. 	void PostOrder(BiNode* bt);
    28. 	int Depth(BiNode* bt);
    29. 	int LeafCount(BiNode* bt);
    30. 	BiNode* root;//指向根结点的头指针
    31. public:
    32. 	BiTree() {
    33. 		root = Creat();
    34. 	}
    35. 	~BiTree() {
    36. 		Release(root);
    37. 	}
    38.  
    39. 	//前序遍历二叉树
    40. 	void PreOrder() {
    41. 		PreOrder(root);
    42. 	}
    43.  
    44. 	//中序遍历二叉树
    45. 	void InOrder() {
    46. 		InOrder(root);
    47. 	}
    48.  
    49. 	//后序遍历二叉树
    50. 	void PostOrder() {
    51. 		PostOrder(root);
    52. 	}
    53. 	//层序二叉树
    54. 	void LevelOrder();
    55.  
    56. 	//计算树的深度
    57. 	void Depth() {
    58. 		cout << Depth(root);
    59. 	}
    60.  
    61. 	//计算二叉树叶子结点个数
    62. 	void LeafCount() {
    63. 		cout<<LeafCount(root);
    64.  
    65. 	}
    66. };
    67.  
    68. //建立二叉树
    69. BiNode* BiTree::Creat()
    70. {
    71. 	BiNode* bt;
    72. 	//cout << "请依次输入二叉树序列：" << endl;
    73. 	char ch;
    74. 	cin >> ch;        //输入结点的数据信息，假设为字符
    75. 	if (ch == '#')   //建立一个空树
    76. 		bt = nullptr;
    77. 	else {
    78. 		bt = new BiNode;//开辟空间
    79. 		bt->data = ch;  //树根
    80. 		bt->lchid = Creat();//递归建立左子树
    81. 		bt->rchid = Creat();//递归建立右子树
    82. 	}
    83. 	return bt;
    84. }
    85.  
    86. //销毁二叉树(后序消除法)
    87. void BiTree::Release(BiNode* bt) {
    88. 	if (bt == nullptr)
    89. 		return;
    90. 	else {
    91. 		Release(bt->lchid);  //释放左子树
    92. 		Release(bt->rchid); //释放右子树
    93. 		delete bt;         //释放根结点
    94. 	}
    95. }
    96. //层序遍历二叉树
    97. void BiTree::LevelOrder() {
    98. 	BiNode* Q[100], * q = nullptr;
    99. 	int font = -1, rear = -1;//队列初始化
    100. 	if (root == nullptr)
    101. 		return;
    102. 	Q[++rear] = root;//根指针入队
    103. 	while (font != rear)
    104. 	{
    105. 		q = Q[++font];//出队
    106. 		cout << q->data << "\t";
    107. 		if (q->lchid != nullptr)
    108. 			Q[++rear] = q->lchid;
    109. 		if (q->rchid != nullptr)
    110. 			Q[++rear] = q->rchid;
    111. 	}
    112. }
    113.  
    114. //前序遍历
    115. void BiTree::PreOrder(BiNode* bt) {
    116. 	if (bt == nullptr)
    117. 		return;
    118. 	else {
    119. 		std::cout << bt->data; //访问根结点bt的数据域
    120. 		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    121. 		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    122. 	}
    123. }
    124.  
    125. //中序遍历
    126. void BiTree::InOrder(BiNode* bt) {
    127. 	if (bt == nullptr)
    128. 		return;
    129. 	else
    130. 	{
    131. 		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    132. 		cout << bt->data;    //访问根结点bt的数据域
    133. 		InOrder(bt->rchid); //中序递归遍历bt的右子树
    134. 	}
    135. }
    136.  
    137. //后序遍历
    138. void BiTree::PostOrder(BiNode* bt) {
    139. 	if (bt == nullptr)
    140. 		return;
    141. 	else {
    142. 		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    143. 		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    144. 		cout << bt->data;     //访问根结点bt的数据域
    145. 	}
    146. }
    147.  
    148. //计算该二叉树的叶子结点个数
    149. int BiTree::LeafCount(BiNode* bt) {
    150. 	if (bt == nullptr)
    151. 		return 0;
    152. 	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    153. 		return 1;
    154. 	}
    155. 	else
    156. 	{
    157. 		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    158. 	}
    159. }
    160.  
    161. //	//计算二叉树的深度
    162. int BiTree::Depth(BiNode *bt){
    163. 	if (bt == nullptr)
    164. 		return 0;
    165. 	else {
    166. 		int n, m;
    167. 		m = Depth(bt->lchid);
    168. 		n = Depth(bt->rchid);
    169. 		if (m > n)
    170. 			return m + 1;
    171. 		else
    172. 			return n + 1;
    173. 	}
    174. }
    175.  
    176. int main() {
    177.  
    178. 	//试验：输入A B # D # # C # #
    179. 	cout << "请依次输入二叉树序列：" << endl;
    180. 	BiTree T{};//定义对象变量 T
    181. 	std::cout << "该二叉树的前序遍历序列为：";
    182. 	T.PreOrder();
    183. 	std::cout << endl;
    184.  
    185. 	std::cout << "叶子结点的个数为：";
    186. 	T.LeafCount();
    187. 	cout << endl;
    188. 	
    189. 	cout << "树的深度为：";
    190. 	T.Depth();
    191. 	cout << endl;
    192. 	system("pause");
    193. 	return 0;
    194. }

    运行结果：

    补充计算二叉树结点个数方法：（R+L+D=结点个数）

    1.  
    2. /*
    3. *    二叉树的使用
    4. */
    5.  
    6. #include
    7. #include
    8. using namespace std;
    9.  
    10. /*
    11. *    二叉树的结点结构
    12. */
    13. struct BiNode {
    14. 	char data;
    15. 	BiNode* lchid, * rchid;
    16. };
    17.  
    18. /*
    19. *  二叉链表的实现
    20. */
    21. class BiTree {
    22. private:
    23. 	BiNode* Creat();				   //建树
    24. 	void Release(BiNode* bt);         //销毁
    25. 	void PreOrder(BiNode* bt);	     //前序
    26. 	void InOrder(BiNode* bt);	    //中序
    27. 	void PostOrder(BiNode* bt);    //后序
    28. 	int NodeCount(BiNode* bt);	  //计算二叉树结点个数
    29. 	int Depth(BiNode* bt);		 //计算二叉树深度
    30. 	int LeafCount(BiNode* bt);	//计算二叉树叶子结点个数
    31. 	BiNode* root;			   //指向根结点的头指针
    32. public:
    33. 	BiTree() {
    34. 		root = Creat();
    35. 	}
    36. 	~BiTree() {
    37. 		Release(root);
    38. 	}
    39.  
    40. 	//前序遍历二叉树
    41. 	void PreOrder() {
    42. 		PreOrder(root);
    43. 	}
    44.  
    45. 	//中序遍历二叉树
    46. 	void InOrder() {
    47. 		InOrder(root);
    48. 	}
    49.  
    50. 	//后序遍历二叉树
    51. 	void PostOrder() {
    52. 		PostOrder(root);
    53. 	}
    54. 	//层序二叉树
    55. 	void LevelOrder();
    56.  
    57. 	//计算二叉树结点个数
    58. 	void NodeCount() {
    59. 		cout << NodeCount(root);
    60. 	}
    61.  
    62. 	//计算树的深度
    63. 	void Depth() {
    64. 		cout << Depth(root);
    65. 	}
    66.  
    67. 	//计算二叉树叶子结点个数
    68. 	void LeafCount() {
    69. 		cout<<LeafCount(root);
    70.  
    71. 	}
    72. };
    73.  
    74. //建立二叉树
    75. BiNode* BiTree::Creat()
    76. {
    77. 	BiNode* bt;
    78. 	//cout << "请依次输入二叉树序列：" << endl;
    79. 	char ch;
    80. 	cin >> ch;        //输入结点的数据信息，假设为字符
    81. 	if (ch == '#')   //建立一个空树
    82. 		bt = nullptr;
    83. 	else {
    84. 		bt = new BiNode;//开辟空间
    85. 		bt->data = ch;  //树根
    86. 		bt->lchid = Creat();//递归建立左子树
    87. 		bt->rchid = Creat();//递归建立右子树
    88. 	}
    89. 	return bt;
    90. }
    91.  
    92. //销毁二叉树(后序消除法)
    93. void BiTree::Release(BiNode* bt) {
    94. 	if (bt == nullptr)
    95. 		return;
    96. 	else {
    97. 		Release(bt->lchid);  //释放左子树
    98. 		Release(bt->rchid); //释放右子树
    99. 		delete bt;         //释放根结点
    100. 	}
    101. }
    102. //层序遍历二叉树
    103. void BiTree::LevelOrder() {
    104. 	BiNode* Q[100], * q = nullptr;
    105. 	int font = -1, rear = -1;//队列初始化
    106. 	if (root == nullptr)
    107. 		return;
    108. 	Q[++rear] = root;//根指针入队
    109. 	while (font != rear)
    110. 	{
    111. 		q = Q[++font];//出队
    112. 		cout << q->data << "\t";
    113. 		if (q->lchid != nullptr)
    114. 			Q[++rear] = q->lchid;
    115. 		if (q->rchid != nullptr)
    116. 			Q[++rear] = q->rchid;
    117. 	}
    118. }
    119.  
    120. //前序遍历
    121. void BiTree::PreOrder(BiNode* bt) {
    122. 	if (bt == nullptr)
    123. 		return;
    124. 	else {
    125. 		std::cout << bt->data; //访问根结点bt的数据域
    126. 		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    127. 		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    128. 	}
    129. }
    130.  
    131. //中序遍历
    132. void BiTree::InOrder(BiNode* bt) {
    133. 	if (bt == nullptr)
    134. 		return;
    135. 	else
    136. 	{
    137. 		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    138. 		cout << bt->data;    //访问根结点bt的数据域
    139. 		InOrder(bt->rchid); //中序递归遍历bt的右子树
    140. 	}
    141. }
    142.  
    143. //后序遍历
    144. void BiTree::PostOrder(BiNode* bt) {
    145. 	if (bt == nullptr)
    146. 		return;
    147. 	else {
    148. 		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    149. 		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    150. 		cout << bt->data;     //访问根结点bt的数据域
    151. 	}
    152. }
    153.  
    154. //计算二叉树结点个数
    155. int BiTree::NodeCount(BiNode* bt) {
    156. 	if (bt == nullptr)
    157. 		return 0;
    158. 	else {
    159. 		return NodeCount(bt->lchid) + NodeCount(bt->rchid)+1;
    160. 	}
    161. }
    162.  
    163. //计算该二叉树的叶子结点个数
    164. int BiTree::LeafCount(BiNode* bt) {
    165. 	if (bt == nullptr)
    166. 		return 0;
    167. 	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    168. 		return 1;
    169. 	}
    170. 	else
    171. 	{
    172. 		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    173. 	}
    174. }
    175.  
    176. //	//计算二叉树的深度
    177. int BiTree::Depth(BiNode *bt){
    178. 	if (bt == nullptr)
    179. 		return 0;
    180. 	else {
    181. 		int n, m;
    182. 		m = Depth(bt->lchid);
    183. 		n = Depth(bt->rchid);
    184. 		if (m > n)
    185. 			return m + 1;
    186. 		else
    187. 			return n + 1;
    188. 	}
    189. }
    190.  
    191. int main() {
    192.  
    193. 	//试验：输入A B # D # # C # #
    194. 	cout << "请依次输入二叉树序列：" << endl;
    195. 	BiTree T{};//定义对象变量 T
    196. 	std::cout << "该二叉树的前序遍历序列为：";
    197. 	T.PreOrder();
    198. 	std::cout << endl;
    199.  
    200. 	//二叉树结点个数
    201. 	cout << "二叉树结点个数为：";
    202. 	T.NodeCount();
    203. 	cout << endl;
    204. 	
    205. 	//叶子结点的个数
    206. 	std::cout << "叶子结点的个数为：";
    207. 	T.LeafCount();
    208. 	cout << endl;
    209. 	
    210. 	//树的深度
    211. 	cout << "树的深度为：";
    212. 	T.Depth();
    213. 	cout << endl;
    214.  
    215. 	system("pause");
    216. 	return 0;
    217. }

    运行结果：

    二叉树相关方法大实现： 

    • 计算二叉树深度方法
    • 计算二叉树结点个数方法：（R+L+D=结点个数）
    • 计算叶子结点的个数方法

    1.  
    2. /*
    3. *    二叉树的使用
    4. */
    5.  
    6. #include
    7. #include
    8. using namespace std;
    9.  
    10. /*
    11. *    二叉树的结点结构
    12. */
    13. struct BiNode {
    14. 	char data;
    15. 	BiNode* lchid, * rchid;
    16. };
    17.  
    18. /*
    19. *  二叉链表的实现
    20. */
    21. class BiTree {
    22. private:
    23. 	BiNode* Creat();				   //建树
    24. 	void Release(BiNode* bt);         //销毁
    25. 	void PreOrder(BiNode* bt);	     //前序
    26. 	void InOrder(BiNode* bt);	    //中序
    27. 	void PostOrder(BiNode* bt);    //后序
    28. 	int NodeCount(BiNode* bt);	  //计算二叉树结点个数
    29. 	int Depth(BiNode* bt);		 //计算二叉树深度
    30. 	int LeafCount(BiNode* bt);	//计算二叉树叶子结点个数
    31. 	BiNode* root;			   //指向根结点的头指针
    32. public:
    33. 	BiTree() {
    34. 		root = Creat();
    35. 	}
    36. 	~BiTree() {
    37. 		Release(root);
    38. 	}
    39.  
    40. 	//前序遍历二叉树
    41. 	void PreOrder() {
    42. 		PreOrder(root);
    43. 	}
    44.  
    45. 	//中序遍历二叉树
    46. 	void InOrder() {
    47. 		InOrder(root);
    48. 	}
    49.  
    50. 	//后序遍历二叉树
    51. 	void PostOrder() {
    52. 		PostOrder(root);
    53. 	}
    54. 	//层序二叉树
    55. 	void LevelOrder();
    56.  
    57. 	//计算二叉树结点个数
    58. 	void NodeCount() {
    59. 		cout << NodeCount(root);
    60. 	}
    61.  
    62. 	//计算树的深度
    63. 	void Depth() {
    64. 		cout << Depth(root);
    65. 	}
    66.  
    67. 	//计算二叉树叶子结点个数
    68. 	void LeafCount() {
    69. 		cout<<LeafCount(root);
    70.  
    71. 	}
    72. };
    73.  
    74. //建立二叉树
    75. BiNode* BiTree::Creat()
    76. {
    77. 	BiNode* bt;
    78. 	//cout << "请依次输入二叉树序列：" << endl;
    79. 	char ch;
    80. 	cin >> ch;        //输入结点的数据信息，假设为字符
    81. 	if (ch == '#')   //建立一个空树
    82. 		bt = nullptr;
    83. 	else {
    84. 		bt = new BiNode;//开辟空间
    85. 		bt->data = ch;  //树根
    86. 		bt->lchid = Creat();//递归建立左子树
    87. 		bt->rchid = Creat();//递归建立右子树
    88. 	}
    89. 	return bt;
    90. }
    91.  
    92. //销毁二叉树(后序消除法)
    93. void BiTree::Release(BiNode* bt) {
    94. 	if (bt == nullptr)
    95. 		return;
    96. 	else {
    97. 		Release(bt->lchid);  //释放左子树
    98. 		Release(bt->rchid); //释放右子树
    99. 		delete bt;         //释放根结点
    100. 	}
    101. }
    102. //层序遍历二叉树
    103. void BiTree::LevelOrder() {
    104. 	BiNode* Q[100], * q = nullptr;
    105. 	int font = -1, rear = -1;//队列初始化
    106. 	if (root == nullptr)
    107. 		return;
    108. 	Q[++rear] = root;//根指针入队
    109. 	while (font != rear)
    110. 	{
    111. 		q = Q[++font];//出队
    112. 		cout << q->data << "\t";
    113. 		if (q->lchid != nullptr)
    114. 			Q[++rear] = q->lchid;
    115. 		if (q->rchid != nullptr)
    116. 			Q[++rear] = q->rchid;
    117. 	}
    118. }
    119.  
    120. //前序遍历
    121. void BiTree::PreOrder(BiNode* bt) {
    122. 	if (bt == nullptr)
    123. 		return;
    124. 	else {
    125. 		std::cout << bt->data; //访问根结点bt的数据域
    126. 		PreOrder(bt->lchid);  //前序递归遍历bt的左子树
    127. 		PreOrder(bt->rchid); //前序递归遍历bt的右子树
    128. 	}
    129. }
    130.  
    131. //中序遍历
    132. void BiTree::InOrder(BiNode* bt) {
    133. 	if (bt == nullptr)
    134. 		return;
    135. 	else
    136. 	{
    137. 		InOrder(bt->lchid);   //中序递归遍历bt的左子树
    138. 		cout << bt->data;    //访问根结点bt的数据域
    139. 		InOrder(bt->rchid); //中序递归遍历bt的右子树
    140. 	}
    141. }
    142.  
    143. //后序遍历
    144. void BiTree::PostOrder(BiNode* bt) {
    145. 	if (bt == nullptr)
    146. 		return;
    147. 	else {
    148. 		PostOrder(bt->lchid);   //后序递归遍历bt的左子树
    149. 		PostOrder(bt->rchid);  //后序递归遍历bt的右子树
    150. 		cout << bt->data;     //访问根结点bt的数据域
    151. 	}
    152. }
    153.  
    154. //计算二叉树结点个数
    155. int BiTree::NodeCount(BiNode* bt) {
    156. 	if (bt == nullptr)
    157. 		return 0;
    158. 	else {
    159. 		return NodeCount(bt->lchid) + NodeCount(bt->rchid)+1;
    160. 	}
    161. }
    162.  
    163. //计算该二叉树的叶子结点个数
    164. int BiTree::LeafCount(BiNode* bt) {
    165. 	if (bt == nullptr)
    166. 		return 0;
    167. 	if (bt->lchid == nullptr && bt->rchid == nullptr) {
    168. 		return 1;
    169. 	}
    170. 	else
    171. 	{
    172. 		return LeafCount(bt->lchid) + LeafCount(bt->rchid);
    173. 	}
    174. }
    175.  
    176. //	//计算二叉树的深度
    177. int BiTree::Depth(BiNode *bt){
    178. 	if (bt == nullptr)
    179. 		return 0;
    180. 	else {
    181. 		int n, m;
    182. 		m = Depth(bt->lchid);
    183. 		n = Depth(bt->rchid);
    184. 		if (m > n)
    185. 			return m + 1;
    186. 		else
    187. 			return n + 1;
    188. 	}
    189. }
    190.  
    191. int main() {
    192.  
    193. 	//试验：输入A B # D # # C # #
    194. 	cout << "请依次输入二叉树序列：" << endl;
    195. 	BiTree T{};//定义对象变量 T
    196. 	std::cout << "该二叉树的前序遍历序列为：";
    197. 	T.PreOrder();
    198. 	std::cout << endl;
    199.  
    200. 	//二叉树结点个数
    201. 	cout << "二叉树结点个数为：";
    202. 	T.NodeCount();
    203. 	cout << endl;
    204. 	
    205. 	//叶子结点的个数
    206. 	std::cout << "叶子结点的个数为：";
    207. 	T.LeafCount();
    208. 	cout << endl;
    209. 	
    210. 	//树的深度
    211. 	cout << "树的深度为：";
    212. 	T.Depth();
    213. 	cout << endl;
    214.  
    215. 	system("pause");
    216. 	return 0;
    217. }

    运行结果：

     

  • 相关阅读:
    yolov7 onnx tensorrt 批量预测 全网首发
    在Linux上用Gitlab搭建自己的私有库并配置cpolar内网穿透
    YOLOv8-Pose推理详解及部署实现
    【nlp-with-transformers】|Transformers中的generate函数解析
    nodejs操作rabbitMQ amqplib库 消息持久化
    Word2Vec词向量训练、使用及可视化操作
    LeetCode 33.搜索旋转排序数组
    利用Proxifier配置多级代理
    Linux 主机数据拷贝与 Linux 服务器之间拷贝文件的方法
    原生js--购物车案例
  • 原文地址：https://blog.csdn.net/m0_63064861/article/details/127556214