devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的定义与C++实现_c++定义二叉树结构体

作者：繁依Fanyi0 | 2024-05-25 11:55:54

赞

踩

c++定义二叉树结构体

        树，是有限节点的集合。生活中的树是树根在下面，数据结构中的树的根在顶部，如下图：

        公司的人员组织架构，董事长，总经理，副总。。。，这种模型可以用二叉树表示，还有一些压缩算法也用到了树结构。

树的几个概念

（1）度：有几个直接的孩子，例如，A的度是3，它有BCD三个孩子，B的度是2，它有EF两个孩子，度为0的节点也就是叶子节点（终端节点）

（2）祖先：E的祖先是B,A , 从当前节点一直往上找

（3）叶子节点：下面的一层称为叶子节点，也可以称为终端节点。

（4）根：非叶子节点。

（5）树的深度，如下图

 （6）森林：不交叉的几棵树在一起称为森林

二叉树

       所有节点的度都小于等于2的树称为二叉树。下面这几种都可以称为二叉树

1、二叉树的遍历

       3种遍历方式，根据根节点的位置，分为前序，中序，后序。

                                                                               前序：根左右，ABC

                                                                              中序 ：左根右, BAC

                                                                        后序遍历：左右根, BCA

       例如下面这颗二叉树

          从根节点A在结果中的位置也可以看出是那种遍历方式。

2、二叉树的存储结构

     （1）顺序存储，类似于数组，例如下面这颗二叉树，在数组中的存储是：3561972

       数组存储时，如果节点不存在就用0表示，例如下面的，在数组中就是35019

        顺序存储可以作为一种特殊形式，有相关需求时可以采用，

     （2）链式存储，这是二叉树最好的存储形式，用一个结构体表示节点，有数据成员，指向左子树的指针，指向右子树的指针。

        

3、满二叉树与完全二叉树

       完全二叉树的定义：如果二叉树的深度为h, 除h层外，其它各层的节点数都达到最大数，且第h层的所有节点都连续集中在最左边，这种二叉树称为完全二叉树。

       

      

