二叉树的基本操作及部分面试题

1.构造二叉树

#include<iostream> #include<queue> #include<stack> #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; } 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 _DestroyBinaryTree(Node* &pRoot) { if(pRoot) { _DestroyBinaryTree(pRoot->_pLeft); _DestroyBinaryTree(pRoot->_pRight); delete pRoot; pRoot=NULL; } } private: Node* _pRoot; };

2.二叉树的遍历—递归形式

public: 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; } private: 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<<" "; } }

3.二叉树的遍历—-非递归形式

public: void _PreOrder_Nor()//前序遍历(非递归)---方法一 { if(NULL==_pRoot) return; stack<Node*> s; s.push(_pRoot); while(!s.empty()) { Node* pTop=s.top(); cout<<pTop->_value<<" "; s.pop(); if(pTop->_pRight) s.push(pTop->_pRight); if(pTop->_pLeft) s.push(pTop->_pLeft); } cout<<endl; } void _PreOrder_Nor()//前序遍历(非递归)---方法二:左右结点都存在时，将右结点入栈，直接访问左结点 { if(NULL==_pRoot) return; stack<Node*> s; s.push(_pRoot); while(!s.empty()) { Node* pCur=s.top(); s.pop(); while(pCur) { cout<<pCur->_value<<" "; if(pCur->_pRight) s.push(pCur->_pRight); pCur=pCur->_pLeft; } } cout<<endl; } void _InOrder_Nor()//中序遍历(非递归) { if(NULL==_pRoot) return; stack<Node*> s; Node* pCur=_pRoot; while(pCur||!s.empty()) { while(pCur)//找最左边的结点，并保存路径上的每个结点 { s.push(pCur); pCur=pCur->_pLeft; } pCur=s.top(); cout<<pCur->_value<<" "; s.pop(); while(NULL==pCur->_pRight && !s.empty())//右子树不存在时 { pCur=s.top(); cout<<pCur->_value<<" "; s.pop(); } pCur=pCur->_pRight; } cout<<endl; } void _PostOrder_Nor()//后序遍历(非递归) { if(NULL==_pRoot) return; stack<Node*> s; Node* pCur=_pRoot; Node* prev=NULL; while(pCur||!s.empty()) { while(pCur)//找最左边的结点，并保存路径上的每个结点 { s.push(pCur); pCur=pCur->_pLeft; } Node* pTop=s.top(); if(NULL==pTop->_pRight||prev==pTop->_pRight)//右子树存在时，可能会被访问两次，造成死循环，所以要判断是否已经访问过 { cout<<pTop->_value<<" "; prev=pTop; s.pop(); } else pCur=pTop->_pRight; } cout<<endl; }

4.找二叉树中是否有某个节点

public: Node* Find(const T& value)//找二叉树中某个结点 { Node* pCur=NULL; pCur=_Find(_pRoot,value); cout<<pCur->_value<<endl; return pCur; } private: 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); }

4.获取双亲节点

public： Node* Parent(Node* pCur)//寻找双亲结点 { Node* result=NULL; result=_Parent(_pRoot,pCur); cout<<"Parent:"<<endl; cout<<result->_value<<endl; return result; } private： 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); }

5.获取左孩子节点

public: Node* LeftChild(Node* pCur)//寻找左孩子结点 { Node* result=NULL; result=_LeftChild(_pRoot,pCur); cout<<"LeftChild:"<<endl; cout<<result->_value<<endl; return result; } private： 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); }

6.获取右孩子节点

public: Node* RightChild(Node* pCur)//寻找右孩子结点 { Node* result=NULL; result=_RightChild(_pRoot,pCur); cout<<"RightChild:"<<endl; cout<<result->_value<<endl; return result; } private： 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); }

7.计算二叉树的深度

public: size_t Height()//计算二叉树的深度 { size_t depth=0; depth=_Height(_pRoot); cout<<"Height:"<<depth<<endl; return depth; } private： 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; }

8.计算二叉树的叶子节点个数

public: size_t GetLeefCount()//计算叶子结点个数 { size_t count=0; count=_GetLeefCount(_pRoot); cout<<"leefcount: "<<count<<endl; return count; } privte: 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); }

9.计算二叉树第k层的节点个数

public: size_t GetKLevelCount(size_t k)//计算二叉树第k层结点数 { size_t count=0; count=_GetKLevelCount(_pRoot, k); cout<<"KLevelCount: "<<count<<endl; return count; } private： 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); }

