本人刚学数据结构,对树的基本功能网上找不到C++代码
便自己写了一份,贴出方便大家进行测试和学习。
大部分功能未测试,如有错误或者BUG,请高手们指教一下,谢谢。
结点声明:
BinTreeNode.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 template<typename ElemType> 2 struct BinTreeNode 3 { 4 ElemType data; //数据元素 5 BinTreeNode<ElemType> *leftChild; //指向左孩子的指针 6 BinTreeNode<ElemType> *rightChild; //指向右孩子的指针 7 BinTreeNode<ElemType> *pre; //指向双亲的指针 8 9 //函数构造 10 BinTreeNode(); 11 BinTreeNode(const ElemType &val, 12 BinTreeNode<ElemType> *lChild=NULL, 13 BinTreeNode<ElemType> *rChild=NULL); 14 BinTreeNode<ElemType> &operator =(const BinTreeNode<ElemType> ©); 15 }; 16 17 template<typename ElemType> 18 BinTreeNode<ElemType>::BinTreeNode() 19 { 20 leftChild=rightChild=pre=NULL; 21 } 22 23 template<typename ElemType> 24 BinTreeNode<ElemType>::BinTreeNode(const ElemType &val, 25 BinTreeNode<ElemType> *lChild, 26 BinTreeNode<ElemType> *rChild) 27 { 28 data=val; 29 leftChild=lChild; 30 rightChild=rChild; 31 pre=NULL; 32 } 33 34 template<typename ElemType> 35 BinTreeNode<ElemType> &BinTreeNode<ElemType>::operator =(const BinTreeNode<ElemType> ©) 36 { 37 data=copy.data; 38 leftChild=copy.leftChild; 39 rightChild=copy.leftChild; 40 pre=copy.pre; 41 }
类声明:
BinaryTree.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include"BinTreeNode.h" 2 template<typename ElemType> 3 class BinaryTree 4 { 5 protected: 6 //数据成员 7 BinTreeNode<ElemType> *root; 8 //辅助函数 9 void CreateBTreeHelp(BinTreeNode<ElemType> *&r,ElemType pre[],ElemType in[],int,int,int,int);//构造树 10 BinTreeNode<ElemType> *CopyTreeHelp(const BinTreeNode<ElemType> *r);//复制二叉树 11 void DestroyHelp(BinTreeNode<ElemType> *&r);//销毁r为根的二叉树 12 //先,中,后序遍历 13 void PreOrderHelp (const BinTreeNode<ElemType> *r,void (*visit) (const ElemType &))const; 14 void InOrderHelp (const BinTreeNode<ElemType> *r,void (*visit) (const ElemType &))const; 15 void PostOrderHelp(const BinTreeNode<ElemType> *r,void (*visit) (const ElemType &))const; 16 17 int HeightHelp(const BinTreeNode<ElemType> *r) const;//返回树的高度 18 int NodeCountHelp(const BinTreeNode<ElemType> *r)const;//返回树的节点个数 19 20 public: 21 BinaryTree(){root=NULL}//无参构造 22 BinaryTree(const ElemType &e);//建立以e元素为根的二叉树 23 BinaryTree(BinTreeNode<ElemType> *r);//建立以r为根的二叉树 24 virtual ~BinaryTree();//有指针用虚虚构 25 BinaryTree<ElemType> &CreateBTree(ElemType pre[],ElemType in[],int n); //构造树 26 BinTreeNode<ElemType> *GetRoot() const;//返回根 27 bool Empty()const; 28 bool GetElem(const BinTreeNode<ElemType> *cur,ElemType &e);//用e结点返回cur元素值 29 bool SetTlem(const BinTreeNode<ElemType> *cur,const ElemType &e);//e赋值给cur 30 //先,中,后序遍历 31 void PreOrder(void (*visit) (const ElemType &))const; 32 void InOrder(void (*visit) (const ElemType &))const; 33 void PostOrder(void (*visit) (const ElemType &))const; 34 //层次遍历 35 void LevelOrder(void (*visit) (const ElemType &))const; 36 int NodeCount()const; 37 BinTreeNode<ElemType> *LeftChild(const BinTreeNode<ElemType> *cur)const;//返回cur左孩子 38 BinTreeNode<ElemType> *RightChild(const BinTreeNode<ElemType> *cur)const;//返回cur右孩子 39 BinTreeNode<ElemType> *Parent(const BinTreeNode<ElemType> *cur)const;//返回cur双亲 40 void InsertLeftChild(BinTreeNode<ElemType> *cur,const ElemType &e);//插入左孩子 41 void InsertRightChild(BinTreeNode<ElemType> *cur,const ElemType &e);//插入右孩子 42 void DeleteLeftChild(BinTreeNode<ElemType> *cur);//删除左子树 43 void DeleteRightChild(BinTreeNode<ElemType> *cur);//删除右子树 44 int Height()const;//求二叉树高 45 BinaryTree(const BinaryTree<ElemType> ©);//复制构造函数 46 BinaryTree<ElemType> &operator =(const BinaryTree<ElemType> ©);//重载赋值运算符 47 }; 48 #include"CreateBTree.h" 49 #include"Destroy,copy,operator.h" 50 #include"height.h" 51 #include"NodeCount.h" 52 #include"return,set.h" 53 #include"Traversal.h"
成员函数:
CreateBTree.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 template<typename ElemType> 2 void BinaryTree<ElemType>::CreateBTreeHelp(BinTreeNode<ElemType> *&r, 3 ElemType pre[],ElemType in[], 4 int preLeft,int preRight,int inLeft,int inRight) 5 6 { 7 if(preLeft>preRight||inLeft>inRight) 8 r=NULL; 9 else 10 { 11 r=new BinTreeNode<ElemType>(pre[preLeft]);//生成根结点 12 int mid=inLeft; 13 while(in[mid]!=pre[preLeft]) 14 mid++; 15 CreateBTreeHelp(r->leftChild,pre,in,preLeft+1,preLeft+mid-inLeft,inLeft,mid-1); 16 CreateBTreeHelp(r->rightChild,pre,in,preLeft+mid-inLeft+1,preRight,mid+1,inRight); 17 } 18 } 19 20 template<typename ElemType> 21 //构造树 22 BinaryTree<ElemType>& BinaryTree<ElemType>::CreateBTree(ElemType pre[],ElemType in[],int n) 23 { 24 BinTreeNode<ElemType> *r; //根 25 CreateBTreeHelp(r,pre,in,0,n-1,0,n-1); 26 //return BinaryTree<ElemType>(r);//Error:不应该返回局部变量的地址 27 *this = BinaryTree<ElemType>(r); 28 return *this; 29 }
Destroy,copy,operator.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //Destroy 2 template<typename ElemType> 3 void BinaryTree<ElemType>::DestroyHelp(BinTreeNode<ElemType> *&r) 4 { 5 if(r!=NULL) 6 { 7 DestroyHelp(r->leftChild); 8 DestroyHelp(r->rightChild); 9 delete r; 10 r=NULL; 11 } 12 } 13 template<typename ElemType> 14 //删除左子树 15 void BinaryTree<ElemType>::DeleteLeftChild(BinTreeNode<ElemType> *cur) 16 { 17 DestroyHelp(cur->leftChild); 18 } 19 template<typename ElemType> 20 //删除右子树 21 void BinaryTree<ElemType>::DeleteRightChild(BinTreeNode<ElemType> *cur) 22 { 23 DestroyHelp(cur->rightChild); 24 } 25 //虚构 26 template<typename ElemType> 27 BinaryTree<ElemType>::~BinaryTree() 28 { 29 DestroyHelp(root); 30 } 31 32 //Copy 33 template<typename ElemType> 34 BinTreeNode<ElemType> *BinaryTree<ElemType>::CopyTreeHelp(const BinTreeNode<ElemType> *r) 35 { 36 BinTreeNode<ElemType> *cur; 37 if(r==NULL) cur=NULL; 38 else 39 { 40 BinTreeNode<ElemType> *lChild=CopyTreeHelp(r->leftChild);//复制左子树 41 BinTreeNode<ElemType> *rChild=CopyTreeHelp(r->rightChild);//复制右子树 42 cur=new BinTreeNode<ElemType>(r->data,lChild,rChild); 43 //复制根节点 44 } 45 return cur; 46 } 47 template<typename ElemType> 48 BinaryTree<ElemType>::BinaryTree(const BinaryTree<ElemType> ©) 49 { 50 root=CopyTreeHelp(copy.root) 51 } 52 53 //operator = 54 template<typename ElemType> 55 BinaryTree<ElemType> &BinaryTree<ElemType>::operator=(const BinaryTree<ElemType> ©) 56 { 57 if(©!=this) 58 { 59 DestroyHelp(root); 60 root=CopyTreeHelp(copy.root); 61 } 62 return *this; 63 }
height.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 template<typename ElemType> 2 int BinaryTree<ElemType>::HeightHelp(const BinTreeNode<ElemType> *r) const 3 { 4 if(r==NULL) return 0; 5 else 6 { 7 int lHeight,rHeight,height; 8 lHeight=HeightHelp(r->leftChild); 9 rHeight=HeightHelp(r->rightChild); 10 height-1=lHeight>rHeight?lHeight:rHeight;//深度为左右子树最大值加1; 11 return height; 12 } 13 14 }
NodeCount.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 template<class ElemType> 2 int BinaryTree<ElemType>::NodeCountHelp(const BinTreeNode<ElemType> *r) const 3 { 4 int count; 5 if (r == NULL) 6 count=0; 7 else 8 { 9 count = NodeCountHelp(r->leftChild) + NodeCountHelp(r->rightChild) + 1; 10 //左孩子加右孩子结点数再加根节点。 11 } 12 return count; 13 } 14 template<class ElemType> 15 int BinaryTree<ElemType>::NodeCount() const 16 { 17 return NodeCountHelp(root); 18 }
return,set.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
template<typename ElemType> //返回根 BinTreeNode<ElemType> *BinaryTree<ElemType>::GetRoot() const { return root; } template<typename ElemType> //用e结点返回cur元素值 bool BinaryTree<ElemType>::GetElem(const BinTreeNode<ElemType> *cur, ElemType &e) { if(cur) { e = cur->data; return true } else return false; } template<typename ElemType> //e赋值给cur bool BinaryTree<ElemType>::SetTlem(const BinTreeNode<ElemType> *cur, const ElemType &e) { if(cur) { cur->data = e; return true; } else return false; } template<typename ElemType> //返回cur左孩子 BinTreeNode<ElemType> *BinaryTree<ElemType>::LeftChild(const BinTreeNode<ElemType> *cur)const { if(cur->leftChild) return cur->leftChild; else return NULL; } template<typename ElemType> //返回cur右孩子 BinTreeNode<ElemType> *BinaryTree<ElemType>::RightChild(const BinTreeNode<ElemType> *cur)const { if(cur->RightChild) return cur->RightChild; else return NULL; } template<typename ElemType> //插入左孩子 void BinaryTree<ElemType>::InsertLeftChild(BinTreeNode<ElemType> *cur,const ElemType &e)//插入左孩子 { if(!(cur->leftChild)) cur->leftChild = new BinTreeNode<ElemType>(e); else throw "左孩子已存在!插入失败."; } template<typename ElemType> //插入右孩子 void BinaryTree<ElemType>::InsertRightChild(BinTreeNode<ElemType> *cur,const ElemType &e)//插入右孩子 { if(!(cur->rightChild)) cur->rightChild = new BinTreeNode<ElemType>(e); else throw "右孩子已存在!插入失败."; } template<typename ElemType> //返回cur的双亲 BinTreeNode<ElemType> *BinaryTree<ElemType>::Parent(const BinTreeNode<ElemType> *cur)const { if(cur->pre != NULL) return cur->pre; else return NULL; } template<typename ElemType> //建立以r为根的二叉树 BinaryTree<ElemType>::BinaryTree(BinTreeNode<ElemType> *r) { root = r; } template<typename ElemType> //建立以e元素为根的二叉树 BinaryTree<ElemType>::BinaryTree(const ElemType &e)//建立以e元素为根的二叉树 { root = new BinTreeNode(e); } template<typename ElemType> //判断树空 bool BinaryTree<ElemType>::Empty() const { return root == NULL; }
Traversal.h
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //recursion algorithm 2 template<typename ElemType> 3 void BinaryTree<ElemType>::PreOrderHelp(const BinTreeNode<ElemType> *r, 4 void (*visit) (const ElemType &))const 5 { 6 if(r!=NULL) 7 { 8 visit(r->data); 9 PreOrderHelp(r->leftChild,visit); 10 PreOrderHelp(r->rightChild,visit); 11 } 12 } 13 14 15 16 template<typename ElemType> 17 void BinaryTree<ElemType>::InOrderHelp(const BinTreeNode<ElemType> *r, 18 void (*visit) (const ElemType &))const 19 { 20 if(r!=NULL) 21 { 22 InOrderHelp(r->leftChild,visit); 23 visit(r->data); 24 InOrderHelp(r->rightChild,visit); 25 } 26 } 27 28 29 30 template<typename ElemType> 31 void BinaryTree<ElemType>::PostOrderHelp(const BinTreeNode<ElemType> *r, 32 void (*visit) (const ElemType &))const 33 { 34 if(r!=NULL) 35 { 36 PostOrderHelp(r->leftChild,visit); 37 PostOrderHelp(r->rightChild,visit); 38 visit(r->data); 39 } 40 } 41 42 using namespace std; 43 template<typename ElemType> 44 void print(const ElemType &e ) 45 { 46 cout<<e<<" "; 47 } 48 #include<queue> 49 template<typename ElemType> 50 void BinaryTree<ElemType>::LevelOrder(void (*visit) (const ElemType &))const 51 { //队列实现 52 visit=print; 53 queue<BinTreeNode<ElemType> *> q; 54 BinTreeNode<ElemType> *t=GetRoot(); 55 if(t!=NULL) q.push(t); //根非空,入队 56 while(!q.empty()) //队不空 57 { 58 t=q.front(); 59 q.pop(); //出队 60 (*visit)(t->data); 61 if(t->leftChild) 62 q.push(t->leftChild); //遍历左孩子 63 if(t->rightChild) 64 q.push(t->rightChild); //遍历右孩子 65 } 66 67 } 68 69 /* 70 //非递归先序遍历 71 #include<stack> 72 using namespace std; 73 template<typename ElemType> 74 void NonRecurPreOrder(const BinaryTree<ElemType> &bt, 75 void (*visit) (const ElemType &))const 76 { 77 BinTreeNode<ElemType> *cur=bt.GetRoot();//当前结点 78 stack<ElemType> s; 79 while(cur)//cur不空 80 { 81 (*visit)(cur->data);//访问cur元素 82 if(cur->leftChild) //左孩子不空 83 { if(cur->rightChild) //右孩子也不空 84 s.push(cur); //入栈(若右孩子空无须入栈) 85 } 86 else 87 { 88 if(cur->rightChild) //左孩子空,右孩子不空(不入栈) 89 cur=cur->rightChild; 90 else if(!s.empty()) //左右孩子都空,栈不空 91 { 92 cur=s.top(); //取出栈,退返。 93 s.pop(); //出栈 94 } 95 else //栈空 96 cur=NULL;//结束循环 97 } 98 } 99 } 100 */ 101 /* 102 //非递归中序遍历 103 template<typename ElemType> 104 BinTreeNode<ElemType> *GoFarLeft(BinTreeNode<ElemType> *r, 105 stack<ElemType> &s) 106 { 107 if(r==NULL) //结点空 108 return NULL; 109 BinTreeNode<ElemType> *cur=r; 110 while(cur->leftChild) //往左走 111 { 112 s.push(); //左孩子进栈 113 cur=cur->leftChild; 114 } 115 return cur; 116 } 117 118 template<typename ElemType> 119 void NonRecurInOrder(const BinaryTree<ElemType> &bt, 120 void (*visit) (const ElemType &))const 121 { 122 BinTreeNode<ElemType> *cur=bt.GetRoot(); //cur指向根节点 123 stack<ElemType> s; 124 cur=GoFarLeft(cur,s); //走到最底层 125 while(cur) 126 { 127 (*visit)(cur->data); 128 if(cur->rightChild) //右孩子不空 129 cur=GoFarLeft(cur->rightChild,s); //遍历右孩子 130 else if(!s.empty()) //右孩子空,取栈 131 { cur=s.top(); s.pop();} 132 else //栈空 133 cur=NULL; 134 } 135 } 136 */ 137 138 139 template<typename ElemType> 140 void BinaryTree<ElemType>::PreOrder(void (*visit) (const ElemType &))const 141 { 142 PreOrderHelp(root,visit); 143 } 144 template<typename ElemType> 145 void BinaryTree<ElemType>::InOrder(void (*visit) (const ElemType &))const 146 { 147 InOrderHelp(root,visit); 148 } 149 template<typename ElemType> 150 void BinaryTree<ElemType>::PostOrder(void (*visit) (const ElemType &))const 151 { 152 PostOrderHelp(root,visit); 153 }
主函数:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include"BinaryTree.h" 3 using namespace std; 4 BinaryTree<char>; 5 int main() 6 { 7 char s1[1000], s2[1000]; 8 cin >> s1 >> s2; 9 int n = strlen(s1); 10 if(n != strlen(s2)) 11 cout << "ERROR "; 12 BinTreeNode<char> *root = NULL; 13 BinaryTree<char> T(root); 14 T.CreateBTree(s1, s2, n); 15 T.LevelOrder(print<char>); 16 cout<<endl; 17 T.PreOrder(print<char>); 18 cout<<endl; 19 T.InOrder(print<char>); 20 cout<<endl; 21 T.PostOrder(print<char>); 22 cout<<endl; 23 }
运行结果如下: