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

二叉树——从建立到销毁_二叉树的销毁

作者：笔触狂放9 | 2024-05-25 12:18:24

赞

踩

二叉树的销毁

目录

结构体和类定义

一、二叉树建立

前序遍历建立二叉树

二、遍历

2.1前序遍历

2.2中序遍历

2.3后序遍历

2.4层次遍历

三、求结点

3.1求父结点

3.2求左子结点、右子结点

四、求高度、深度、判空等

4.1高度

4.2结点个数

4.3判空

4.4结点是否存在

4.5结点数据

4.6销毁二叉树

五、主函数

六、总代码

七、总结

前言

个人认为二叉树的核心是递归，绝大部分的操作，都可以使用递归来实现。

主要操作

结构体和类定义

  1. template <class T>
  2. struct BinTreeNode{
  3. 	T data;
  4. 	BinTreeNode *leftChild,*rightChild;
  5. 	BinTreeNode():leftChild(NULL),rightChild(NULL){}
  6. 	BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL)
  7. 	:data(x),leftChild(l),rightChild(r){}
  8. };
  9.  
  10. //类定义 
  11. //对象: 结点的有限集合, 二叉树是有序树
  12. template <class T>
  13. class BinaryTree {
  14.  
  15. public:
  16.      //构造函数
  17.      BinaryTree ():root(NULL){}			
  18.      BinaryTree(T value):RefValue(value),root(NULL){}
  19.      BinaryTree(BinaryTree<T>& s);
  20.      ~BinaryTree(){destroy(root);}
  21. 	 BinaryTree (BinTreeNode<T> *lch,BinTreeNode<T> *rch, T item);
  22.      //构造函数, 以item为根, lch和rch为左、右子
  23.  
  24.  
  25.      //树构造一棵二叉树
  26. 	 //BinTreeNode<T> *createpretree(int l,int i,string &a);
  27. 	 void CreatTree(BinTreeNode<T> *& root);
  28.  
  29.     //高度、深度、判空、取结点
  30. 	 int Height (BinTreeNode<T> * root);//求树深度或高度{return Height(root);}
  31. 	 int Size (BinTreeNode<T> * root);//求树中结点个数{return Size(root);}
  32.      bool IsEmpty (){return (root==NULL)?true:false;};		//判二叉树空否？ 
  33.      bool Find (T& item,BinTreeNode<T> * root);		//判断item是否在树中
  34.      BinTreeNode<T> *getData(T& item,BinTreeNode<T> * root);	//取得结点数据
  35. 	 
  36.      //求结点
  37.      BinTreeNode<T> *Parent (BinTreeNode <T> *subTree,BinTreeNode<T> *t); 
  38. 	 //求结点 t 的双亲{return (root==NULL||root==t)?NULL:Parent(root,t);}					
  39.      BinTreeNode<T> *LeftChild (BinTreeNode<T> *t)//求结点 t 的左子女
  40.      {return (t!=NULL)?t->leftChild:NULL;}       				
  41.      BinTreeNode<T> *RightChild (BinTreeNode<T> *t)//求结点 t 的右子女
  42. 	 {return (t!=NULL)?t->rightChild:NULL;}
  43. 	 
  44.      
  45.      //遍历
  46. 	 BinTreeNode<T> *getRoot (){return root;}	//取根
  47. 	 BinTreeNode<T> *CopyTree( BinTreeNode<T> *orignode); 
  48. 	void preOrder ( BinTreeNode<T> *root);//前序遍历 	
  49.            
  50. 	 void inOrder ( BinTreeNode<T> * root);//中序遍历 
  51. 		
  52. 	 void postOrder ( BinTreeNode<T> * root);//后序遍历 
  53. 		
  54. 	 void levelOrder (BinTreeNode<T> * root);//层次序遍历 
  55. 		
  56.  
  57. 	protected:
  58. 		BinTreeNode<T> * root;
  59. 		T RefValue;
  60. 		void destroy (BinTreeNode<T> * subTree);
  61.  
  62. };

一、二叉树建立

前序遍历建立二叉树

空传入

  1. template <class T>
  2. void BinaryTree<T>::CreatTree(BinTreeNode<T> *& root) 
  3. {  T item;
  4.    cin>>item;
  5.    if(item!=RefValue)
  6.    {   root=new BinTreeNode<T>(item);
  7.        if(root ==NULL)
  8.         {  cerr<<"分配结点失败！\n";  exit(1);  }
  9.        CreatTree(root->leftChild);
  10.        CreatTree(root->rightChild);
  11.    }
  12.    else root=NULL;
  13. }

