mfc平衡二叉树绘制-源码（节点动态插入、动态删除、前序遍历、中序遍历、后续遍历动态显示）

#include "pch.h" #include <string> #include <cstdlib> #define OK 1 #define ERROR 0 using namespace std; typedef int Status; static string strOrderResult = ""; // 用于返回多种遍历结果 // 平衡二叉树结点结构 template <typename T> struct AvlNode { T data; // 结点数据 AvlNode<T>* left; // 左子节点指针 AvlNode<T>* right; // 右子节点指针 int height; // 结点所在高度 AvlNode<T>(const T theData) : data(theData), left(NULL), right(NULL), height(0) { } // 构造方法 }; /* 链队列结点结构（用于层序遍历） */ template <typename T> struct QNode { AvlNode<T>* t; // 结点数据域 struct QNode<T>* next; // 结点指针域 }; /* 链队列结构（用于层序遍历） */ template <typename T> struct LinkQueue { QNode<T>* front; // 队首指针 QNode<T>* rear; // 队尾指针 }; //------------- AvlTree类 ------------- template <typename T> class AvlTree { public: AvlNode<T>* root; AvlTree<T>() : root(NULL) { } ~AvlTree<T>() { } /* 初始化链队列函数 */ template <typename T> Status InitQueue(LinkQueue<T>& Q) { // 创建一个带附加头结点的空链队列 Q.front = Q.rear = (QNode<T>*)malloc(sizeof(QNode<T>)); if (!Q.front) { return ERROR; } Q.front->next = NULL; return OK; } /* 进队函数 */ /* e：插入元素 */ template <typename T> Status EnQueue(LinkQueue<T>& Q, AvlNode<T>* e) { // 将元素e插入到链队列中 QNode<T>* p; p = (QNode<T>*)malloc(sizeof(QNode<T>)); if (!p) { return ERROR; } p->t = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } /* 出队函数 */ /* e：出队元素 */ template <typename T> Status DeQueue(LinkQueue<T>& Q, AvlNode<T>*& e) { // 出队，将出队元素放入e中 QNode<T>* p; if (Q.rear == Q.front) { return ERROR; } p = Q.front->next; e = p->t; Q.front->next = p->next; if (Q.rear == p) { Q.rear = Q.front; } free(p); return OK; } // 获取树的最大值结点 template <typename T> AvlNode<T>* FindMax(AvlNode<T>* t) const { if (t == NULL) return NULL; if (t->right == NULL) return t; return FindMax(t->right); } // 返回树的最小值结点 template <typename T> AvlNode<T>* FindMin(AvlNode<T>* t) const { if (t == NULL) return NULL; if (t->left == NULL) return t; return FindMin(t->left); } // 获取树的高度 template <typename T> int GetHeight(AvlNode<T>* t) { if (t == NULL) return -1; else return t->height; } //查找结点 template <typename T> bool Contains(AvlNode<T>* t, const T x) const { if (t == NULL) return false; if (x < t->data) return Contains(t->left, x); else if (x > t->data) return Contains(t->right, x); else return true; } // 判断是否为完全二叉树 template <typename T> bool IsCompleteTree(AvlNode<T>* t) { if(!t) return true; LinkQueue<T> Q; AvlNode<T>* p; p=t; InitQueue(Q);//初始化队列 EnQueue(Q,p);//根结点入队 while(Q.front != Q.rear){ DeQueue(Q,p); if(!p) break;//读到空指针则停止循环 EnQueue(Q,p->left);//左孩子入队 EnQueue(Q,p->right);//右孩子入队 } while(Q.front != Q.rear){//检查此时队列中是否还有未访问到的结点 DeQueue(Q,p); if(p) return false; } return true; } //单旋转 //左左插入导致的不平衡 template <typename T> AvlNode<T>* LL(AvlNode<T>* t) { AvlNode<T>* q = t->left; t->left = q->right; q->right = t; t = q; t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1; q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1; return q; } //单旋转 //右右插入导致的不平衡 template <typename T> AvlNode<T>* RR(AvlNode<T>* t) { AvlNode<T>* q = t->right; t->right = q->left; q->left = t; t = q; t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1; q->height = max(GetHeight(q->left), GetHeight(q->right)) + 1; return q; } //双旋转 //插入点位于t的左儿子的右子树 template <typename T> AvlNode<T>* LR(AvlNode<T>* t) { //双旋转可以通过两次单旋转实现 //对t的左结点进行RR旋转，再对根节点进行LL旋转 RR(t->left); return LL(t); } //双旋转 //插入点位于t的右儿子的左子树 template <typename T> AvlNode<T>* RL(AvlNode<T>* t) { LL(t->right); return RR(t); } template <typename T> void InsertAvlNode(AvlNode<T>*& t, T x) { if (t == NULL) t = new AvlNode<T>(x); else if (x < t->data) { InsertAvlNode(t->left, x); //判断平衡情况 if (GetHeight(t->left) - GetHeight(t->right) > 1) { //分两种情况 左左或左右 if (x < t->left->data)//左左 t = LL(t); else //左右 t = LR(t); } } else if (x > t->data) { InsertAvlNode(t->right, x); if (GetHeight(t->right) - GetHeight(t->left) > 1) { if (x > t->right->data) t = RR(t); else t = RL(t); } } else ;//数据重复 t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1; } template <typename T> bool DeleteAvlNode(AvlNode<T>*& t, T x) { //t为空 未找到要删除的结点 if (t == NULL) return false; //找到了要删除的结点 else if (t->data == x) { //左右子树都非空 if (t->left != NULL && t->right != NULL) {//在高度更大的那个子树上进行删除操作 //左子树高度大，删除左子树中值最大的结点，将其赋给根结点 if (GetHeight(t->left) > GetHeight(t->right)) { t->data = FindMax(t->left)->data; DeleteAvlNode(t->left, t->data); } else//右子树高度更大，删除右子树中值最小的结点，将其赋给根结点 { t->data = FindMin(t->right)->data; DeleteAvlNode(t->right, t->data); } } else {//左右子树有一个不为空，直接用需要删除的结点的子结点替换即可 AvlNode<T>* old = t; t = t->left ? t->left : t->right;//t赋值为不空的子结点 delete old; } } else if (x < t->data)//要删除的结点在左子树上 { //递归删除左子树上的结点 DeleteAvlNode(t->left, x); //判断是否仍然满足平衡条件 if (GetHeight(t->right) - GetHeight(t->left) > 1) { if (GetHeight(t->right->left) > GetHeight(t->right->right)) { //RL双旋转 t = RL(t); } else {//RR单旋转 t = RR(t); } } else//满足平衡条件 调整高度信息 { t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1; } }