最近看数据结构看到二叉树的时候,自己实现了一下,同时写成了类,正好复习一下以前看C++的一些知识。代码如下。
// BiTNode.h // 参照《c++大学教程》中P639页编写 // 模版结点BiTNode类的声明 #ifndef BITNODE_H #define BITNODE_H // 声明BiNTree类型 template<typename NODETYPE> class BiTree; template<typename NODETYPE> class BiTNode { // 声明友元BiNTree类,使得BiTree类可以访问BiTNode类中的private成员 friend class BiTree<NODETYPE>; public: BiTNode(const NODETYPE &d) : lchild(0), data(d), rchild(0) { } NODETYPE getData() const { return data; } private: BiTNode<NODETYPE> *lchild; NODETYPE data; BiTNode<NODETYPE> *rchild; }; #endif
// BiTree.h // 链表二叉树类模版的定义 #ifndef BITREE_H #define BITREE_H #include <iostream> #include <iomanip> #include "BiTNode.h" #include <queue> #include <stack> using namespace std; typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 template<typename NODETYPE> class BiTree { public: BiTree(); void CreateBiTree(); void DestroyBiTree(); Status BiTreeEmpty(); NODETYPE Root(); int BiTreeDepth(); int BiTreeDepthNonRecursion(); void PreOrderTraverse(); void PreOrderNonRecursion(); void InOrderTraverse(); void InOrderNonRecursion(); void PostOrderTraverse(); void PostOrderNonRecursion(); void LevelOrderTraverse(); void PrintLast(); void PrintByDepth(); private: BiTNode<NODETYPE> *rootPtr; // utility function void visit(BiTNode<NODETYPE> *p); void CreateBiTreeHelper(BiTNode<NODETYPE> **T); void DestroyBiTreeHelper(BiTNode<NODETYPE> **T); int BiTreeDepthHelper(BiTNode<NODETYPE> *T); // 用helper函数的原因是对二叉树进行遍历要传入参数 void PreOrderTraverseHelper(BiTNode<NODETYPE> *T); void InOrderTraverseHelper(BiTNode<NODETYPE> *T); void PostOrderTraverseHelper(BiTNode<NODETYPE> *T); }; template<typename NODETYPE> BiTree<NODETYPE>::BiTree() { rootPtr = 0; } template<typename NODETYPE> Status BiTree<NODETYPE>::BiTreeEmpty() { if (rootPtr) return FALSE; else return TRUE; } template<typename NODETYPE> void BiTree<NODETYPE>::CreateBiTree() { CreateBiTreeHelper(&rootPtr); } // 按前序输入二叉树中结点的值(一个字符) // #表示空树,构造二叉链表表示二叉树T。 template<typename NODETYPE> void BiTree<NODETYPE>::CreateBiTreeHelper(BiTNode<NODETYPE> **T) { NODETYPE val; cin >> val; if (val == '#') *T = NULL; else { *T = new BiTNode<NODETYPE>(val); CreateBiTreeHelper(&(*T)->lchild); CreateBiTreeHelper(&(*T)->rchild); } } template<typename NODETYPE> void BiTree<NODETYPE>::DestroyBiTree() { DestroyBiTreeHelper(&rootPtr); } template<typename NODETYPE> void BiTree<NODETYPE>::DestroyBiTreeHelper(BiTNode<NODETYPE> **T) { if (*T) { if ((*T)->lchild) DestroyBiTreeHelper(&(*T)->lchild); if ((*T)->rchild) DestroyBiTreeHelper(&(*T)->rchild); free(*T); *T = NULL; } } template<typename NODETYPE> int BiTree<NODETYPE>::BiTreeDepth() { return BiTreeDepthHelper(rootPtr); } template<typename NODETYPE> int BiTree<NODETYPE>::BiTreeDepthHelper(BiTNode<NODETYPE> *T) { int i, j; if (!T) return 0; if (T->lchild) i = BiTreeDepthHelper(T->lchild); else i = 0; if (T->rchild) j = BiTreeDepthHelper(T->rchild); else j = 0; return i > j ? i+1 : j+1; } template<typename NODETYPE> NODETYPE BiTree<NODETYPE>::Root() { if (!rootPtr) return ' '; else return rootPtr->data; } // 借用层次遍历的思想,实现非递归形式求出二叉树深度 template<typename NODETYPE> int BiTree<NODETYPE>::BiTreeDepthNonRecursion() { if (!rootPtr) return 0; BiTNode<NODETYPE> *p; // 工作指针,每次记录从队列队首弹出的结点 BiTNode<NODETYPE> *back; // 记录每层二叉树的最右边的结点。此结点在每次遍历一层之后的队列队尾 int level = 0; // 层数,初始值为0 queue<BiTNode<NODETYPE> *> Q; Q.push(rootPtr); back = Q.back(); while (!Q.empty()) { p = Q.front(); Q.pop(); if (p->lchild) Q.push(p->lchild); if (p->rchild) Q.push(p->rchild); if (p == back) // 如果p == 每层的最右边的结点,则层数+1,同时重新赋值队尾结点 { level++; if (!Q.empty()) // 如果队列为空,则下一步的操作出错。主要用于防止最后一个结点弹出队列之后的那次操作 back = Q.back(); } } return level; } template<typename NODETYPE> void BiTree<NODETYPE>::PreOrderTraverse() { PreOrderTraverseHelper(rootPtr); } template<typename NODETYPE> void BiTree<NODETYPE>::PreOrderTraverseHelper(BiTNode<NODETYPE> *T) { if (!T) return; visit(T); PreOrderTraverseHelper(T->lchild); PreOrderTraverseHelper(T->rchild); } // 前序遍历非递归形式 template<typename NODETYPE> void BiTree<NODETYPE>::PreOrderNonRecursion() { if (!rootPtr) return; BiTNode<NODETYPE> *p; stack<BiTNode<NODETYPE> *> S; // 借助栈实现非递归的前序遍历 p = rootPtr; while (p || !S.empty()) { while (p) { visit(p); // 在每次入栈之前进行访问 S.push(p); p = p->lchild; } if (!S.empty()) { p = S.top(); S.pop(); p = p->rchild; } } } template<typename NODETYPE> void BiTree<NODETYPE>::InOrderTraverse() { InOrderTraverseHelper(rootPtr); } template<typename NODETYPE> void BiTree<NODETYPE>::InOrderTraverseHelper(BiTNode<NODETYPE> *T) { if (!T) return; InOrderTraverseHelper(T->lchild); visit(T); InOrderTraverseHelper(T->rchild); } template<typename NODETYPE> void BiTree<NODETYPE>::InOrderNonRecursion() { if (!rootPtr) return; BiTNode<NODETYPE> *p; stack<BiTNode<NODETYPE> *> S; p = rootPtr; while (p || !S.empty()) { while (p) { S.push(p); p = p->lchild; } if (!S.empty()) { p = S.top(); S.pop(); visit(p); // 在每次出栈之时进行访问 p = p->rchild; } } } template<typename NODETYPE> void BiTree<NODETYPE>::PostOrderTraverse() { PostOrderTraverseHelper(rootPtr); } template<typename NODETYPE> void BiTree<NODETYPE>::PostOrderTraverseHelper(BiTNode<NODETYPE> *T) { if (!T) return; PostOrderTraverseHelper(T->lchild); PostOrderTraverseHelper(T->rchild); visit(T); } template<typename NODETYPE> void BiTree<NODETYPE>::PostOrderNonRecursion() { if (!rootPtr) return; BiTNode<NODETYPE> *p; BiTNode<NODETYPE> *r; // 用于记录栈中弹出的结点的右子树是否访问过 stack<BiTNode<NODETYPE> *> S; p = rootPtr; r = NULL; while (p || !S.empty()) { while (p) { S.push(p); p = p->lchild; } if (!S.empty()) { p = S.top(); if (p->rchild && p->rchild != r) // 此结点的右子树尚未入栈 { p = p->rchild; S.push(p); p = p->lchild; } else { S.pop(); visit(p); // 每次出栈时访问结点 r = p; p = NULL; } } } } template<typename NODETYPE> void BiTree<NODETYPE>::LevelOrderTraverse() { if (!rootPtr) return; BiTNode<NODETYPE> *p; BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针 queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列 Q.push(rootPtr); back = Q.back(); while (!Q.empty()) { p = Q.front(); Q.pop(); visit(p); if (p->lchild) Q.push(p->lchild); if (p->rchild) Q.push(p->rchild); } } template<typename NODETYPE> void BiTree<NODETYPE>::PrintLast() { if (!rootPtr) return; BiTNode<NODETYPE> *p; BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针 queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列 Q.push(rootPtr); back = Q.back(); while (!Q.empty()) { p = Q.front(); Q.pop(); if (p->lchild) Q.push(p->lchild); if (p->rchild) Q.push(p->rchild); if (p == back) { visit(p); if (!Q.empty()) back = Q.back(); // 更新back指针的位置 } } } template<typename NODETYPE> void BiTree<NODETYPE>::PrintByDepth() { if (!rootPtr) return; BiTNode<NODETYPE> *p; BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针 queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列 Q.push(rootPtr); back = Q.back(); while (!Q.empty()) { p = Q.front(); Q.pop(); visit(p); if (p->lchild) Q.push(p->lchild); if (p->rchild) Q.push(p->rchild); if (p == back) { cout << endl; if (!Q.empty()) back = Q.back(); // 更新back指针的位置 } } } template<typename NODETYPE> void BiTree<NODETYPE>::visit(BiTNode<NODETYPE> *p) { cout << left << setw(5) << p->data; } #endif
为了省事,main函数有些代码直接使用了前面一篇文章里面c的代码。
// main.h #include <iostream> #include "BiTree.h" using namespace std; int main() { int i; BiTree<char> T; char e1; //StrAssign(str,"ABDH#K###E##CFI###G#J##"); T.CreateBiTree(); printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度: %d\n",T.BiTreeEmpty(), T.BiTreeDepthNonRecursion()); e1 = T.Root(); printf("二叉树的根为: %c\n",e1); printf("\n前序遍历二叉树:\n"); //T.PreOrderTraverse(); T.PreOrderNonRecursion(); printf("\n中序遍历二叉树:\n"); T.InOrderTraverse(); //T.InOrderNonRecursion(); printf("\n后序遍历二叉树:\n"); //T.PostOrderTraverse(); T.PostOrderNonRecursion(); printf("\n层次遍历二叉树:\n"); T.LevelOrderTraverse(); printf("\n每行二叉树的最右边的结点为:\n"); T.PrintLast(); printf("\n按层次输出每行的结点:\n"); T.PrintByDepth(); T.DestroyBiTree(); printf("\n清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",T.BiTreeEmpty(),T.BiTreeDepth()); i = T.Root(); if(!i) printf("树空,无根\n"); getchar(); getchar(); return 0; }
写这个代码的时候,感觉自己计算机编程入门了——之前写代码主要都是照着书写,出错了更多都是照着书查找错误。写这个二叉树类的时候有个地方指针出错了,自己设断点改错,改了很久。所以入门的一些经验在下面一篇文章里面谈谈吧。
参考资料:
1.《大话数据结构》
2.《C++大学教程(第七版)》
Pingback: 计算机入门的一点经验和对迷茫的一些分析 – Frank