包含的二叉树运算: 删除一个二叉树, 求一颗二叉树的高度, 求一颗二叉树中叶子结点数, 复制一颗二叉树, 交换一颗二叉树的左右子树,

自上到下, 自左到右层次遍历一颗二叉树.

增加相关功能完善即可, 层次遍历利用队列作为辅助的数据结构, 元素类型是指向二叉树中结点的指针类型.

实现代码:

#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; }

顶 1 踩 0

我的同类文章

查看评论

* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场