- // 树的数据结构表示有三种形式: 双亲表示法, 孩子表示法, 孩子兄弟表示法 (可以将树化为二叉树)
- // 双亲表示法, 这里的树结构使用一维数组表示, 所以类型为 int 指向下标
- template<class T>
- struct pNode {
- T data;
- int parent;
- };
- // 孩子表示法, 由于孩子数量不定, 采用一维数组与单链表结合的方法
- template<class T>
- struct cNode {
- int child;
- cNode* next;
- };
- // 孩子兄弟表示法
- template<class T>
- struct TNode {
- T data;
- TNode<T>* fistchild;
- TNode<T>* rightsib;
- };
- // 二叉树的存储结构可以是一维数组 (使用二叉树的性质存储), 更多的使用链式结构, 分为二叉和三叉链表, 二叉链表缺点是不容易找双亲
- // 二叉树的遍历分为: 前序遍历, 中序遍历, 后序遍历, 层序遍历
- // 二叉树的实现:
- template<class T>
- struct BiNode {
- T data;
- BiNode* lch;
- BiNode* rch;
- };
- // 各功能在类外实现
- template<class T>
- class BiTree {
- private:
- void Create(BiNode<T>*& R, T data[], int i,int n);
- void Release(BiNode<T>* R);
- public:
- BiNode<T>* root;
- BiTree(T data[],int n); // 构造函数创建一个二叉树
- void PreOrder(BiNode<T>* R); // 前序遍历
- void InOrder(BiNode<T>* R); // 中序遍历
- void PostOrder(BiNode<T>* R); // 后序遍历,
- void LevelOrder(BiNode<T>* R); // 层序遍历
- ~BiTree() {
- }
- };
- template<class T>
- void BiTree<T>::Create(BiNode<T>*& R, T data[], int i,int n) {
- if (i<=n) {
- R = new BiNode<T>;
- R->data = data[i - 1];
- R->lch = R->rch = NULL;
- Create(R->lch, data, 2 * i,n);
- Create(R->rch, data, 2 * i + 1,n);
- }
- }
- template<class T>
- BiTree<T>::BiTree(T data[],int n) {
- Create(root, data, 1,n);
- };
- // 前序中序后序递归实现方法只是输出的次序不同, 方式相同, 输出在递归前面表示递归时运行, 在递归后面表示回溯时运行
- template<class T>
- void BiTree<T>::PreOrder(BiNode<T>* R) {
- if (R != NULL) {
- cout <<R->data <<" ";
- PreOrder(R->lch);
- PreOrder(R->rch);
- }
- }
- template<class T>
- void BiTree<T>::InOrder(BiNode<T>* R) {
- if (R != NULL) {
- InOrder(R->lch);
- cout <<R->data <<" ";
- InOrder(R->rch);
- }
- }
- template<class T>
- void BiTree<T>::PostOrder(BiNode<T>* R) {
- PostOrder(R->lch);
- PostOrder(R->rch);
- cout <<R->data <<" ";
- }
- template<class T>
- void BiTree<T>::LevelOrder(BiNode<T>* R) {
- BiNode<T>* queue[5];
- int f = 0, r = 0;
- if (R != NULL) {
- queue[++r] = R;
- }
- while (f != r) {
- BiNode<T>* p = queue[++f];
- cout <<p -> data;
- if (p->lch != NULL) {
- queue[++r] = p->lch;
- }
- if (p->rch != NULL) {
- queue[++r] = p->rch;
- }
- }
- }
- template<class T>
- void BiTree<T>::Release(BiNode<T>* R) {
- // 后序遍历删除
- if (R != NULL) {
- Release(R->lch);
- Release(R->rch);
- delete R;
- }
- }
- template<class T>
- BiTree<T>::~BiTree() {
- Release(root);
- }
来源: http://www.bubuko.com/infodetail-3360555.html