网站家建设培训学校,最近文章 wordpress,wordpress菜单怎么设置,珠海企业网站建设价格思路#xff1a; 考察的点是建立AVL树以及如何判断是否为满二叉树。
建立AVL树需要搞清楚LL、LR、RR、RL四种情况如何左旋和右旋#xff0c;如下#xff1a;
类型BF条件操作LLBF(root)2,BF(root-lchild)1root右旋LRBF(root)2,BF(root-lchild)-1先root-lchild左… 思路 考察的点是建立AVL树以及如何判断是否为满二叉树。
建立AVL树需要搞清楚LL、LR、RR、RL四种情况如何左旋和右旋如下
类型BF条件操作LLBF(root)2,BF(root-lchild)1root右旋LRBF(root)2,BF(root-lchild)-1先root-lchild左旋再root右旋RRBF(root)-2,BF(root-rchild)-1root左旋RLBF(root)-2,BF(root-rchild)1先root-rchild右旋再root左旋
接着是用bfs遍历判断是否为满二叉树 按照层序遍历的方式但遇到空结点也需要放入队列将各个结点放入队列中直到从队列拿出来的结点是空的。按照完全二叉树的定义只有最后一层才能是有空结点并且结点朝左排列。如果我们此时依次将队列前部的空结点全部拿出队列应该最后是空的此时证明是完全二叉树的。
#includebits/stdc.h
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;struct node {int data;int height;node* lchild;node* rchild;
};int getHeight(node* tnode)
{if (tnode NULL) return 0;else return tnode-height;
}void UpdateHeight(node* tnode)
{tnode-height max(getHeight(tnode-lchild), getHeight(tnode-rchild)) 1;
}int getBF(node* tnode)
{return getHeight(tnode-lchild) - getHeight(tnode-rchild);
}void L(node* tnode)
{node* temp tnode-rchild;tnode-rchild temp-lchild;temp-lchild tnode;UpdateHeight(tnode);UpdateHeight(temp);tnode temp;
}void R(node* tnode)
{node* temp tnode-lchild;tnode-lchild temp-rchild;temp-rchild tnode;UpdateHeight(tnode);UpdateHeight(temp);tnode temp;
}node* newnode(int v)
{node* tnode new node;tnode-data v;tnode-height 1;tnode-lchild tnode-rchild NULL;return tnode;
}void insert(node* root, int v)
{if (root NULL){root newnode(v);return;}if (v root-data){insert(root-lchild, v);UpdateHeight(root);if (getBF(root) 2){if (getBF(root-lchild) 1){R(root);}else if (getBF(root-lchild) -1){L(root-lchild);R(root);}}}else{insert(root-rchild, v);UpdateHeight(root);if (getBF(root) -2){if (getBF(root-rchild) -1){L(root);}else if (getBF(root-rchild) 1){R(root-rchild);L(root);}}}
}node* create()
{int n;cin n;node* root NULL;for (int i 0; i n; i){int t;cin t;insert(root, t);}return root;
}void bfs(node* root)
{vectorint res;queuenode* q;node* t;q.push(root);while (!q.empty()){t q.front();q.pop();res.emplace_back(t-data);if (t-lchild) q.push(t-lchild);if (t-rchild) q.push(t-rchild);}for (int i 0; i res.size(); i)if (i 0) cout res[0];else cout res[i];cout endl;
}void checkCompleteBinary(node* root)
{queuenode* q;node* t;q.push(root);while (!q.empty()){t q.front();q.pop();if (t NULL) break;q.push(t-lchild);q.push(t-rchild);}while (!q.empty() q.front() NULL)q.pop();if (q.empty()) cout YES;else cout NO;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);node* root create();bfs(root);checkCompleteBinary(root);return 0;
}
