该文件中应用双向链表充当队列与栈，链表放在DLinkList.h头文件中。
DLinkList.h头文件的地址: http://blog.csdn.net/aiwodaqinshi/article/details/52170958
//******************************************************************************** // 作者：忠义乾坤 // 日期：2016-08-13 // 描述： // 1.二叉树 // 2.前序遍历，中序遍历，后序遍历，层序遍历。 // 3.求解二叉树的高度（递归和非递归）。 // 4.求解一个结点的父结点。 // 说明：将该文件放在BinaryTree.h文件中，在源文件中包含#include "BinaryTree.h"即可。 //******************************************************************************** #pragma //保证该头文件只被引用一次 #include "DLinkList.h" #include <iostream> using namespace std; //******************************************************** // 类名：BinaryTreeNode // 描述：构建一个二叉树结点 //******************************************************** template<class DataType> class BinaryTreeNode { public: DataType data; //结点数据 BinaryTreeNode<DataType> * lChildPtr; //左子结点 BinaryTreeNode<DataType> * rChildPtr; //右子结点 //****************************【构建一个指定数据域的结点】*********************** BinaryTreeNode(const DataType &newData) { data = newData; lChildPtr = NULL; rChildPtr = NULL; } ~BinaryTreeNode() { lChildPtr = NULL; rChildPtr = NULL; } }; //******************************************************** // 类名：BinaryTree // 描述：创建一个二叉树类 //******************************************************** template<class DataType> class BinaryTree { private: BinaryTreeNode<DataType>* rootPtr; //根节点 public: BinaryTree() { rootPtr = NULL; } ~BinaryTree() { cleanNode(rootPtr); } //****************************【返回根结点】********************************** BinaryTreeNode<DataType> *getRootPoint(void) { return rootPtr; } //****************************【层序插入】********************************** void insertLay(const DataType &value) { BinaryTreeNode<DataType> *node = rootPtr; BinaryTreeNode<DataType> *current; //设置指向当前结点的指针 DLinkList<BinaryTreeNode<DataType>*>list; //创建一个双向链表替代队列 if(node == NULL) { BinaryTreeNode<DataType> *ptr = new BinaryTreeNode<DataType>(value); rootPtr = ptr; } if(node != NULL)//判断初始结点是否为空 { list.insertFromBack(node); //将初始根结点移入队列 while(list.getLength() != 0) //判断队列元素是否完全出队 { current = list.getHeadPoint()->getData(); //队首元素设置为当前结点 if(current->lChildPtr != NULL) //判断出队元素的左子结点是否为空，若不为空，则入队 { list.insertFromBack((current->lChildPtr)); //将左孩子结点入队 } else //如果左孩子结点为空，则改位置即插入新元素 { BinaryTreeNode<DataType> *ptr = new BinaryTreeNode<DataType>(value); current->lChildPtr = ptr; break; //插入结点后，停止遍历，跳出循环 } if(current->rChildPtr !=NULL) { list.insertFromBack((current->rChildPtr)); } else //如果右孩子结点为空，则改位置即插入新元素 { BinaryTreeNode<DataType> *ptr = new BinaryTreeNode<DataType>(value); current->rChildPtr = ptr; break; //插入结点后，停止遍历，跳出循环 } list.removeFromFront(); //将进入左右孩子结点都入队的结点出队 } } } //*****************************【向二叉树中插入一个新结点】********************** void insertNode( const DataType &value ) { insertNodeHelper( &rootPtr, value ); } //****************************【以该结点为根结点，向该树插入结点】**************** //只使用于内置数据类型，不适用与类与结构体 void insertNodeHelper(BinaryTreeNode< DataType > **ptr, const DataType &value ) { // 子树是空的，添加一个新结点 if ( *ptr == 0 ) { *ptr = new BinaryTreeNode< DataType >( value ); } else //子树非空 { // 当数据小于当前点的数据，插入左结点 if ( value < (*ptr) ->data ) insertNodeHelper( &((*ptr) ->lChildPtr) , value ); else { // 当数据大于当前结点的数据，插入右结点 if ( value > (*ptr) ->data ) insertNodeHelper( &((*ptr)->rChildPtr) , value ); else // duplicate data value ignored cout << value << " dup" << endl; } } } //*****************************【前序遍历】*************************************** void preOrder(BinaryTreeNode<DataType>* ptr) { if(ptr != NULL) //子树非空 { cout<<ptr->data<<"\t"<<ptr<<endl; //输出指定结点信息（可更改，方便调试和使用） preOrder(ptr->lChildPtr); preOrder(ptr->rChildPtr); } } //*******************************【中序遍历】*************************************** void midOrder(BinaryTreeNode<DataType> *ptr) { if(ptr!=NULL) //子树非空 { midOrder(ptr->lChildPtr); cout<<ptr->data<<"\t"<<ptr<<endl; //输出指定结点信息（可更改，方便调试和使用） midOrder(ptr->rChildPtr); } } //********************************【后序遍历】*************************************** void lastOrder(BinaryTreeNode<DataType> *ptr) { if(ptr != NULL) { lastOrder(ptr->lChildPtr); lastOrder(ptr->rChildPtr); cout<<ptr->data<<"\t"<<ptr<<endl; //输出指定结点信息（可更改，方便调试和使用） } } //*******************************【层序遍历】************************************** void layOrder(BinaryTreeNode<DataType>*node) { BinaryTreeNode<DataType> *current; //设置指向当前结点的指针 DLinkList<BinaryTreeNode<DataType>*>list; //创建一个双向链表替代队列 if(node != NULL) //判断初始结点是否为空 { list.insertFromBack(node); //将初始根结点移入队列 while(list.getLength() != 0) //判断队列元素是否完全出队 { current = list.getHeadPoint()->getData(); //队首元素设置为当前结点 cout<<current->data<<"\t"<<current<<endl; //输出队首元素的信息（可修改） if(current->lChildPtr != NULL) //队元素的左子结点若不为空，则入队 { list.insertFromBack((current->lChildPtr)); //将左孩子结点入队 } if(current->rChildPtr !=NULL) { list.insertFromBack((current->rChildPtr)); //将由孩子结点入队 } list.removeFromFront(); //将进入左右孩子结点都入队的结点出队 } } } //***************************【清空二叉树】******************************* void cleanNode(BinaryTreeNode<DataType>*ptr) { if(ptr != NULL) { cleanNode(ptr->lChildPtr); cleanNode(ptr->rChildPtr); //cout<<"删除："<<ptr->data<<" "<<ptr<<endl;//输出要删除的结点数据与结点数据地址 delete ptr; } } //**************************【寻求一个结点的父结点】************************ BinaryTreeNode<DataType> *getFatherPoint(BinaryTreeNode<DataType> *node) { if(node == NULL || node == rootPtr) //如果该结点为空，或为根结点，则该结点无父结点 return NULL; else { BinaryTreeNode<DataType> *current; //设置指向当前结点的指针 DLinkList<BinaryTreeNode<DataType>*>list; //创建一个双向链表替代队列 list.insertFromBack(rootPtr); //将初始根结点移入队列 while(list.getLength() != 0) //判断队列元素是否完全出队 { current = list.getHeadData(); //队首元素设置为当前结点 if(current->lChildPtr != NULL) //出队元素的左子结点是若不为空，则入队 { //当该结点为目标结点的父结点 if((current->lChildPtr == node) || (current->rChildPtr == node)) { return current; } list.insertFromBack((current->lChildPtr)); //该结点不是目标结点的父结点，则左孩子结点入队 } if(current->rChildPtr !=NULL) { //当该结点为目标结点的父结点 if((current->rChildPtr == node) || (current->rChildPtr == node)) { return current; } list.insertFromBack((current->rChildPtr)); //该结点不是目标结点的父结点，则右孩子结点入队 } list.removeFromFront(); } return NULL; } } //**********************************【求解二叉树的高度非递归版】****************************** int getDepth() { int maxDepth = 0; //最大深度 int currentDepth = 1; //当前深度 DLinkList<BinaryTreeNode<DataType> *>nodeStack;//创建一个双向链表，充当结点栈的使用 DLinkList<int> depthStack;//定义一个双向链表，充当深度栈的书用 BinaryTreeNode<DataType> *node = rootPtr; if(node != NULL) { currentDepth =1; //循环遍历整棵树，将访问的结点入栈，并不停反复查找最长的路径 do { while(node != NULL) { nodeStack.insertFromBack(node); //将访问到的不为空的结点入栈，直至遇到空结点为止 depthStack.insertFromBack(currentDepth); //将相应的深度入栈 node = node->lChildPtr; //继续访问当前的结点的左孩子结点 currentDepth++; //当前深度加1 } node = nodeStack.getTailPoint()->getData(); //一条路径走到尽头时，出栈栈顶元素，尝试新路径 nodeStack.removeFromBack(); //结点出栈 currentDepth = depthStack.getTailPoint()->getData(); depthStack.removeFromBack(); //深度出栈 if(node->lChildPtr == NULL && node->rChildPtr == NULL) //判断是否有叶子结点 { if(currentDepth >maxDepth) //如果该叶子结点的深度大于最大深度，更改最大深度。 maxDepth = currentDepth; } node = node->rChildPtr; //开始访问出栈结点的右子树 currentDepth++; } while (!(node == NULL&&depthStack.getLength() == NULL && nodeStack.getLength() == NULL)); } return maxDepth; } //**********************************【求解二叉树的高度递归版】****************************** int getHigh(BinaryTreeNode<DataType> *root) { if(root == NULL) { return 0; } int leftDepth = getHigh(root->lChildPtr); int rightDepth = getHigh(root->rChildPtr); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; } //**********************************【判断一棵树是否为空】********************************** bool isEmpty(BinaryTreeNode<DataType>*root) { if(root == NULL) //如果根结点是空，该树是一棵空树 return true; else return false; } //**********************************【比较两棵树是否相同】********************************** bool compareTree(BinaryTreeNode<DataType>* tree1,BinaryTreeNode<DataType>* tree2) { bool isTree1Null = (tree1 == NULL); //判断是否为空数 bool isTree2Null = (tree2 == NULL); if(isTree1Null != isTree2Null) //一棵空树，另一棵不是空树，肯定不相等 return false; if(isTree1Null &&isTree2Null) //两颗空树，肯定相等 return true; return (compareTree(tree1->lChildPtr,tree2->lChildPtr) & compareTree(tree1->rChildPtr,tree2->rChildPtr)); } };