7-3 是否完全二叉搜索树

7-3 是否完全二叉搜索树

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果

#include #include #include #include #include using namespace std;struct Node { int val, depth; Node *left; Node *right; Node() { val = 0; depth = 0; left = right = NULL; }};struct BST { Node *root; int cnt, inorder[25], maxdep; void init() { root = new Node; cnt = 0; maxdep = 0; } void insert(int x) { Node *t = root, *fa = root; int depth = 0; while (t != NULL) { depth++; fa = t; if (x > (t->val)) t = (t->left); else t = (t->right); } t = new Node; if (x > fa->val) fa->left = t; else fa->right = t; t->val = x; t->depth = depth; maxdep = max(maxdep, depth); } void bfs() { bool ok = true; queue q; q.push(root->left); bool flag = false; while (!q.empty()) { Node *t = q.front(); q.pop(); inorder[++cnt] = t->val; if (t->depth == maxdep) continue; if (t->depth < maxdep - 1) { if (t->left != NULL) q.push(t->left); else ok = false; if (t->right != NULL) q.push(t->right); else ok = false; } else if (t->depth == maxdep - 1) { if (t->left != NULL && t->right != NULL) { q.push(t->left); q.push(t->right); if (flag) ok = false; } else if (t->left != NULL && t->right == NULL) { if (flag) ok = false; flag = true; q.push(t->left); } else if (t->left == NULL && t->right != NULL) { flag = true; ok = false; q.push(t->right); } else flag = true; } } printf("%d", inorder[1]); for (int i = 2; i <= cnt; i++) printf(" %d", inorder[i]); printf("\n"); if (ok) printf("YES\n"); else printf("NO\n"); }}bst;int main() { int n, t; bst.init(); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &t); bst.insert(t); } bst.bfs(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。