10.求二叉树的镜像树—-递归形式

public: void BinaryMirror()//求镜像树(递归) { _BinaryMirror(_pRoot); } private: void _BinaryMirror(Node* pRoot)//镜像树(递归) { if(pRoot) { std::swap(pRoot->_pLeft,pRoot->_pRight); _BinaryMirror(pRoot->_pLeft); _BinaryMirror(pRoot->_pRight); } }

11.求二叉树的镜像树—-非递归形式

public: 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(); } }

12.判断是否为完全二叉树

public： bool IsCompleteBinaryTree()//判断是否为完全二叉树? { if(NULL==_pRoot) return true; bool flag=false; queue<Node*> q; q.push(_pRoot); while(!q.empty()) { Node* pCur=q.front(); if(flag)//判断到此处时，说明pCur已经指向一棵右子树 { if(pCur->_pLeft||pCur->_pRight) return false; } if(pCur->_pLeft && pCur->_pRight) { q.push(pCur->_pLeft); q.push(pCur->_pRight); } else if(pCur->_pLeft) { q.push(pCur->_pLeft); flag=true; } else if(pCur->_pRight) return false; else flag=true; q.pop(); } return true; }

13.根据前序遍历和中序遍历的结果重建二叉树

public: Node* ReBuild_PreIn(T Pre[],int start_Pre,int end_Pre,T In[],int start_In,int end_In)//根据前序遍历和中序遍历的结果重建二叉树 { if((end_Pre-start_Pre)!=(end_In-start_In)||start_Pre>end_Pre) return NULL; Node* pCur=new Node(sizeof(Pre)); pCur->_value=Pre[start_Pre]; pCur->_pLeft=NULL; pCur->_pRight=NULL; if(start_Pre==end_Pre) return pCur; int index=0; int length=0; for(index=start_In;index<=end_In;index++) { if(In[index]==Pre[start_Pre]) break; } if(index>end_In) return NULL; if (index > start_In) { length = index-start_In; pCur->_pLeft= ReBuild_PreIn(Pre,start_Pre+1,start_Pre+1+length-1,In,start_In,start_In+length-1); } //有右子树，递归调用构建右子树 if (index < end_In) { length = end_In - index; pCur->_pRight= ReBuild_PreIn(Pre,end_Pre-length+1,end_Pre,In,end_In-length+1,end_In); } return pCur; }

14.求两个节点最近的公共祖先

public: void CommonAncestor(Node* node1,Node* node2) { //bool flag=false; cout<<(_CommonAncestor(_pRoot,node1,node2))->_value<<endl; } private： bool _GetPath(Node* pRoot,Node* pCur,stack<Node*>& s)//在根为pRoot的树中查找节点pCur的路径 { if (NULL == pRoot || NULL == pCur)//树为空 return false; s.push(pRoot); //将当前节点入栈 if (pCur->_value == pRoot->_value) //找到路径 { return true; } if (_GetPath(pRoot->_pLeft,pCur,s))//在左子树中找路径 { return true; } if (_GetPath(pRoot->_pRight,pCur,s))//在右子树中找路径 { return true; } s.pop(); return false; } Node* _CommonAncestor(Node*& pRoot,Node* n1,Node* n2)//求两个节点的最近公共祖先(时间复杂度：O(N)) { //树为空 if (NULL == pRoot) { return NULL; } stack<Node*> s1; stack<Node*> s2; //用栈s1和s2分别保存节点n1和节点n2的路径 _GetPath(pRoot,n1,s1); _GetPath(pRoot,n2,s2); //将多余的路径删除 while (s1.size() > s2.size()) { s1.pop(); } while(s1.size() < s2.size()) { s2.pop(); } //找s1与s2中不同的节点 while(s1.top() != s2.top()) { s1.pop(); s2.pop(); } return s1.top(); }

15.测试代码：

void Test() { char* pStr="124###35##6"; char* pStrs="124##5##3"; char* PreOrder="124356"; char* InOrder="421536"; BinaryTree<char> bt1(pStr,strlen(pStr),'#'); BinaryTree<char> bts(pStrs,strlen(pStrs),'#'); //bt1.ReBuild_PreIn(PreOrder,0,5,InOrder,0,5); bt1.CommonAncestor(bt1.Find('5'),bt1.Find('6')); //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(); //bt1._PreOrder_Nor(); //bt1._InOrder_Nor(); //bt1._PostOrder_Nor(); //cout<<bts.IsCompleteBinaryTree()<<endl; /*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; }