定义：二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
特点：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^(i-1)个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树，如果其终端结点(即叶子节点)数为n0，度为2的结点数为n2，则n0=n2+1。
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，即节点总数为2^k-1 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边
template<class T> //创建节点 struct BinaryTreeNode { public: BinaryTreeNode(const T& value) :_value(value) ,_pLeft(NULL) ,_pRight(NULL) {} T _value; BinaryTreeNode<T>* _pLeft; BinaryTreeNode<T>* _pRight; };
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) //拷贝构造函数 { cout<<endl<<"CopyBinaryTree"<<endl; _pRoot=_CopyBinaryTree(bt._pRoot); } BinaryTree& operator=(const BinaryTree<T>& bt) //赋值运算符重载 { if(this!=&bt) { _DestroyBinaryTree(_pRoot); _pRoot=_CopyBinaryTree(bt._pRoot); } return *this; } ~BinaryTree() //析构函数 { _DestroyBinaryTree(_pRoot); }
void _CreateBinaryTree(Node* &pRoot,const T array[],size_t size,size_t & index,const T& invalid) //构造二叉树 { if(index<size && array[index]!=invalid) // 得到的字符为无效值时，不处理 { pRoot=new Node(array[index]); _CreateBinaryTree(pRoot->_pLeft,array,size,++index,invalid); _CreateBinaryTree(pRoot->_pRight,array,size,++index,invalid); } } Node* _CopyBinaryTree(Node* pRoot) //拷贝二叉树 { Node* pNewNode=NULL; if(pRoot) { pNewNode=new Node(pRoot->_value); pNewNode->_pLeft=_CopyBinaryTree(pRoot->_pLeft); pNewNode->_pRight=_CopyBinaryTree(pRoot->_pRight); } return pNewNode; //返回根节点 } void _DestroyBinaryTree(Node*& pRoot) //销毁二叉树 { if(pRoot) { _DestroyBinaryTree(pRoot->_pLeft); _DestroyBinaryTree(pRoot->_pRight); //先销毁左右子树 delete pRoot; //再销毁根节点 pRoot=NULL; //根节点置空 } }
//二叉树的基本构造就完成了 ——二叉树的常见操作 //前序遍历 public: void PerOrder() { cout<<"PerOrder:"; _PerOrder(_pRoot); cout<<endl; } private: void _PerOrder(Node* pRoot) { if(pRoot) { cout<<pRoot->_value<<" "; //访问根节点 _PerOrder(pRoot->_pLeft); //再左子树 _PerOrder(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<<" "; } }
—三种遍历的基本方法都相同，只访问的顺序不一样 — ——这三种遍历方式均为递归遍历 //找特定值的节点 public: Node* Find(const T& value) //包装Find方法 { return _Find(_pRoot,value); } private: Node* _Find(Node* pRoot,const T& value) { if(NULL==pRoot) //树空---NULL return NULL; if(pRoot->_value == value) //根节点就是要找的节点 return pRoot; Node* pCur=NULL; if(pCur=_Find(pRoot->_pLeft,value)) //左子树中找 return pCur; if(_Find(pRoot->_pRight,value)) //右子树中找 return pCur; //返回pCur } //找某个节点的父节点 public: Node* Find(const T& value) { return _Find(_pRoot,value); } 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; if(_Find(pRoot->_pRight,value)) return pCur; } //树的高度 size_t _Height(Node* pRoot)// NULL -> 0 一个节点->1 多个节点->左、右子树 { if(NULL==pRoot) return 0; if(NULL==pRoot->_pLeft && NULL==pRoot->_pRight) return 1; size_t LeftHeight=_Height(pRoot->_pLeft); size_t RightHeight=_Height(pRoot->_pRight); return (LeftHeight>RightHeight)? LeftHeight+1:RightHeight+1; } //叶子节点的个数 size_t _GetLeefCount(Node* pRoot) { if(NULL==pRoot) return 0; if(NULL==pRoot->_pLeft && NULL==pRoot->_pRight) return 1; size_t LeftLeefCount=_GetLeefCount(pRoot->_pLeft); size_t RightLeefCount=_GetLeefCount(pRoot->_pRight); return LeftLeefCount+RightLeefCount; } //第K层叶子节点的个数 size_t _GetKLevelCount(Node* pRoot,size_t k) { if(NULL==pRoot || k<1) return 0; if(1==k) return 1; return _GetKLevelCount(pRoot->_pLeft,k-1)+_GetKLevelCount(pRoot->_pRight,k-1); //左子树上K-1层叶子节点的个数+右子树上K-1层叶子节点的个数 } //二叉树的镜像树-------左右子树颠倒 void _BinaryMirror(Node* pRoot) { if(pRoot) { std::swap(pRoot->_pLeft,pRoot->_pRight); //交换左右子树 _BinaryMirror(pRoot->_pLeft); //对左子树进行镜像处理 _BinaryMirror(pRoot->_pRight); //对右子树进行镜像处理 } } ——非递归的三种遍历方式 //前序遍历 void PerOrder_Nor() { cout<<"PerOrder_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 InOrder_Nor() { cout<<"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(); pCur=pCur->_pRight; } cout<<endl; } //后序遍历 void PostOrder_Nor() { cout<<"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 || pTop->_pRight==prev) { cout<<pTop->_value<<" "; prev=pTop; s.pop(); } else pCur=pTop->_pRight; } } ok，就这样，完成了 void _InOrder(Node* pRoot) { if(pRoot) { _InOrder(pRoot->_pLeft); cout<<pRoot->_value<<" "; _InOrder(pRoot->_pRight); } }