這道題考察平衡二叉排列樹，由于之前沒有編寫過平衡二叉排列樹的代碼，過程中出現了一些小錯誤 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;}新聞熱點
疑難解答
