二叉树的基本操作--递归

1.创建结构体保存二叉树的节点，每个节点有值，左孩子，右孩子

template<class T> struct BinaryTreeNode { T _value; BinaryTreeNode<T>* _pLeft;//左孩子 BinaryTreeNode<T>* _pRight;//右孩子 BinaryTreeNode(const T& value) :_value(value) ,_pLeft(NULL) ,_pRight(NULL) {} };

2.构造函数及拷贝构造函数

BinaryTree() :_pRoot(NULL) {} BinaryTree(const T array[],size_t size,const T& invalid)//构造函数 { size_t index=0; _CreateBinaryTree(_pRoot,array,size,index,invalid); } BinaryTree(const BinaryTree<T>& bt)//拷贝构造函数 { _pRoot=_CopyBinaryTree(bt._pRoot); }

3.析构函数

~BinaryTree() { _DestroyBinaryTree(_pRoot); }

4.创建二叉树的函数

void _CreateBinaryTree(Node* &pRoot,const T array[],size_t size,size_t& index,const T& invalid) { if(index<size&&invalid!=array[index]) { pRoot=new Node(array[index]); _CreateBinaryTree(pRoot->_pLeft,array,size,++index,invalid);//创建左子树 _CreateBinaryTree(pRoot->_pRight,array,size,++index,invalid);//创建右子树 } }

5.拷贝函数

Node* _CopyBinaryTree(Node* pRoot)//拷贝 { Node* pNewRoot=NULL; if(pRoot) { //拷贝根节点 pNewRoot=new Node(pRoot->_value); //拷贝左子树 pNewRoot->_pLeft=_CopyBinaryTree(pRoot->_pLeft); //拷贝右子树 pNewRoot->_pRight=_CopyBinaryTree(pRoot->_pRight); } return pNewRoot; }

6.销毁函数

void _DestroyBinaryTree(Node* &pRoot) { if(pRoot) { _DestroyBinaryTree(pRoot->_pLeft); _DestroyBinaryTree(pRoot->_pRight); delete pRoot; pRoot=NULL; } }

7.二叉树的三种遍历

void _PreOrder(Node* pRoot)//前序遍历 { if(pRoot) { cout<<pRoot->_value<<" "; _PreOrder(pRoot->_pLeft); _PreOrder(pRoot->_pRight); } } void _InOrder(Node* pRoot)//中序遍历 { if(pRoot) { _InOrder(pRoot->_pLeft); cout<<pRoot->_value<<" "; _InOrder(pRoot->_pRight); } } void _PostOrder(Node* pRoot)//后序遍历 { if(pRoot) { _PostOrder(pRoot->_pLeft); _PostOrder(pRoot->_pRight); cout<<pRoot->_value<<" "; } }

8.二叉树的基本操作

Node* _Find(Node* pRoot,const T& value)//根据值寻找二叉树中的相应结点 { if(NULL==pRoot) return NULL; if(pRoot->_value==value) return pRoot; Node* pCur=NULL; if(pCur=_Find(pRoot->_pLeft,value)) return pCur; return _Find(pRoot->_pRight,value); } Node* _Parent(Node* pRoot,Node* pCur)//获取双亲,pRoot为根节点 { assert(pCur); if(pRoot==NULL||pCur==pRoot) return NULL; if((pCur==pRoot->_pLeft)||(pCur==pRoot->_pRight)) return pRoot; Node* ret=NULL; if(ret=_Parent(pRoot->_pLeft,pCur)) return ret; else return _Parent(pRoot->_pRight,pCur); } Node* _LeftChild(Node* pRoot,Node* pCur)//寻找左孩子 { assert(pCur); if(pRoot!=NULL && pCur->_pLeft!=NULL) return pCur->_pLeft; Node* ret=NULL; if(ret=_LeftChild(pRoot->_pLeft,pCur)) return ret; else return _LeftChild(pRoot->_pRight,pCur); } Node* _RightChild(Node* pRoot,Node* pCur)//寻找右孩子 { assert(pCur); if(pRoot!=NULL && pCur->_pRight!=NULL) return pCur->_pRight; Node* ret=NULL; if(ret=_RightChild(pRoot->_pLeft,pCur)) return ret; else return _RightChild(pRoot->_pRight,pCur); } size_t _Height(Node* pRoot)//计算二叉树的深度 { int hl=0; int hr=0; int max=0; if(pRoot!=NULL) { hl=_Height(pRoot->_pLeft); hr=_Height(pRoot->_pRight); max=hl>hr?hl:hr; return max+1; } else return 0; } size_t _GetLeefCount(Node* pRoot)//计算叶子结点的个数 { if(pRoot==NULL) return 0; if(NULL==pRoot->_pLeft && NULL==pRoot->_pRight) return 1; return _GetLeefCount(pRoot->_pLeft)+_GetLeefCount(pRoot->_pRight); } size_t _GetKLevelCount(Node* pRoot,size_t k)//计算K行的节点个数 { if(pRoot==NULL||k<1) return 0; if(k==1) return 1; return _GetKLevelCount(pRoot->_pLeft,k-1)+_GetKLevelCount(pRoot->_pRight,k-1); } void _BinaryMirror(Node* pRoot)//镜像树 { if(pRoot) { std::swap(pRoot->_pLeft,pRoot->_pRight); _BinaryMirror(pRoot->_pLeft); _BinaryMirror(pRoot->_pRight); } }

完整代码：

#include<iostream> #include<queue> #include<assert.h> using namespace std; template<class T> struct BinaryTreeNode { T _value; BinaryTreeNode<T>* _pLeft;//左孩子 BinaryTreeNode<T>* _pRight;//右孩子 BinaryTreeNode(const T& value) :_value(value) ,_pLeft(NULL) ,_pRight(NULL) {} }; template<class T> class BinaryTree { public: typedef BinaryTreeNode<T> Node; BinaryTree() :_pRoot(NULL) {} BinaryTree(const T array[],size_t size,const T& invalid)//构造函数 { size_t index=0; _CreateBinaryTree(_pRoot,array,size,index,invalid); } BinaryTree(const BinaryTree<T>& bt)//拷贝构造函数 { _pRoot=_CopyBinaryTree(bt._pRoot); } ~BinaryTree() { _DestroyBinaryTree(_pRoot); } BinaryTree<T>& operator=(const BinaryTree<T>& bt) { if(this!=&bt) { __DestroyBinaryTree(_pRoot); _pRoot=_CopyBinaryTree(bt._pRoot); } return *this; } void PreOrder()//前序遍历 { cout<<"PreOrder:"<<endl; _PreOrder(_pRoot); cout<<endl; } void InOrder()//中序遍历 { cout<<"InOrder:"<<endl; _InOrder(_pRoot); cout<<endl; } void PostOrder()//后序遍历 { cout<<"PostOrder:"<<endl; _PostOrder(_pRoot); cout<<endl; } void LevelOrder() { if(NULL==_pRoot) return; queue<Node*> q; q.push(_pRoot); cout<<"LevelOrder:"<<endl; while(!q.empty())//队列不为空 { Node* pCur=q.front();//取队头元素 if(pCur->_pLeft) q.push(pCur->_pLeft);//取左子树 if(pCur->_pRight) q.push(pCur->_pRight);//取右子树 cout<<pCur->_value<<" ";//访问队头 q.pop();//出队列 } cout<<endl; } Node* Find(const T& value)//找二叉树中某个结点 { Node* pCur=NULL; pCur=_Find(_pRoot,value); cout<<pCur->_value<<endl; return pCur; } Node* Parent(Node* pCur)//寻找双亲结点 { Node* result=NULL; result=_Parent(_pRoot,pCur); cout<<"Parent:"<<endl; cout<<result->_value<<endl; return result; } Node* LeftChild(Node* pCur)//寻找左孩子结点 { Node* result=NULL; result=_LeftChild(_pRoot,pCur); cout<<"LeftChild:"<<endl; cout<<result->_value<<endl; return result; } Node* RightChild(Node* pCur)//寻找右孩子结点 { Node* result=NULL; result=_RightChild(_pRoot,pCur); cout<<"RightChild:"<<endl; cout<<result->_value<<endl; return result; } size_t Height()//计算二叉树的深度 { size_t depth=0; depth=_Height(_pRoot); cout<<"Height:"<<depth<<endl; return depth; } size_t GetLeefCount() { size_t count=0; count=_GetLeefCount(_pRoot); cout<<"leefcount: "<<count<<endl; return count; } size_t GetKLevelCount(size_t k) { size_t count=0; count=_GetKLevelCount(_pRoot, k); cout<<"KLevelCount: "<<count<<endl; return count; } void BinaryMirror_Nor() { if(NULL==_pRoot) return; queue<Node*> q; q.push(_pRoot); while(!q.empty()) { Node* pCur=q.front(); if(pCur->_pLeft) q.push(pCur->_pLeft); if(pCur->_pRight) q.push(pCur->_pRight); std::swap(pCur->_pLeft,pCur->_pRight); q.pop(); } } void BinaryMirror() { _BinaryMirror(_pRoot); } private: void _CreateBinaryTree(Node* &pRoot,const T array[],size_t size,size_t& index,const T& invalid) { if(index<size&&invalid!=array[index]) { pRoot=new Node(array[index]); _CreateBinaryTree(pRoot->_pLeft,array,size,++index,invalid);//创建左子树 _CreateBinaryTree(pRoot->_pRight,array,size,++index,invalid);//创建右子树 } } Node* _CopyBinaryTree(Node* pRoot)//拷贝 { Node* pNewRoot=NULL; if(pRoot) { //拷贝根节点 pNewRoot=new Node(pRoot->_value); //拷贝左子树 pNewRoot->_pLeft=_CopyBinaryTree(pRoot->_pLeft); //拷贝右子树 pNewRoot->_pRight=_CopyBinaryTree(pRoot->_pRight); } return pNewRoot; } void _PreOrder(Node* pRoot)//前序遍历 { if(pRoot) { cout<<pRoot->_value<<" "; _PreOrder(pRoot->_pLeft); _PreOrder(pRoot->_pRight); } } void _InOrder(Node* pRoot)//中序遍历 { if(pRoot) { _InOrder(pRoot->_pLeft); cout<<pRoot->_value<<" "; _InOrder(pRoot->_pRight); } } void _PostOrder(Node* pRoot)//后序遍历 { if(pRoot) { _PostOrder(pRoot->_pLeft); _PostOrder(pRoot->_pRight); cout<<pRoot->_value<<" "; } } void _DestroyBinaryTree(Node* &pRoot) { if(pRoot) { _DestroyBinaryTree(pRoot->_pLeft); _DestroyBinaryTree(pRoot->_pRight); delete pRoot; pRoot=NULL; } } Node* _Find(Node* pRoot,const T& value)//根据值寻找二叉树中的相应结点 { if(NULL==pRoot) return NULL; if(pRoot->_value==value) return pRoot; Node* pCur=NULL; if(pCur=_Find(pRoot->_pLeft,value)) return pCur; return _Find(pRoot->_pRight,value); } Node* _Parent(Node* pRoot,Node* pCur)//获取双亲,pRoot为根节点 { assert(pCur); if(pRoot==NULL||pCur==pRoot) return NULL; if((pCur==pRoot->_pLeft)||(pCur==pRoot->_pRight)) return pRoot; Node* ret=NULL; if(ret=_Parent(pRoot->_pLeft,pCur)) return ret; else return _Parent(pRoot->_pRight,pCur); } Node* _LeftChild(Node* pRoot,Node* pCur) { assert(pCur); if(pRoot!=NULL && pCur->_pLeft!=NULL) return pCur->_pLeft; Node* ret=NULL; if(ret=_LeftChild(pRoot->_pLeft,pCur)) return ret; else return _LeftChild(pRoot->_pRight,pCur); } Node* _RightChild(Node* pRoot,Node* pCur) { assert(pCur); if(pRoot!=NULL && pCur->_pRight!=NULL) return pCur->_pRight; Node* ret=NULL; if(ret=_RightChild(pRoot->_pLeft,pCur)) return ret; else return _RightChild(pRoot->_pRight,pCur); } size_t _Height(Node* pRoot)//计算二叉树的深度 { int hl=0; int hr=0; int max=0; if(pRoot!=NULL) { hl=_Height(pRoot->_pLeft); hr=_Height(pRoot->_pRight); max=hl>hr?hl:hr; return max+1; } else return 0; } size_t _GetLeefCount(Node* pRoot) { if(pRoot==NULL) return 0; if(NULL==pRoot->_pLeft && NULL==pRoot->_pRight) return 1; return _GetLeefCount(pRoot->_pLeft)+_GetLeefCount(pRoot->_pRight); } size_t _GetKLevelCount(Node* pRoot,size_t k) { if(pRoot==NULL||k<1) return 0; if(k==1) return 1; return _GetKLevelCount(pRoot->_pLeft,k-1)+_GetKLevelCount(pRoot->_pRight,k-1); } void _BinaryMirror(Node* pRoot) { if(pRoot) { std::swap(pRoot->_pLeft,pRoot->_pRight); _BinaryMirror(pRoot->_pLeft); _BinaryMirror(pRoot->_pRight); } } private: Node* _pRoot; }; void Test() { char* pStr="124###35##6"; BinaryTree<char> bt1(pStr,strlen(pStr),'#'); bt1.PreOrder(); bt1.InOrder(); bt1.PostOrder(); //bt1.LevelOrder(); //bt1.Find('5'); //bt1.Parent(bt1.Find('5')); //bt1.LeftChild(bt1.Find('1')); //bt1.RightChild(bt1.Find('1')); //bt1.Height(); //bt1.GetLeefCount(); //bt1.GetKLevelCount(4); //bt1.BinaryMirror_Nor(); bt1.BinaryMirror(); /*cout<<endl; BinaryTree<char> bt2(bt1); bt2.PreOrder(); bt2.InOrder(); bt2.PostOrder(); cout<<endl; BinaryTree<char> bt3=bt1; bt3.PreOrder(); bt3.InOrder(); bt3.PostOrder();*/ } int main() { Test(); return 0; }