二叉树、线索二叉树类模版（C++）

#include <iostream> #include <queue> #include <stack> /*******二叉树模版,,,,,,luna_leung******/ //尼玛啊写完这模版一看都500行了啊姐姐我纯手工精制出来的啊啊啊啊啊啊啊啊啊~~~~~~~ using namespace std; template <typename T> class BinaryTree; template <typename T> class Node { T data; Node<T> * left; Node<T> * right; public: Node(); friend class BinaryTree<T>; }; template <typename T> Node<T>::Node() { data = 0; left = NULL; right = NULL; } template <typename T> class BinaryTree { protected: Node<T>* root; public: BinaryTree(); bool empty(); bool leaf(Node<T>* pCur); Node<T>* get_root(); void set_root(T & a); //先序中序构造，先序序列pre，中序序列in, 中序序列范围in1~in2，序列总长len Node<T>* prein_set(Node<T>* pRoot, T* pre, T* in, int in1, int in2, int len); //后序中序构造，后序序列post，中序序列in, 中序序列范围in1~in2，序列总长len Node<T>* postin_set(Node<T>* pRoot, T* post, T* in, int in1, int in2, int len); int du(Node<T>*pCur); //结点的度 int du_sum(Node<T>* pRoot, int n); //统计度为n的结点个数 int high(Node<T>* pRoot); //高度 int width(Node<T>* pRoot); //宽度 T max(Node<T>* pRoot); //结点的最大值 void lr_swap(Node<T>* &pRoot); //交换每个结点的左右 void del_leaf(Node<T>* &pRoot, bool tag);//删除叶结点 bool wanquan(Node<T>* pRoot); //是否完全二叉树 void breadth_first(Node<T>* pCur); //从当前结点起广度优先遍历 void pre_order(Node<T>* pCur); //从当前结点起先序遍历 void in_order(Node<T>* pCur); //从当前结点起中序遍历 void post_order(Node<T>* pCur); //从当前结点起后序遍历 void clear(Node<T>* pCur); ~BinaryTree(); }; template <typename T> BinaryTree<T>::BinaryTree() { root = NULL; } template <typename T> bool BinaryTree<T>::empty() { if(root==NULL) return true; return false; } template <typename T> bool BinaryTree<T>::leaf(Node<T>* pCur) { if(pCur->left==NULL && pCur->right==NULL) return true; return false; } template <typename T> Node<T>* BinaryTree<T>::get_root() { return root; } template <typename T> void BinaryTree<T>::set_root(T & a) { root = new Node<T>; root->data = a; } template <typename T> Node<T>* BinaryTree<T>::prein_set(Node<T>* pRoot, T* pre, T* in, int in1, int in2, int len) //先序中序构造 { //非法数据检测 if(pre==NULL || in==NULL || in1<0 ||in2<0 || len<=0) return NULL; if(pRoot!=NULL) clear(pRoot); int index,i; if(in1==in2) //只有一个结点 { pRoot = new Node<T>; pRoot->data = in[in1]; //cout<<pRoot->data<<endl; return pRoot; } //寻找根结点在中序序列中的位置 for(i = 0,index = in1; in[index]!=*pre && i<len; index++); if(i==len) //找不到匹配的根结点 { cout<<"序列出错！"<<endl; return NULL; } pRoot = new Node<T>; pRoot->data = in[index]; //cout<<pRoot->data<<endl; if(index>in1) //index<=in1: 无左子树 pRoot->left = prein_set(pRoot->left, pre+1, in, in1, index-1, index-in1); if(index<in2) pRoot->right = prein_set(pRoot->right, pre+index-in1+1, in, index+1, in2, in2-index); return pRoot; } template <typename T> Node<T>* BinaryTree<T>::postin_set(Node<T>* pRoot, T* post, T* in, int in1, int in2, int len) //后序中序构造 { if(post==NULL || in==NULL || in1<0 || in2<0 ||len<=0) return NULL; if(pRoot!=NULL) clear(pRoot); if(in1==in2) { pRoot = new Node<T>; pRoot->data = in[in1]; return pRoot; } int index, i; for(i = len-1, index = in1; in[index]!=post[i] && i>=0;) { if(index>in2) { i--; index = in1; } else index++; } if(i<0) { cout<<"序列出错！"<<endl; return NULL; } pRoot = new Node<T>; pRoot->data = in[index]; if(index<in2) pRoot->right = postin_set(pRoot->right, post, in, index+1, in2, len-1); if(index>in1) pRoot->left = postin_set(pRoot->left, post, in, in1, index-1, len-1); return pRoot; } template <typename T> void BinaryTree<T>::breadth_first(Node<T>* pCur) //从当前结点起广度优先遍历 { if(pCur==NULL) return ; Node<T>* temp = NULL; queue<Node<T>*> node_queue; cout<<pCur->data; if(pCur->left) node_queue.push(pCur->left); if(pCur->right) node_queue.push(pCur->right); while(!node_queue.empty()) { temp = node_queue.front(); cout<<temp->data; node_queue.pop(); if(temp->left!=NULL) node_queue.push(temp->left); if(temp->right!=NULL) node_queue.push(temp->right); } } template <typename T> void BinaryTree<T>::pre_order(Node<T>* pCur) //从当前结点起先序遍历 { if(pCur==NULL) return ; stack<Node<T>*> node_stack; Node<T>* temp = NULL; cout<<pCur->data; //访问根结点（根结点不入栈） if(pCur->right) node_stack.push(pCur->right); temp = pCur->left; while(!node_stack.empty() || temp!=NULL) { if(temp==NULL) { temp = node_stack.top(); node_stack.pop(); } cout<<temp->data; if(temp->right!=NULL) //右结点入栈 node_stack.push(temp->right); temp = temp->left; //指针指向左结点（左结点不入栈） } } template <typename T> void BinaryTree<T>::in_order(Node<T>* pCur) //从当前结点起中序遍历 { if(pCur==NULL) return ; stack<Node<T>*> node_stack; Node<T>* temp = pCur; while(!node_stack.empty() || temp!=NULL) { if(temp!=NULL) //将当前结点入栈并将指针指向左结点 { node_stack.push(temp); temp = temp->left; } else //走到左的尽头了，回去找上一个节点（栈顶元素） { temp = node_stack.top(); cout<<temp->data; node_stack.pop(); temp = temp->right; } } } template <typename T> void BinaryTree<T>::post_order(Node<T>* pCur) //从当前结点起后序遍历 { if(pCur==NULL) return ; Node<T>* prev = pCur; stack<Node<T>*> node_stack; while(pCur->left) //一路向左... { node_stack.push(pCur); pCur = pCur->left; } while(!node_stack.empty()) { if(pCur->right!=NULL && pCur->right!=prev)//右路不为空且未访问过 { if(pCur!=node_stack.top()) node_stack.push(pCur); pCur = pCur->right; while(pCur->left) //一路向左... { node_stack.push(pCur); pCur = pCur->left; } } else { if(pCur==node_stack.top()) node_stack.pop(); cout<<pCur->data; prev = pCur ; if(node_stack.empty()) return ; pCur = node_stack.top(); } } } template <typename T> void BinaryTree<T>::clear(Node<T>* pCur) //广度优先遍历删除以pCur为根指针的树 { if(pCur==NULL) return ; Node<T>* temp = NULL; queue<Node<T>*> node_queue; if(pCur->left) node_queue.push(pCur->left); if(pCur->right) node_queue.push(pCur->right); delete pCur; while(!node_queue.empty()) { temp = node_queue.front(); node_queue.pop(); if(temp->left!=NULL) node_queue.push(temp->left); if(temp->right!=NULL)