实验内容及要求：
从键盘输入若干两两互不相同的非0整数，直到输入0时停止。将输入的所有非0整数按输入次序插入二叉排序树来构造平衡的二叉排序树。输出平衡的二叉排序树的先序和中序递归遍历次序；按中序递归遍历次序输出平衡的二叉排序树各结点的平衡因子。注意：二叉树结点存储结构中应增加平衡因子域。
实验目的：掌握平衡二叉排序的建立方法（学会LL,LR,RR,RL四种旋转类型）；掌握二叉排序树的特性。
不说别的，直接上源码
#includeusing namespace std; typedef int ElemTp; // 定义二叉链 typedef struct Node { ElemTp data; // 数据域 int bf; // 平衡因子bf=hl-hr,左树高减右树高 struct Node *lchild; // 左指针 struct Node *rchild; // 右指针 } * BiT, BTNode; // struct Node 的别名 // 先序遍历输出data void preOrder(BTNode *BT) { if (BT != NULL) // 判断不为空 { cout << BT->data << " "; // 访问根节点 preOrder(BT->lchild); // 递归,先序遍历左子树 preOrder(BT->rchild); // 递归,先序遍历右子树 } } // 中序遍历输出data void midOrder(BTNode *BT) { if (BT != NULL) // 判断不为空 { midOrder(BT->lchild); // 递归,中序遍历左子树 cout << BT->data << " "; // 访问根节点 midOrder(BT->rchild); // 递归,中序遍历右子树 } } // 中序遍历输出平衡因子bf void midOrderbf(BTNode *BT) { if (BT != NULL) // 判断不为空 { midOrderbf(BT->lchild); // 递归,中序遍历左子树 cout << BT->data << "--" << BT->bf << endl; // 访问根节点 midOrderbf(BT->rchild); // 递归,中序遍历右子树 } } // 平衡二叉排序树插入结点算法 void insert(BiT &BT, BiT s) { // step a.在查找s结点的插入位置的过程中,记下离s结点最近且平衡因子不等于0的结点,令指针a指向该结点； BiT p, a, f; // 辅助指针 BiT b, c, fa; // 辅助指针2,用于LR,RL型平衡操作 a = BT; // 溯回指针 p = BT; // 主动指针 f = NULL; // 指向插入结点的双亲指针 b = c = NULL; // 初始赋值为NULL s->bf = 0; // 将待插入结点的bf赋值0 while (p) { if (p->bf != 0) // 主动指针寻找离s结点最近且平衡因子不等于0的结点 { fa = f; // fa为*a的双亲结点 a = p; } f = p; // 从动指针指向双亲 if (s->data < p->data) // 判断主动指针移动方向 p = p->lchild; // 插入结点key小于子树根节点,主动指针向左儿子移动 else p = p->rchild; // 插入结点key大于子树根节点,主动指针向右儿子移动 } if (!f) // 特殊情况,树为空树,待插入结点定为根节点 BT = s; else if (s->data < f->data) f->lchild = s; // 插入结点key小于双亲,插入为左儿子 else f->rchild = s; // 插入结点key大于双亲,插入为右儿子 // step b.的C语言算法修,改自a至s路径上所有结点的平衡因子 // 注意: *a至*s路径上除*a外, 其余结点的bf域均为0 if (a) // a为NULL说明是空树插入第1个结点 { if (s->data < a->data) { p = a->lchild; a->bf += 1; } // 是在*a的左子树上插入 else { p = a->rchild; a->bf -= 1; } // 是在*a的右子树上插入 while (p != s) if (s->data < p->data) { p->bf = 1; p = p->lchild; // 是在*a的左子树上插入 } else { p->bf = -1; p = p->rchild; // 是在*a的右子树上插入 } // 以下为step c.判断以*a为根的子树是否失衡，若失衡，根据4种旋转类型进行调整，使*a的平衡因子=0且*a子树高度与原*a子树高度相同。 if (a->bf == 2) if (a->lchild->bf == 1) // LL型调整算法 { b = a->lchild; a->lchild = b->rchild; a->bf = 0; b->rchild = a; b->bf = 0; //以下实现*b与原*a的双亲结点连接 if (!fa) BT = b; //a->parent为*a的双亲结点地址 else if (b->data < fa->data) fa->lchild = b; else fa->rchild = b; } else // LR型调整算法 { b = a->lchild; c = b->rchild; a->lchild = c->rchild; b->rchild = c->lchild; c->lchild = b; c->rchild = a; switch (c->bf) { case 0: a->bf = b->bf = 0; break; case 1: a->bf = -1; b->bf = 0; break; case -1: a->bf = 0; b->bf = 1; break; } c->bf = 0; //以下实现*c与原*a的双亲结点连接 if (!fa) BT = c; // a->parent为*a的双亲结点地址 else if (c->data < fa->data) fa->lchild = c; else fa->rchild = c; } if (a->bf == -2) if (a->rchild->bf == -1) // RR型调整算法 { b = a->rchild; a->rchild = b->lchild; a->bf = 0; b->lchild = a; b->bf = 0; // 以下实现*b与原*a的双亲结点连接 if (!fa) BT = b; // fa为*a的双亲结点地址 else if (b->data < fa->data) fa->lchild = b; else fa->rchild = b; } else // RL型调整算法 { b = a->rchild; c = b->lchild; a->rchild = c->lchild; b->lchild = c->rchild; c->lchild = a; c->rchild = b; switch (c->bf) { case 0: a->bf = b->bf = 0; break; case 1: a->bf = 0; b->bf = -1; break; case -1: a->bf = 1; b->bf = 0; break; } c->bf = 0; // 以下实现*c与原*a的双亲结点连接 if (!fa) BT = c; // fa为*a的双亲结点地址 else if (c->data < fa->data) fa->lchild = c; else fa->rchild = c; } } } int main() { ElemTp K; BiT BT, p; BT = NULL; // 创建空树 cout << "输入：" << endl; cin >> K; while (K) { p = new BTNode; p->lchild = NULL; p->rchild = NULL; p->data = K; insert(BT, p); cin >> K; } preOrder(BT); // 先序输出data cout << endl; midOrder(BT); // 中序输出data cout << endl; midOrderbf(BT); // 中序输出bf return 0; }
仅供参考