C++实现二叉树

     下面介绍如何用数组和链表，例如实现下面这颗树

  基于数组的二叉树实现 

  头文件TreeArray.h

  1. /*
  3. 用数组实现二叉树
  5. */
  6.  
  7. #pragma once
  8.  
  9. //节点的插入方向
  10. enum DIRECTION
  11. {
  12. 	LEFT,
  13. 	RIGHT
  14. };
  15.  
  16. class TreeArray
  17. {
  18. public:
  19. 	TreeArray(int size, int *pRoot);    //构造创建树
  20. 	~TreeArray();           //销毁树
  21.  
  22. 	int *SearchNode(int nodeIndex);
  23. 	bool AddNode(int nodeIndex, DIRECTION dirc, int *pNode);
  24. 	bool DeleteNode(int nodeIndex, int *pNode);
  25. 	void TreeTraverse();    //遍历树
  26.  
  27. private:
  28. 	int *m_pTree;
  29. 	int m_iSize;    //树的容量
  30. };

   TreeArray.cpp

  1. #include "TreeArray.h"
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. TreeArray::TreeArray(int size,int *pRoot)
  7. {
  8. 	if (size > 0)
  9. 	{
  10. 		m_iSize = size;
  11. 		m_pTree = new int[size];
  12.  
  13. 		for (int i = 0; i < size; i++)
  14. 		{
  15. 			m_pTree[i] = 0;
  16. 		}
  17.  
  18. 		m_pTree[0] = *pRoot;
  19. 	}
  20. 	else
  21. 	{
  22. 		m_iSize = 0;
  23. 		m_pTree = nullptr;
  24. 	}
  25. }
  26.  
  27. TreeArray::~TreeArray()
  28. {
  29. 	if (m_pTree != nullptr)
  30. 	{
  31. 		delete[] m_pTree;
  32. 		m_pTree = nullptr;
  33. 	}
  34. }
  35.  
  36. int * TreeArray::SearchNode(int nodeIndex)
  37. {
  38. 	if (nodeIndex < m_iSize && m_pTree >= 0)
  39. 	{
  40. 		if (m_pTree[nodeIndex] == 0)  //0表示空节点
  41. 		{
  42. 			return nullptr;
  43. 		}
  44. 	}
  45. 	else 
  46. 	{
  47. 		return nullptr;
  48. 	}
  49.  
  50. 	return &m_pTree[nodeIndex];
  51. }
  52.  
  53. bool TreeArray::AddNode(int nodeIndex, DIRECTION dirc, int * pNode)
  54. {
  55. 	if (nodeIndex < 0 || nodeIndex >= m_iSize)
  56. 	{
  57. 		return false;
  58. 	}
  59.  
  60. 	if (m_pTree[nodeIndex] == 0)
  61. 	{
  62. 		return false;
  63. 	}
  64.  
  65. 	if (dirc == LEFT)
  66. 	{
  67. 		int insertId = nodeIndex * 2 + 1;
  68. 		if (insertId >= m_iSize)
  69. 		{
  70. 			return false;
  71. 		}
  72.  
  73. 		if (m_pTree[insertId] != 0)
  74. 		{
  75. 			return false;
  76. 		}
  77.  
  78. 		m_pTree[insertId] = *pNode;
  79. 	}
  80. 	else if (dirc == RIGHT)
  81. 	{
  82. 		int insertId = nodeIndex * 2 + 2;
  83. 		if (insertId >= m_iSize)
  84. 		{
  85. 			return false;
  86. 		}
  87.  
  88. 		if (m_pTree[insertId] != 0)
  89. 		{
  90. 			return false;
  91. 		}
  92.  
  93. 		m_pTree[insertId] = *pNode;
  94. 	}
  95.  
  96. 	return true;
  97. }
  98.  
  99. bool TreeArray::DeleteNode(int nodeIndex, int * pNode)
  100. {
  101. 	if (nodeIndex < 0 || nodeIndex >= m_iSize)
  102. 	{
  103. 		return false;
  104. 	}
  105.  
  106. 	if (m_pTree[nodeIndex] == 0)
  107. 	{
  108. 		return false;
  109. 	}
  110.  
  111. 	*pNode = m_pTree[nodeIndex];
  112. 	m_pTree[nodeIndex] = 0;
  113. 	return true;
  114. }
  115.  
  116. void TreeArray::TreeTraverse()
  117. {
  118. 	for (int i = 0; i<m_iSize; i++)
  119. 	{
  120. 		cout << m_pTree[i] << " ";
  121. 	}
  122. 	cout << endl;
  123. }

  main函数测试

  1. #include <iostream>
  2. #include "TreeArray.h"
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8. 	int root = 666;
  9. 	TreeArray *pTree = new TreeArray(10, &root);
  10. 	int node1 = 500;
  11. 	int node2 = 800;
  12. 	pTree->AddNode(0, LEFT, &node1);
  13. 	pTree->AddNode(0, RIGHT, &node2);
  14.  
  15. 	int node3 = 200;
  16. 	int node4 = 600;
  17. 	pTree->AddNode(1, LEFT, &node3);
  18. 	pTree->AddNode(1, RIGHT, &node4);
  19.  
  20. 	int node5 = 900;
  21. 	int node6 = 700;
  22. 	pTree->AddNode(2, LEFT, &node5);
  23. 	pTree->AddNode(2, RIGHT, &node6);
  24.  
  25. 	//遍历
  26. 	pTree->TreeTraverse();
  27.  
  28. 	//查找
  29. 	int *pValue = pTree->SearchNode(3);
  30. 	cout << "index = 3的节点值是" << *pValue << endl;
  31.  
  32. 	//删除
  33. 	int dValue = 0;
  34. 	pTree->DeleteNode(6, &dValue);
  35.  
  36. 	//遍历
  37. 	pTree->TreeTraverse();
  38.  
  39. 	delete pTree;
  40. 	return 0;
  41. }

 运行结果

 基于链表的二叉树实现

        用链表实现二叉树，得先定义好二叉树的节点类型，根据二叉树的性质，节点得有5个属性：索引、数据 、左孩子指针、右孩子指针 、父结点指针 。如下所示：

  1. struct Node
  2. {
  3. 	int index;
  4. 	int data;
  5. 	Node *pLChild;  //左子树
  6. 	Node *pRChild;  //右字数
  7. 	Node *pParent;  //父节点
  8. };

 还得实现3种遍历方式，使用递归遍历是比较方便的。具体代码如下

      Tree.h

  1. #ifndef TREE_H
  2. #define TREE_H
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. //树的节点
  10. struct Node
  11. {
  12. 	Node(int _data = 0);
  13. 	Node *SearchNode(int nodeIndex);
  14. 	void DeleteNode();
  15. 	void PreOrderTraversal();
  16. 	void MiddleOrderTraversal();
  17. 	void LastOrderTraversal();
  18. 	int index;
  19. 	int data;
  20. 	Node *pLChild;  //左子树
  21. 	Node *pRChild;  //右字数
  22. 	Node *pParent;  //父节点
  23. };
  24.  
  25. //节点的插入方向
  26. enum DIRECTION
  27. {
  28. 	LEFT,
  29. 	RIGHT
  30. };
  31.  
  32. //二叉树
  33. class Tree
  34. {
  35. public:
  36. 	Tree(int data = 0);                                                            //创建树
  37. 	~Tree();                                                           //销毁树
  38. 	Node *SearchNode(int nodeIndex);                                  //搜索结点
  39. 	bool AddNode(int nodeIndex, DIRECTION direction, Node *pNode);   //添加结点
  40. 	bool DeleteNode(int nodeIndex, Node *pNode);                      //删除结点
  41. 	void PreOrderTraversal();                                          //前序遍历
  42. 	void MiddleOrderTraversal();                                           //中序遍历
  43. 	void LastOrderTraversal();                                         //后序遍历
  44.  
  45. private:
  46. 	Node *m_pRoot;
  47. };
  48.  
  49. #endif

  Tree.cpp

  1. #include "Tree.h"
  2.  
  3. Node::Node(int _data)
  4. {
  5. 	index = 0;
  6. 	data = _data;
  7. 	pLChild = NULL;
  8. 	pRChild = NULL;
  9. 	pParent = NULL;
  10. }
  11.  
  12. Node *Node::SearchNode(int nodeIndex)
  13. {
  14. 	if (this->index == nodeIndex)
  15. 	{
  16. 		return this;
  17. 	}
  18.  
  19. 	Node *temp = NULL;
  20. 	if (this->pLChild != NULL)
  21. 	{
  22. 		if (this->pLChild->index == nodeIndex)
  23. 		{
  24. 			return this->pLChild;
  25. 		}
  26. 		else
  27. 		{
  28. 			temp = this->pLChild->SearchNode(nodeIndex);
  29. 			if (temp != NULL)
  30. 			{
  31. 				return temp;
  32. 			}
  33. 		}
  34. 	}
  35.  
  36. 	if (this->pRChild != NULL)
  37. 	{
  38. 		if (this->pRChild->index == nodeIndex)
  39. 		{
  40. 			return this->pRChild;
  41. 		}
  42. 		else
  43. 		{
  44. 			temp = this->pRChild->SearchNode(nodeIndex);
  45. 			if (temp != NULL)
  46. 			{
  47. 				return temp;
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	return NULL;
  53. }
  54.  
  55. void Node::DeleteNode()
  56. {
  57. 	if (this->pLChild != NULL)
  58. 	{
  59. 		this->pLChild->DeleteNode();
  60. 	}
  61. 	if (this->pRChild != NULL)
  62. 	{
  63. 		this->pRChild->DeleteNode();
  64. 	}
  65. 	if (this->pParent != NULL)
  66. 	{
  67. 		if (this->pParent->pLChild == this)
  68. 		{
  69. 			this->pParent->pLChild = NULL;
  70. 		}
  71. 		if (this->pParent->pRChild == this)
  72. 		{
  73. 			this->pParent->pRChild = NULL;
  74. 		}
  75. 	}
  76.  
  77. 	delete this;
  78. }
  79.  
  80. void Node::PreOrderTraversal()
  81. {
  82. 	cout << this->index << "     " << this->data << endl;
  83. 	if (this->pLChild != NULL)
  84. 	{
  85. 		this->pLChild->PreOrderTraversal();
  86. 	}
  87. 	if (this->pRChild != NULL)
  88. 	{
  89. 		this->pRChild->PreOrderTraversal();
  90. 	}
  91. }
  92.  
  93. void Node::MiddleOrderTraversal()
  94. {
  95.  
  96. 	if (this->pLChild != NULL)
  97. 	{
  98. 		this->pLChild->MiddleOrderTraversal();
  99. 	}
  100.  
  101. 	cout << this->index << "     " << this->data << endl;
  102.  
  103. 	if (this->pRChild != NULL)
  104. 	{
  105. 		this->pRChild->MiddleOrderTraversal();
  106. 	}
  107. }
  108.  
  109. void Node::LastOrderTraversal()
  110. {
  111. 	if (this->pLChild != NULL)
  112. 	{
  113. 		this->pLChild->LastOrderTraversal();
  114. 	}
  115.  
  116. 	if (this->pRChild != NULL)
  117. 	{
  118. 		this->pRChild->LastOrderTraversal();
  119. 	}
  120.  
  121. 	cout << this->index << "     " << this->data << endl;
  122. }
  123.  
  124. Tree::Tree(int data)
  125. {
  126. 	m_pRoot = new Node(data);
  127. }
  128.  
  129. Tree::~Tree()
  130. {
  131. 	//DeleteNode(0, NULL);
  132. 	m_pRoot->DeleteNode();
  133. }
  134.  
  135. Node *Tree::SearchNode(int nodeIndex)
  136. {
  137. 	return m_pRoot->SearchNode(nodeIndex);
  138. }
  139.  
  140. bool Tree::AddNode(int nodeIndex, DIRECTION direction, Node *pNode)
  141. {
  142. 	Node *temp = SearchNode(nodeIndex);
  143. 	if(temp == NULL)
  144. 	{
  145. 		return false;
  146. 	}
  147. 	
  148. 	Node *node = new Node();
  149. 	if(node == NULL)
  150. 	{
  151. 		return false;
  152. 	}
  153. 	node->index = pNode->index;
  154. 	node->data = pNode->data;
  155. 	node->pParent = temp;
  156.  
  157. 	if(direction == LEFT)
  158. 	{
  159. 		temp->pLChild = node;
  160. 	}
  161.  
  162. 	if(direction == RIGHT)
  163. 	{
  164. 		temp->pRChild = node;
  165. 	}
  166.  
  167. 	return true;
  168. 	
  169. }
  170.  
  171. bool Tree::DeleteNode(int nodeIndex, Node *pNode)
  172. {
  173. 	Node *temp = SearchNode(nodeIndex);
  174. 	if(temp == NULL)
  175. 	{
  176. 		return false;
  177. 	}
  178.  
  179. 	if(pNode != NULL)
  180. 	{
  181. 		pNode->data = temp->data;
  182. 	}
  183.  
  184. 	temp->DeleteNode();
  185. 	return true;
  186. }
  187.  
  188. void Tree::PreOrderTraversal()
  189. {
  190. 	m_pRoot->PreOrderTraversal();
  191. }
  192.  
  193. void Tree::MiddleOrderTraversal()
  194. {
  195. 	m_pRoot->MiddleOrderTraversal();
  196. }
  197.  
  198. void Tree::LastOrderTraversal()
  199. {
  200. 	m_pRoot->LastOrderTraversal();
  201. }

 main方法测试：

  1. #include <iostream>
  2. #include "Tree.h"
  3.  
  4. int main(void)
  5. {
  6. 	Node *node1 = new Node();
  7. 	node1->index = 1;
  8. 	node1->data = 500;
  9.  
  10. 	Node *node2 = new Node();
  11. 	node2->index = 2;
  12. 	node2->data = 800;
  13.  
  14. 	Node *node3 = new Node();
  15. 	node3->index = 3;
  16. 	node3->data = 200;
  17.  
  18. 	Node *node4 = new Node();
  19. 	node4->index = 4;
  20. 	node4->data = 600;
  21.  
  22. 	Node *node5 = new Node();
  23. 	node5->index = 5;
  24. 	node5->data = 900;
  25.  
  26. 	Node *node6 = new Node();
  27. 	node6->index = 6;
  28. 	node6->data = 700;
  29.  
  30. 	Tree *tree = new Tree(666);
  31.  
  32. 	tree->AddNode(0, LEFT, node1);
  33. 	tree->AddNode(0, RIGHT, node2);
  34.  
  35. 	tree->AddNode(1, LEFT, node3);
  36. 	tree->AddNode(1, RIGHT, node4);
  37.  
  38. 	tree->AddNode(2, LEFT, node5);
  39. 	tree->AddNode(2, RIGHT, node6);
  40.  
  41. 	//tree->DeleteNode(6, NULL);
  42. 	//tree->DeleteNode(5, NULL);
  43.  
  44. 	tree->DeleteNode(2, NULL);
  45.  
  46. 	tree->PreOrderTraversal();
  47.  
  48. 	//tree->MiddleOrderTraversal();
  49. 	//tree->LastOrderTraversal();
  50.  
  51. 	delete tree;
  52.  
  53. 	system("pause");
  54. 	return 0;
  55. }

 以上就是二叉树的两种实现方，推荐使用链表的形式。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/621960
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号