模板实现二叉树的增删查改和遍历
最近博主在研究二叉树的基本操作：增删查改海投二叉树重要的遍历操作，这里只实现了递归遍历，如果有需要，我会次序更新，，谢谢你你能参考文章，如果觉得哪里不好或者有必要改进的，欢迎留言，欢迎留言，如果想要学习C/C++，linux，win32，MFC，QT等编程的欢迎加博主一起学习交流：QQ：2424496907，此文为原创，未经允许，不得转载，谢谢合作：！！！
#pragma once //Tree.h #include<iostream> #include<cstdlib> #include<ctime> #include<list>//队列 队尾插入 队头删除 struct node { struct node *lchild, *rchild, *father; int data; }; template<class T> class Tree { private: node *root; public: Tree(); ~Tree(); void insert(T data); node* findNode(int data); void preOrder(node *p);//先序遍历 void inOrder(node* p); void lasOrder(node* p); void clear(node* p); node* getRoot(); void leverOrder(); void deleByData(int data); }; template<class T> Tree<T>::Tree() :root(nullptr){} template<class T> Tree<T>::~Tree() { clear(root); root = nullptr; } template<class T> void Tree<T>::insert(T data) { if (nullptr == root)//判断是否空树 { root = new node; root->data = data; root->lchild = root->rchild = root->father = nullptr; } else { node *p = root; while (true) { if (p->data <= data) { if (nullptr == p->rchild) { p->rchild = new node; p->rchild->lchild = p->rchild->rchild = nullptr; p->rchild->father = p->rchild; p->rchild->data = data; break; } p = p->rchild; } else { if (nullptr == p->lchild) { p->lchild = new node; p->lchild->lchild = p->lchild->rchild = nullptr; p->lchild->data = data; p->lchild->father = p->lchild; break; } p = p->lchild; } } } } template<class T> node * Tree<T>::findNode(int data) { node * p = root; while (nullptr != p) { if (p->data == data) break; else if (p->data < data) p = p->rchild; else p = p->lchild; } return p; } template<class T> void Tree<T>::preOrder(node* p) { if (nullptr != p) { std::cout << p->data << '\t'; preOrder(p->lchild); preOrder(p->rchild); } } template<class T> void Tree<T>::inOrder(node*p)//中序遍历 { if (p != nullptr) { inOrder(p->lchild); std::cout << p->data << '\t'; inOrder(p->rchild); } } template<class T> void Tree<T>::lasOrder(node*p) { if (p != nullptr) { lasOrder(p->lchild); lasOrder(p->rchild); std::cout << p->data << '\t'; } } template<class T> void Tree<T>::clear(node*p) { if (p != nullptr) { clear(p->lchild); clear(p->rchild); delete p; } } template<class T> node* Tree<T>::getRoot() { return root; } template<class T> void Tree<T>::leverOrder() { using std::list; list<node*>lis; lis.push_back(root); node*p; while (lis.empty() == 0)//lis不空 { p = lis.front();//得到队头元素 if (nullptr!=p) { lis.push_back(p->lchild); lis.push_back(p->rchild); std::cout << p->data << '\t'; } lis.pop_front();//出队 } } template<class T> void Tree<T>::deleByData(int data) { node*p = findNode(data);//查找要删除的节点 if (p == nullptr) return; else if (p == root)//要删除的是根节点 { if (root->lchild == nullptr&&root->rchild == nullptr)//只有一个节点 { delete root;//直接删除 root = nullptr; } else if (root->lchild == nullptr)//左边为空 右边不为空 { root = root->rchild; delete p;//释放节点 } else if (root->rchild == nullptr)//右边为空 左边不为空 { root = root->lchild; delete p;//释放节点 } else { node*q = root->lchild; while (q->rchild != nullptr) { q = q->rchild;//继续往右找 } q->father->rchild = nullptr; q->father = root->father; q->lchild = root->lchild; q->rchild = root->rchild; root = q;//新的根节点 delete p;//释放之前的根节点 } } }
//mian.cpp
#include"Tree.h" int main() { srand((unsigned)time(NULL)); Tree<char> mytree; for (int i = 0; i < 10; ++i) { mytree.insert(rand() % 100); } std::cout << "前序遍历"<< std::endl; mytree.preOrder(mytree.getRoot()); std::cout << std::endl; std::cout << "中序遍历" << std::endl; mytree.inOrder(mytree.getRoot()); std::cout << std::endl; std::cout << "后序遍历" << std::endl; mytree.lasOrder(mytree.getRoot()); std::cout << std::endl; std::cout << "层次遍历" << std::endl; mytree.leverOrder(); std::cout << std::endl; std::cin.get(); return 0; }