传引用

  1. template <class T>
  2. BinTreeNode<T> * BinaryTree<T>::createpretree(int l,int i,string &a)
  3. {//l为数组a的长度，i为数组下标
  4. 	BinTreeNode<T> *root;
  5. 	if(l==0||a[i]=='#'||i==l)root=NULL;
  6. 	else
  7. 	{
  8. 		root=new BinTreeNode<T>(a[i++]);
  9. 		root->leftChild=createpretree(l,i,a);
  10. 		root->rightChild=createpretree(l,++i,a);
  11. 	}
  12. 	return root; 
  13. }

二、遍历

2.1前序遍历

  1. template <class T>
  2. void BinaryTree<T>::preOrder(BinTreeNode<T> * root)   
  3. {   
  4.      if (root != NULL)
  5.       {
  6.     	cout<<root->data<<" ";        //先序访问根结点
  7. 	    preOrder(root->leftChild);     //遍历左子树
  8. 	    preOrder(root->rightChild);   //先序遍历右子树
  9.        }
  10. }

2.2中序遍历

  1. template <class T>
  2. void BinaryTree<T>::inOrder(BinTreeNode<T> * root)   
  3. {   
  4.      if (root != NULL)
  5.       {
  6. 	  	inOrder(root->leftChild);      //中序遍历左子树
  7.         cout<<root->data<<" ";       //访问根结点
  8. 	    inOrder(root->rightChild);   //中序遍历右子树
  9.        }
  10. }

2.3后序遍历

  1. template <class T>
  2. void BinaryTree<T>::postOrder(BinTreeNode<T> * root)   
  3. {   
  4.      if (root != NULL)
  5.       {	
  6. 	    postOrder(root->leftChild);     //后序遍历左子树
  7. 	    postOrder(root->rightChild);   //遍历右子树
  8.         cout<<root->data<<" ";         //后序访问根结点
  9.        }
  10. }

2.4层次遍历

  1. template <class T>
  2. void BinaryTree<T>::levelOrder(BinTreeNode<T> *root)
  3. {    if (root == NULL) return;
  4.      queue<BinTreeNode<T> * > Q;
  5.      BinTreeNode<T> *p;   
  6.      Q.push(root); 	//根结点入队列
  7.      while (!Q.empty()) 
  8.      {   
  9.          p=Q.front();
  10.           cout<<(Q.front())->data<<" ";  //输出出队结点的数据
  11. 		  Q.pop();             //队头结点出队
  12.           if (p->leftChild != NULL)  //若出队结点有左孩子
  13.               { Q.push(p->leftChild);}  //左孩子入队列p=p->leftChild;
  14.           if (p->rightChild != NULL) 
  15. 	     {Q.push(p->rightChild);
  16. 		 }
  17.      }     
  18. }

有一种方法是使用自定义的队列，思路大致和上面相同，但在此不写怎么麻烦的方法了。

三、求结点

3.1求父结点

  1. template <class T>
  2. BinTreeNode<T> *BinaryTree<T>::
  3. Parent (BinTreeNode <T> *subTree,BinTreeNode <T> *t)
  4. {
  5.      if (subTree == NULL) return NULL;
  6.      if (subTree->leftChild == t ||subTree->rightChild == t)
  7. 	  return subTree;	//找到, 返回父结点地址
  8.      BinTreeNode <T> *p;
  9.      if ((p = Parent (subTree->leftChild, t)) != NULL)  
  10.          return p;	         //递归在左子树中搜索
  11.          else return Parent (subTree->rightChild, t);
  12.  				         //递归在右子树中搜索
  13. }

3.2求左子结点、右子结点

  1.     //定义在类中
  2.      BinTreeNode<T> *LeftChild (BinTreeNode<T> *t)
  3.      {return (t!=NULL)?t->leftChild:NULL;}//求结点 t 的左子女
  4.             				
  5.      BinTreeNode<T> *RightChild (BinTreeNode<T> *t)
  6. 	 {return (t!=NULL)?t->rightChild:NULL;}	//求结点 t 的右子女

