包含的二叉樹運算: 刪除一個二叉樹, 求一顆二叉樹的高度, 求一顆二叉樹中葉子結點數, 復制一顆二叉樹, 交換一顆二叉樹的左右子樹, 自上到下, 自左到右層次遍歷一顆二叉樹. 增加相關功能完善即可, 層次遍歷利用隊列作為輔助的數據結構, 元素類型是指向二叉樹中結點的指針類型. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "queue" #include "stack" #include "cmath" #include "utility" #include "map" #include "set" #include "vector" #include "list" using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; template <class T> struct BTNode { /* data */ BTNode() { lChild = rChild = NULL; } BTNode(const T& x) { element = x; lChild = rChild = NULL; } BTNode(const T& x, BTNode<T>* l, BTNode<T>* r) { element = x; lChild = l; rChild = r; } T element; BTNode<T>* lChild, *rChild; }; template <class T> class Queue { public: virtual bool IsEmpty() const = 0; // 隊列為空返回true virtual bool IsFull() const = 0; // 隊列滿返回true virtual bool Front(T &x) const = 0; // 隊頭元素賦給x，操作成功返回true virtual bool EnQueue(T x) = 0; // 隊尾插入元素x，操作成功返回true virtual bool DeQueue() = 0; // 刪除隊頭元素，操作成功返回true virtual bool Clear() = 0; // 清除隊列中所有元素 }; template <class T> class SeqQueue:public Queue<T> { public: SeqQueue(int mSize); ~SeqQueue() { delete []q; } bool IsEmpty() const { return front == rear; } // front與rear相等時循環隊列為空 bool IsFull() const { return (rear + 1) % maxSize == front; } // front與(rear + 1) % maxSize相等時循環隊列滿 bool Front(T &x) const; bool EnQueue(T x); bool DeQueue(); bool Clear() { front = rear = 0; return true; } /* data */ private: int front, rear, maxSize; // 隊頭元素 隊尾元素 數組最大長度 T *q; }; template <class T> SeqQueue<T>::SeqQueue(int mSize) { maxSize = mSize; q = new T[maxSize]; front = rear = 0; } template <class T> bool SeqQueue<T>::Front(T &x) const { if(IsEmpty()) { // 空隊列處理 cout << "SeqQueue is empty" << endl; return false; } x = q[(front + 1) % maxSize]; return true; } template <class T> bool SeqQueue<T>::EnQueue(T x) { if(IsFull()) { // 溢出處理 cout << "SeqQueue is full" << endl; return false; } q[(rear = (rear + 1) % maxSize)] = x; return true; } template <class T> bool SeqQueue<T>::DeQueue() { if(IsEmpty()) { // 空隊列處理 cout << "SeqQueue is empty" << endl; return false; } front = (front + 1) % maxSize; return true; } template <class T> class BinaryTree { public: BinaryTree(): s(100){ root = NULL; } bool IsEmpty() const; // 判斷是否為空, 是返回true void Clear(); // 移去所有結點, 成為空二叉樹 bool Root(T& x) const; // 若二叉樹為空, 則x為根的值, 返回true BTNode<T>* Root(); int Size(); int Count() { return Count(root); } void MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 構造一顆二叉樹, 根的值為x, left & right為左右子樹 void BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 拆分二叉樹為三部分, x為根的值, left & right為左右子樹 void PreOrder(void (*Visit)(T& x)); // 先序遍歷二叉樹 void InOrder(void (*Visit)(T& x)); // 中序遍歷二叉樹 void PostOrder(void (*Visit)(T& x)); // 后序遍歷二叉樹 int High(BTNode<T> *p); // 返回二叉樹高度 int Num(BTNode<T> *p); // 返回二叉樹葉子結點數 BTNode<T> *Copy(BTNode<T> *t); // 復制二叉樹 void Exchange(BTNode<T> *&t); // 交換二叉樹左右子樹 void Level_Traversal(void(*Visit)(T &x)); // 層次遍歷二叉樹 BTNode<T>* root; protected: SeqQueue<T> s; private: void Clear(BTNode<T> *t); int Size(BTNode<T> *t); // 返回二叉樹結點個數 int Count(BTNode<T> *t); // 返回二叉樹只有一個孩子的結點個數 void PreOrder(void (*Visit)(T &x), BTNode<T> *t); void InOrder(void (*Visit)(T &x), BTNode<T> *t); void PostOrder(void (*Visit)(T &x), BTNode<T> *t); void Level_Traversal(void(*Visit)(T &x), BTNode<T> *t); }; template <class T> void Visit(T &x) { cout << x << '\t'; } template <class T> BTNode<T>* BinaryTree<T>::Root() { return root; } template <class T> bool BinaryTree<T>::Root(T &x) const { if(root) { x = root -> element; return true; } return false; } template <class T> void BinaryTree<T>::Clear() { Clear(root); } template <class T> void BinaryTree<T>::Clear(BTNode<T> *t) { if(t) { Clear(t -> lChild); Clear(t -> rChild); cout << "delete" << t -> element << "..." << endl; delete t; } } template <class T> void BinaryTree<T>::MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right) { if(root || &left == &right) return; root = new BTNode<T>(x, left.root, right.root); left.root = right.root = NULL; } template <class T> void BinaryTree<T>::BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& right) { if(!root || &left == &right || left.root || right.root) return; x = root -> element; left.root = root -> lChild; right.root = root -> rChild; delete root; root = NULL; } template <class T> void BinaryTree<T>::PreOrder(void (*Visit)(T& x)) { PreOrder(Visit, root); } template <class T> void BinaryTree<T>::PreOrder(void (*Visit)(T& x), BTNode<T>* t) { if(t) { Visit(t -> element); PreOrder(Visit, t -> lChild); PreOrder(Visit, t -> rChild); } } template <class T> void BinaryTree<T>::InOrder(void (*Visit)(T& x)) { InOrder(Visit, root); } template <class T> void BinaryTree<T>::InOrder(void (*Visit)(T& x), BTNode<T>* t) { if(t) { InOrder(Visit, t -> lChild); Visit(t -> element); InOrder(Visit, t -> rChild); } } template <class T> void BinaryTree<T>::PostOrder(void (*Visit)(T& x)) { PostOrder(Visit, root); } template <class T> void BinaryTree<T>::PostOrder(void (*Visit)(T& x), BTNode<T>* t) { if(t) { PostOrder(Visit, t -> lChild); PostOrder(Visit, t -> rChild); Visit(t -> element); } } template <class T> int BinaryTree<T>::Size() { return Size(root); } template <class T> int BinaryTree<T>::Size(BTNode<T> *t) { if(!t) return 0; return Size(t -> lChild) + Size(t -> rChild) + 1; } template <class T> int BinaryTree<T>::Count(BTNode<T> *t) { if(!t) return 0; if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1; return Count(t -> lChild) + Count(t -> rChild); } template <class T> int BinaryTree<T>::High(BTNode<T> *p) { if(p == NULL) return 0; else if(p -> lChild == NULL && p -> rChild ==NULL) return 1; else return(High(p -> lChild) > High(p -> rChild) ? High(p -> lChild) + 1 : High(p -> rChild) + 1); } template <class T> int BinaryTree<T>::Num(BTNode<T> *p) { if(p) { if(p -> lChild == NULL && p -> rChild == NULL) return 1; else return Num(p -> lChild) + Num(p -> rChild); } else return 0; } template <class T> BTNode<T>*BinaryTree<T>::Copy(BTNode<T> *t) { if(t == NULL) return NULL; BTNode<T> *q = new BTNode<T>(t -> element); q -> lChild = Copy(t -> lChild); q -> rChild = Copy(t -> rChild); return q; } template <class T> void BinaryTree<T>::Exchange(BTNode<T> *&t) { if(t) { BTNode<T> *q = t -> lChild; t -> lChild = t -> rChild; t -> rChild = q; Exchange(t -> lChild); Exchange(t -> rChild); } } template <class T> void BinaryTree<T>::Level_Traversal(void(*Visit)(T &x), BTNode<T> *t) { BTNode<T> *a; Visit(t -> element); if(t -> lChild) s.EnQueue(t -> lChild); if(t -> rChild) s.EnQueue(t -> rChild); while(s.Front(a) == true) { if(a -> lChild) s.EnQueue(a -> lChild); if(a -> rChild) s.EnQueue(a -> rChild); Visit(a -> element); s.DeQueue(); } } int main(int argc, char const *argv[]) { BinaryTree<char> t[100], a, b, tmp; int num = 0, high = 0; t[7].MakeTree('H', a, b); t[8].MakeTree('I', a, b); t[3].MakeTree('D', t[7], t[8]); t[4].MakeTree('E', a, b); t[5].MakeTree('F', a, b); t[6].MakeTree('G', a, b); t[1].MakeTree('B', t[3], t[4]); t[2].MakeTree('C', t[5], t[6]); t[0].MakeTree('A', t[1], t[2]); cout << "二叉樹z的層次遍歷結果:\n"; t[0].PreOrder(Visit); cout << endl; tmp.root = tmp.Copy(t[0].root); cout << "tmp復制二叉樹z后層次遍歷結果:\n"; tmp.PreOrder(Visit); cout << endl; t[0].Exchange(t[0].root); cout << "交換左右子樹后二叉樹z的層次遍歷結果:\n"; t[0].PreOrder(Visit); cout << endl; num = t[0].Num(t[0].root); cout << "二叉樹z的葉子結點數為:\n" << num << endl; high = t[0].High(t[0].root); cout << "二叉樹z的高度為:\n" << high << endl; t[0].Clear(); return 0; } ~~~