二叉树的实现及相关函数的实现

#include <iostream> #include <queue> #include <stack> using namespace std; template<typename T> struct BinaryNode //__默认构造函数__ { BinaryNode() : _pData(0) , _pLeftChild(NULL) , _pRightChild(NULL) {} T _pData;//__值域__ BinaryNode<T>* _pLeftChild;//__左孩子__ BinaryNode<T>* _pRightChild;//__ 右孩子__ typedef BinaryNode<T> Node; }; template<typename T> class BinartyTree { typedef BinaryNode<T> Node; public: BinartyTree()//__默认构造函数__ {} BinartyTree(const T* arr, int size, T& invalid)//__带有参数的构造函数__ :_invalid(invalid) { int index = 0; CreatBinTree(_pRoot, arr, size, _invalid, index); } BinartyTree(const BinartyTree<T>& bt)//__拷贝构造函数__ { Destroy(_pRoot); _invalid = bt._invalid; Copy(_pRoot, bt._pRoot, _invalid); } ~BinartyTree()//__析构函数__ { Destroy(_pRoot); } void FrontOrder()//递归前序遍历，但因为需要传参，所以用C语言再次进行封装 { cout << "FrontOrder:" << " "; _FrontOrder(_pRoot); cout << endl << endl; } void FrontOrder_Nor()//非递归前序遍历 { if (NULL == _pRoot) return; cout << "FrontOrder_Nor: "; stack<Node*> s;//使用栈 s.push(_pRoot); while (!s.empty()) { Node* tmp = s.top();//取栈顶元素并访问 cout << tmp->_pData << " "; s.pop(); if (tmp->_pRightChild)//如果右孩子存在，则入栈右孩子，因为栈的性质， //所以右孩子先入后出，即先访问左孩子，符合前序原则 s.push(tmp->_pRightChild); if (tmp->_pLeftChild)//如果左孩子存在，则入栈左孩子 s.push(tmp->_pLeftChild); } cout << endl << endl; } void InOrder()//递归中序遍历，但因为需要传参，所以用C语言再次进行封装 { cout << "InOrder:" << " "; _InOrder(_pRoot); cout << endl << endl; } void InOrder_Nor()//非递归中序遍历 { if (NULL == _pRoot) return; cout << "InOrder_Nor: "; stack<Node*> s;//使用栈 Node* temp = _pRoot; while (temp || !s.empty())//因为一开始栈为空，所以加上temp的判断条件 { while (temp)//让节点一直沿着左子树走，直到尽头 { s.push(temp); temp = temp->_pLeftChild; } temp = s.top();//取栈顶元素，访问后出栈 s.pop(); cout << temp->_pData << " "; temp = temp->_pRightChild;//开始保存当前节点的右子树，并当做一个普通树进行上述方法保存 } cout << endl << endl; } void PostOrder()//递归后序遍历，但因为需要传参，所以用C语言再次进行封装 { cout << "PostOrder:" << " "; _PostOrder(_pRoot); cout << endl << endl; } void PostOrder_Nor()//非递归后序遍历 { if (NULL == _pRoot) return; cout << "PostOrder_Nor: "; struct Post { Node* BNode; bool flag; }; stack<Post*> s;//使用栈 Node* temp = _pRoot; while (temp || !s.empty()) { while (temp) { Post* p = (Post*)malloc(sizeof(Post)); p->BNode = temp;//将temp赋值给p中的节点 p->flag = true;//将p中的标志位置为true s.push(p);//入栈p temp = temp->_pLeftChild;//让表示节点的temp一直沿着左子树走，直到尽头 } if (!s.empty())//左子树走到尽头 { Post* p = s.top();//取栈顶元素 s.pop();//出栈 if (p->flag)//判断是不是第一次出栈 { p->flag = false;//是第一次出栈，但因为右子树还没有保存 s.push(p);//所以更改标志位后，继续入栈 if (p->BNode->_pRightChild)//如果这个节点存在右子树，那么按上述方法保存这个右子树 temp = p->BNode->_pRightChild; } else { cout << p->BNode->_pData << " ";//如果不是第一次出栈，证明右子树已经保存过了，则访问这个元素 } } } cout << endl << endl; } void LevelOrder()//层序遍历，但因为需要传参，所以用C语言再次进行封装 { cout << "LevelOrder: "; _LevelOrder(_pRoot); cout << endl << endl; } Node* GetParents(Node* child)//获取双亲结点，打印并返回地址，但因为需要传参，所以用C语言再次进行封装 { cout << child->_pData << "'s Parents is: "; cout << _GetParents(_pRoot, child)->_pData << endl << endl; return _GetParents(_pRoot, child); } Node* GetLeftChild(Node* parent)//获取左孩子结点，打印并返回地址，但因为需要传参，所以用C语言再次进行封装 { cout << parent->_pData << "'s LeftChild is: " << _GetLeftChild(_pRoot, parent)->_pData << endl << endl; return _GetLeftChild(_pRoot, parent); } Node* GetRightChild(Node* parent)//获取右孩子结点，打印并返回地址，但因为需要传参，所以用C语言再次进行封装 { cout << parent->_pData << "'s RightChild is: " << _GetRightChild(_pRoot, parent)->_pData << endl << endl; return _GetRightChild(_pRoot, parent); } size_t SumLeafNode()//获取叶子结点的个数，打印并返回数值，但因为需要传参，所以用C语言再次进行封装 { int count = 0; cout << "The Sum Of LeafNode Is: " << _SumLeafNode(_pRoot) << endl << endl; return _SumLeafNode(_pRoot); } Node* FindNode(T value)//判断该元素是否在树中，存在的话打印并返回地址，不存在返回NULL，同样用C语言进行封装 { cout << "The Address Of " << value << " Is: " << _FindNode(_pRoot, value) << "H" << endl << endl; return _FindNode(_pRoot, value); } size_t HightOfBinTree()//获取树的高度，打印并返回数值，但因为需要传参，所以用C语言再次进行封装 { cout << "The Hight Of This Binary Tree Is: " << _HightOfBinTree(_pRoot) << endl << endl; return _HightOfBinTree(_pRoot); } size_t GetKLevelCount(size_t k)//获取第K层结点的个数，打印并返回数值，但因为需要传参，所以用C语言再次进行封装 { cout << "The Hight Of "<< k << " has " << _GetKLevelCount(_pRoot, k) << " Node "<< endl << endl; return _GetKLevelCount(_pRoot, k); } void BinaryMirror()//递归创建二叉树的镜像树，但因为需要传参，所以用C语言再次进行封装 { _BinaryMirror(_pRoot); } void BinaryMirror_Nor()//非递归创建二叉树的镜像树 { if (NULL == _pRoot) return; queue<Node*> q;//使用队列 q.push(_pRoot); while (!q.empty()) { Node* temp = q.front(); q.pop(); //这里的入队顺序并没有要求，左先或右先都行，因为只是保证当前子树的当前层节点全部入队 if(temp->_pLeftChild)//入队左孩子，因为队的性质，该子树该层的节点的全部入队 q. push(temp->_pLeftChild); if(temp->_pRightChild) q.push(temp->_pRightChild); std::swap(temp->_pLeftChild, temp->_pRightChild);//入队完毕，则交换左右孩子 } } private: void CreatBinTree(Node*& pRoot, const T* arr, int size, T& invalid, int& index)//__创建树__ { if ((index < size) && (arr[index] != invalid)) { pRoot = new Node;//__先创建该子树的根节点__ pRoot->_pData = arr[index]; CreatBinTree(pRoot->_pLeftChild, arr, size, invalid, ++index);//__递归创建左孩子__ CreatBinTree(pRoot->_pRightChild, arr, size, invalid, ++index);//__递归创建右孩子__ } } void Copy(Node*& pRoot, Node* SrcNode, T& invalid)//__拷贝函数__ { if (SrcNode != NULL) { pRoot = new Node;//__先创建该子树的根节点__ pRoot->_pData = SrcNode->_pData; Copy(pRoot->_pLeftChild, SrcNode->_pLeftChild, invalid);//__递归创建左子树__ Copy(pRoot->_pRightChild, SrcNode->_pRightChild, invalid);//__递归创建右子树__ } } void Destroy(Node*& pRoot)//__销毁函数__ { if (pRoot != NULL) { Destroy(pRoot->_pLeftChild);//__递归找到最后一个左孩子销毁__ Destroy(pRoot->_pRightChild);//__递归找到最后一个右孩子销毁__ delete pRoot;//__销毁子树的根结点__ pRoot = NULL; } } void _FrontOrder(Node* pRoot)//递归前序遍历 { if (pRoot) { cout << pRoot->_pData << " ";//先访问根节点 _FrontOrder(pRoot->_pLeftChild);//再递归左子树 _FrontOrder(pRoot->_pRightChild);//再递归右子树 } } void _InOrder(Node* pRoot)//递归中序遍历 { if (pRoot) { _InOrder(pRoot->_pLeftChild);//递归左子树 cout << pRoot->_pData << " ";//访问根节点 _InOrder(pRoot->_pRightChild);//递归右子树 } } void _PostOrder(Node* pRoot)//递归后序遍历 { if (pRoot) { _PostOrder(pRoot->_pLeftChild);//递归左子树 _PostOrder(pRoot->_pRightChild);//递归右子树 cout << pRoot->_pData << " ";//访问根节点 } } void _LevelOrder(Node* pRoot)//层序 { if (NULL == pRoot) return; queue<Node*> q;//使用队 q.push(pRoot); while (!q.empty()) { Node* temp = q.front(); if (temp->_pLeftChild)//左子树存在，先入队左子树，因为先入先出，保证从左到右的顺序 q.push(temp->_pLeftChild); if (temp->_pRightChild)//右子树存在，入队右子树 q.push(temp->_pRightChild); cout << temp->_pData << " ";//访问当前节点 q.pop(); } } //求叶子节点的个数 //方法1： //int _SumLeafNode(Node* pRoot, int& sum) //{ // if (pRoot) // { // _SumLeafNode(pRoot->_pLeftChild, sum);//递归左子树到最低层 // _SumLeafNode(pRoot->_pRightChild, sum);//递归右子树到最低层 // if (!(pRoot->_pLeftChild) && !(pRoot->_pRightChild))//若此节点无左右孩子，则为叶子节点，则给计数器加一 // return ++sum; // else // return sum; // } // else // return sum; //} int _SumLeafNode(Node* pRoot) { if (NULL == pRoot)//当前子树不存在，返回0 return 0; if (NULL == pRoot->_pLeftChild && NULL == pRoot->_pRightChild)//当前节点为叶子结点，返回1 return 1; return _SumLeafNode(pRoot->_pLeftChild) + _SumLeafNode(pRoot->_pRightChild);//递归左子树的叶子节点和右子树的，并相加 } Node* _FindNode(Node* pRoot, T& value)//查找value是否在二叉树中 { if (pRoot) { if (pRoot->_pData == value)//遍历到value值时，直接返回该节点 return pRoot; Node* temp = _FindNode(pRoot->_pLeftChild, value);//递归左子树,必须要用变量接收，因为此递归函数为尾递归 //不接收的话，直接返回，造成节点未完全访问 if (temp) return temp; Node* tmp = _FindNode(pRoot->_pRightChild, value);//递归右子树 if (tmp) return tmp; } else return NULL; } size_t _HightOfBinTree(Node* pRoot) //求树的高度 { if (NULL == pRoot)//若当前节点为空，则当前子树的高度为0 return 0; if (NULL == pRoot->_pLeftChild && NULL == pRoot->_pRightChild)//递归到叶子节点，高度必然为1 return 1; int left = _Height(pRoot->_pLeftChild); int right = _Height(pRoot->_pRightChild); return (left > right ? left : right) + 1;//比较左右子树较大者再加上根节点就是这个子树的高度 } Node* _GetParents(Node* pRoot, Node* child)//获取双亲节点 { if (NULL == pRoot)//子树不存咋，返回NULL return NULL; if (pRoot == child)//只有一个根节点，不可能有双亲，返回NULL return NULL; if (pRoot->_pLeftChild == child || pRoot->_pRightChild == child)//pRoot的左孩子 或 右孩子为child，表示找到，返回pRoot return pRoot; Node* temp = _GetParents(pRoot->_pLeftChild, child);//递归左子树，注意变量接收 if (temp) return temp; temp = _GetParents(pRoot->_pRightChild, child); // 递归左子树 if (temp) return temp; } Node* _GetLeftChild(Node* pRoot, Node* parent)//获取左孩子 { if (NULL == pRoot)//子树不存在 return NULL; if (parent->_pLeftChild) return parent->_pLeftChild; } Node* _GetRightChild(Node* pRoot, Node* parent)//获取右孩子 { if (NULL == pRoot)//子树不存在 return NULL; if (parent->_pRightChild) return parent->_pRightChild; } size_t _GetKLevelCount(Node* pRoot, size_t k)//获取第K层节点的个数 { if (NULL == pRoot || k<1)//子树不存在，或者k<1，都表示此时的K层有0个节点 return 0; if (k == 1)//K==1时,表示该子树在K层的左孩子或者右孩子存在， //递归左子树时，判断左孩子是否存在，存在返回1，递归右子树时，判断右孩子是否存在，存在也返回1 return 1; return _GetKLevelCount(pRoot->_pLeftChild, k - 1) + _GetKLevelCount(pRoot->_pRightChild, k - 1);//递归左右子树 } void _BinaryMirror(Node* pRoot)//递归制造镜像树 { if (NULL == pRoot) return; std::swap(pRoot->_pLeftChild, pRoot->_pRightChild);//交换坐右子树 _BinaryMirror(pRoot->_pLeftChild);//递归左子树 _BinaryMirror(pRoot->_pRightChild);//递归右子树 } Node* _pRoot; T _invalid; }; void FunTest()//测试函数 { char* arr = "124###35##6"; char invalid = '#'; BinartyTree<char> bt(arr, strlen(arr), invalid); bt.GetKLevelCount(2); bt.PostOrder_Nor(); bt.FrontOrder(); bt.InOrder(); bt.PostOrder(); bt.LevelOrder(); bt.SumLeafNode(); bt.FindNode('5'); bt.HightOfBinTree(); bt.FrontOrder_Nor(); bt.InOrder_Nor(); BinaryNode<char>* temp = bt.FindNode('5'); bt.GetParents(temp); temp = bt.FindNode('3'); bt.GetLeftChild(temp); bt.GetRightChild(temp); bt.GetKLevelCount(5); BinartyTree<char> bt1(bt); bt1.BinaryMirror(); bt1.BinaryMirror_Nor(); bt1.FrontOrder(); bt1.InOrder(); bt1.PostOrder(); bt1.LevelOrder(); char* brr = "124##78##9##35##6##"; BinartyTree<char> bt2(brr, strlen(brr), invalid); bt2.PostOrder_Nor(); } int main() { FunTest(); system("pause"); return 0; }