四、求高度、深度、判空等

4.1高度

  1. template <class T>
  2. int  BinaryTree<T>::Height(BinTreeNode<T> * root) 
  3. {
  4.      if (root == NULL) return 0;	
  5.      else 
  6. 	 {     
  7. 	  int i = Height(root->leftChild);
  8.       int j = Height(root->rightChild);
  9. 	  return (i < j) ? j+1 : i+1; 
  10. 	}
  11. }

4.2结点个数

  1. template <class T>
  2. int BinaryTree<T>::Size(BinTreeNode<T> * root)  
  3. {
  4.     if (root == NULL) return 0;	  //空树
  5.     else 
  6.        return 1+Size(root->leftChild)+Size(root->rightChild);
  7. }

4.3判空

  1. //在类中
  2. bool IsEmpty (){return (root==NULL)?true:false;};

4.4结点是否存在

  1. template<class T>
  2. bool BinaryTree<T>::Find (T& item,BinTreeNode<T> * root)
  3. {
  4. 	if(this->getData(item,root)==NULL)return false;
  5. 	else return true;
  6. }

4.5结点数据

  1. template<class T>
  2. BinTreeNode<T> *BinaryTree<T>::getData(T& item,BinTreeNode<T> * root)
  3. {
  4. 	if(root==NULL)return NULL;
  5. 	if(root->data==item)return root;
  6. 	return getData(item,root->leftChild)!=NULL?getData(item,root->leftChild):getData(item,root->rightChild);
  7.   
  8. }

4.6销毁二叉树

  1. template<class T>
  2. void BinaryTree<T>::destroy (BinTreeNode<T>* subTree) {
  3. //私有函数: 后序遍历删除根为subTree的子树；
  4.      if (subTree != NULL) {
  5.           destroy (subTree->leftChild);     //删除左子树
  6.  	      destroy (subTree->rightChild);   //删除右子树
  7.  	      delete subTree; 			 //删除根结点
  8. 	 }
  9. }

五、主函数

  1. int main()
  2. {
  3. 	
  4. 	char ch;
  5. 	cout<<"输入结束标志：";
  6. 	cin>>ch;
  7.     BinaryTree<char> t(ch);
  8. 	BinTreeNode<char>* head=t.getRoot();
  9. 	t.CreatTree(head);
  10. 	return 0;
  11.  }

