JS技术

数据结构实验2(二叉链表实现二叉树的基本运算) - GKHacks Blog - 博客频道 - CSDN.NET GKH

字号+ 作者:H5之家 来源:H5之家 2015-12-14 16:13 我要评论( )

style=visibility: hidden和 style=“display:none”区别大多数人很容易将CSS属性display和visibility混淆,它们看似没有什么不同,其实它们的差别却是很大的。v

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

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

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

实现代码:

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

  • 上一篇Codeforces Round #335 (Div. 2) 606C Sorting Railway Cars(hash)
  • 下一篇数据结构实验3(图的DFS和BFS实现)
  • 顶 1 踩 0

    我的同类文章

    猜你在找

    查看评论

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

     

    1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

    相关文章
    • Arduino 温湿度传感器DHT11模块实验 - 比特字节-只为技术 - 博客频道 - CSDN.NET 比特字节-只

      Arduino 温湿度传感器DHT11模块实验 - 比特字节-只为技术 - 博客频道

      2015-12-15 08:54

    • 数据结构实验3(飞机最少环城次数问题) - GKHacks Blog - 博客频道 - CSDN.NET GKHacks

      数据结构实验3(飞机最少环城次数问题) - GKHacks Blog - 博客频道 -

      2015-12-14 16:18

    • 数据结构实验3(图的DFS和BFS实现) - GKHacks Blog - 博客频道 - CSDN.NET GKHack

      数据结构实验3(图的DFS和BFS实现) - GKHacks Blog - 博客频道 - CSDN

      2015-12-14 16:06

    • 实验D----两个数的互素判定 - ITSophia的专栏 - 博客频道 - CSDN.NET ITSophia的专栏

      实验D----两个数的互素判定 - ITSophia的专栏 - 博客频道 - CSDN.NET

      2015-12-14 15:39

    网友点评
    e