这道题考察平衡二叉排列树，由于之前没有编写过平衡二叉排列树的代码，过程中出现了一些小错误 1.我存储的是高度，然后通过左右子树高度差来判断是否平衡，开始获取高度时未+1 2.root指针开始未赋值NULL
#include<iostream>#include<cstdlib>#include<cstdio>#PRagma warning(disable:4996)using namespace std;struct node { int data;//数据 node *l, *r;//左右孩子的指针 int h;//高度 node() { h = 1;l = r = NULL; }};int Geth(node* &p)//求p的h{ if (p->l == NULL && p->r == NULL) p->h = 1; else if (p->l == NULL &&p->r != NULL)p->h = p->r->h+1; else if (p->l != NULL &&p->r == NULL) p->h = p->l->h+1; else p->h = p->l->h > p->r->h ? p->l->h+1 : p->r->h+1; return p->h;}int differ(node* &p)//求p的平衡读(左子数高度-右子树高度)不能出现绝对值>1{ if (p->l == NULL && p->r == NULL) return 0; else if (p->l == NULL &&p->r != NULL)return 0-p->r->h; else if (p->l != NULL &&p->r == NULL)return p->l->h; else return p->l->h - p->r->h; return 0;}void L_Rotate(node* &p)//左旋{ node *temp = p->r; p->r = temp->l; Geth(p); temp->l = p; p = temp; Geth(p);}void R_Rotate(node* &p)//右旋{ node *temp = p->l; p->l = temp->r; Geth(p); temp->r = p; p = temp; Geth(p);}void insert_node(node* &root, int e)//插入节点{ if (root == NULL)//插入新节点 { root = (node *)malloc(sizeof(node)); root->data = e;root->h = 1; root->l = root->r = NULL; } else { if (root->data == e) return;//插入元素已存在，结束 else if (root->data > e) insert_node(root->l, e);//插入元素小于root的值，插入左子树 else insert_node(root->r, e);//cherub元素大于root的值，插入右子树 Geth(root); if (differ(root) > 1)//L { switch (differ(root->l)) { case 1:R_Rotate(root);//LL情况 break; case -1: L_Rotate(root->l);//LR情况 R_Rotate(root); break; } } else if (differ(root) < -1)//R { switch (differ(root->r)) { case -1:L_Rotate(root);//RR情况 break; case 1: R_Rotate(root->r);//RL情况 L_Rotate(root); break; } } }}int flag;void InOrderTraver(node* &root)//中序遍历，从小到大输出{ if (root == NULL) return; InOrderTraver(root->l); if (flag == 0) { printf("%d", root->data);flag++; } else printf(" %d", root->data); InOrderTraver(root->r);}int main(){ node *root = NULL;//root int N; scanf("%d", &N); root = NULL; while (N--) { int temp; scanf("%d", &temp); insert_node(root, temp); } /*flag = 0; InOrderTraver(root);*/ cout << root->data << endl;}新闻热点
疑难解答