六、总代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. template <class T>
  4. struct BinTreeNode{
  5. 	T data;
  6. 	BinTreeNode *leftChild,*rightChild;
  7. 	BinTreeNode():leftChild(NULL),rightChild(NULL){}
  8. 	BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL)
  9. 	:data(x),leftChild(l),rightChild(r){}
  10. };
  11.  
  12. //类定义 
  13. //对象: 结点的有限集合, 二叉树是有序树
  14. template <class T>
  15. class BinaryTree {
  16.  
  17. public:
  18.      BinaryTree ():root(NULL){}			//构造函数
  19.      BinaryTree(T value):RefValue(value),root(NULL){}
  20.      BinaryTree(BinaryTree<T>& s);
  21.      ~BinaryTree(){destroy(root);}
  22. 	 BinaryTree (BinTreeNode<T> *lch,BinTreeNode<T> *rch, T item);
  23. 	    //构造函数, 以item为根, lch和rch为左、右子
  24.         //树构造一棵二叉树
  25. 		//BinTreeNode<T> *createpretree(int l,int i,string &a);
  26. 	void CreatTree(BinTreeNode<T> *& root);
  27. 	 int Height (BinTreeNode<T> * root);//求树深度或高度{return Height(root);}
  28. 	 int Size (BinTreeNode<T> * root);//求树中结点个数{return Size(root);}
  29.      bool IsEmpty (){return (root==NULL)?true:false;};		//判二叉树空否？ 
  30. 	 
  31.      BinTreeNode<T> *Parent (BinTreeNode <T> *subTree,BinTreeNode<T> *t); 
  32. 	 //求结点 t 的双亲{return (root==NULL||root==t)?NULL:Parent(root,t);}
  33. 						
  34.      BinTreeNode<T> *LeftChild (BinTreeNode<T> *t)
  35.      {return (t!=NULL)?t->leftChild:NULL;}//求结点 t 的左子女
  36.             				
  37.      BinTreeNode<T> *RightChild (BinTreeNode<T> *t)
  38. 	 {return (t!=NULL)?t->rightChild:NULL;}	//求结点 t 的右子女
  39. 	 
  40.      //bool Insert (const T& item);		//在树中插入新元素
  41.      //bool Remove (T item);	//在树中删除元素
  42.      bool Find (T& item,BinTreeNode<T> * root);		//判断item是否在树中
  43.      BinTreeNode<T> *getData(T& item,BinTreeNode<T> * root);	//取得结点数据
  44. 	 BinTreeNode<T> *getRoot (){return root;}	//取根
  45. 	 BinTreeNode<T> *CopyTree( BinTreeNode<T> *orignode); 
  46. 	void preOrder ( BinTreeNode<T> *root);//前序遍历 	
  47.            
  48. 	 void inOrder ( BinTreeNode<T> * root);//中序遍历 
  49. 		
  50. 	 void postOrder ( BinTreeNode<T> * root);//后序遍历 
  51. 		
  52. 	 void levelOrder (BinTreeNode<T> * root);//层次序遍历 
  53. 		
  54.  
  55. 	protected:
  56. 		BinTreeNode<T> * root;
  57. 		T RefValue;
  58. 		void destroy (BinTreeNode<T> * subTree);
  59.  
  60. };
  61.  
  62. //template <class T>
  63. //BinaryTree::BinaryTree()
  64. /*
  65. //建立二叉树 
  66. template <class T>
  67. BinTreeNode<T> * BinaryTree<T>::createpretree(int l,int i,string &a)
  68. {
  69. 	BinTreeNode<T> *root;
  70. 	if(l==0||a[i]=='#'||i==l)root=NULL;
  71. 	else
  72. 	{
  73. 		root=new BinTreeNode<T>(a[i++]);
  74. 		root->leftChild=createpretree(l,i,a);
  75. 		root->rightChild=createpretree(l,++i,a);
  76. 	}
  77. 	return root; 
  78. }*/
  79.  
  80. //先序遍历创建一棵二叉树
  81. template <class T>
  82. void BinaryTree<T>::CreatTree(BinTreeNode<T> *& root) 
  83. {  T item;
  84.    cin>>item;
  85.    if(item!=RefValue)
  86.    {   root=new BinTreeNode<T>(item);
  87.        if(root ==NULL)
  88.         {  cerr<<"分配结点失败！\n";  exit(1);  }
  89.        CreatTree(root->leftChild);
  90.        CreatTree(root->rightChild);
  91.    }
  92.    else root=NULL;
  93. }
  94.  
  95. //遍历
  96. //先序遍历
  97. template <class T>
  98. void BinaryTree<T>::preOrder(BinTreeNode<T> * root)   
  99. {   
  100.      if (root != NULL)
  101.       {	cout<<root->data<<" ";        //先序访问根结点
  102. 	preOrder(root->leftChild);     //遍历左子树
  103. 	preOrder(root->rightChild);   //先序遍历右子树
  104.        }
  105. }
  106.  
  107. //中序遍历
  108. template <class T>
  109. void BinaryTree<T>::inOrder(BinTreeNode<T> * root)   
  110. {   
  111.      if (root != NULL)
  112.       {
  113. 	  	inOrder(root->leftChild);      //中序遍历左子树
  114.         cout<<root->data<<" ";       //访问根结点
  115. 	    inOrder(root->rightChild);   //中序遍历右子树
  116.        }
  117. }
  118.  
  119. //后序遍历
  120. template <class T>
  121. void BinaryTree<T>::postOrder(BinTreeNode<T> * root)   
  122. {   
  123.      if (root != NULL)
  124.       {	
  125. 	    postOrder(root->leftChild);     //后序遍历左子树
  126. 	    postOrder(root->rightChild);   //遍历右子树
  127.         cout<<root->data<<" ";         //后序访问根结点
  128.        }
  129. }
  130.  
  131. //层次遍历
  132. template <class T>
  133. void BinaryTree<T>::levelOrder(BinTreeNode<T> *root)
  134. {    if (root == NULL) return;
  135.      queue<BinTreeNode<T> * > Q;
  136.      BinTreeNode<T> *p;   
  137.      Q.push(root); 	//根结点入队列
  138.      while (!Q.empty()) 
  139.      {   
  140.          p=Q.front();
  141.           cout<<(Q.front())->data<<" ";  //输出出队结点的数据
  142. 		  Q.pop();             //队头结点出队
  143.           if (p->leftChild != NULL)  //若出队结点有左孩子
  144.               { Q.push(p->leftChild);}  //左孩子入队列p=p->leftChild;
  145.           if (p->rightChild != NULL) 
  146. 	     {Q.push(p->rightChild);
  147. 		 }
  148.      }     
  149. }
  150. //结点个数 
  151. template <class T>
  152. int BinaryTree<T>::Size(BinTreeNode<T> * root)  
  153. {
  154.     if (root == NULL) return 0;	  //空树
  155.     else 
  156.        return 1+Size(root->leftChild)+Size(root->rightChild);
  157. }
  158.  
  159. //空树高度为0
  160. template <class T>
  161. int  BinaryTree<T>::Height(BinTreeNode<T> * root) 
  162. {
  163.      if (root == NULL) return 0;	
  164.      else 
  165. 	 {     
  166. 	  int i = Height(root->leftChild);
  167.       int j = Height(root->rightChild);
  168. 	  return (i < j) ? j+1 : i+1; 
  169. 	}
  170. }
  171.  
  172. //二叉树复制 
  173. template <class T>
  174. BinTreeNode<T> * BinaryTree<T>::CopyTree( BinTreeNode<T> *orignode) 
  175. {
  176.     if(orignode==NULL)  return NULL;
  177.     BinTreeNode<T> *temp=new BinTreeNode<T>;
  178.     temp->data=orignode->data;
  179.     temp->leftChild=CopyTree(orignode->leftChild);
  180.     temp->rightChild=CopyTree(orignode->rightChild);
  181.     return temp;
  182. }
  183.  
  184. //寻找双亲结点 
  185. template <class T>
  186. BinTreeNode<T> *BinaryTree<T>::
  187. Parent (BinTreeNode <T> *subTree,BinTreeNode <T> *t)
  188. {
  189.      if (subTree == NULL) return NULL;
  190.      if (subTree->leftChild == t ||subTree->rightChild == t)
  191. 	  return subTree;	//找到, 返回父结点地址
  192.      BinTreeNode <T> *p;
  193.      if ((p = Parent (subTree->leftChild, t)) != NULL)  
  194.          return p;	         //递归在左子树中搜索
  195.          else return Parent (subTree->rightChild, t);
  196.  				         //递归在右子树中搜索
  197. }
  198.  
  199.  
  200. //查找结点数据 
  201. template<class T>
  202. BinTreeNode<T> *BinaryTree<T>::getData(T& item,BinTreeNode<T> * root)
  203. {
  204. 	if(root==NULL)return NULL;
  205. 	if(root->data==item)return root;
  206. 	return getData(item,root->leftChild)!=NULL?getData(item,root->leftChild):getData(item,root->rightChild);
  207.   
  208. } 
  209.  
  210. //查找结点是否在树中
  211. template<class T>
  212. bool BinaryTree<T>::Find (T& item,BinTreeNode<T> * root)
  213. {
  214. 	if(this->getData(item,root)==NULL)return false;
  215. 	else return true; 
  216. } 
  217.  
  218.  
  219. //销毁二叉树 
  220. template<class T>
  221. void BinaryTree<T>::destroy (BinTreeNode<T>* subTree) {
  222. //私有函数: 后序遍历删除根为subTree的子树；
  223.      if (subTree != NULL) {
  224.           destroy (subTree->leftChild);     //删除左子树
  225.  	      destroy (subTree->rightChild);   //删除右子树
  226.  	      delete subTree; 			 //删除根结点
  227. 	 }
  228. }
  229.  
  230.  
  231. //BinTreeNode<char> *root;
  232. int main()
  233. {
  234. 	
  235. 	char ch;
  236. 	cout<<"输入结束标志：";
  237. 	 cin>>ch;
  238.     BinaryTree<char> t(ch);
  239. //	 cout<<"输入遍历序列：";
  240. //	string a;
  241. //	cin>>a;
  242. //	int l=a.length();
  243. //	int i=0;	
  244. 	BinTreeNode<char>* head=t.getRoot();
  245. 	t.CreatTree(head);
  246.  
  247. 	return 0;
  248.  }

七、总结

点个赞再走吧~~

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

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

  

闽ICP备14008679号