PTA A1123

AVL模版题+判断是否是层序遍历

//
//  main.cpp
//  test6
//
//  Created by Jacky Roth on 2019/2/28.
//  Copyright © 2019 Jacky Roth. All rights reserved.
//
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace  std;
int N;
struct tree {int data,hight;tree* lchild;tree* rchild;
};tree* creat_node(int x){tree* root=new tree();root->data=x;root->lchild=NULL;root->rchild=NULL;root->hight=1;return root;
}int get_h(tree* root){if (root==NULL) {return 0;}return root->hight;
}void updateh(tree* root){root->hight=max(get_h(root->lchild), get_h(root->rchild))+1;
}int get_balance(tree* root){return get_h(root->lchild)-get_h(root->rchild);
}void L(tree* &root){tree* temp=root->rchild;root->rchild=temp->lchild;temp->lchild=root;updateh(root);updateh(temp);root=temp;
}void R(tree* &root){tree* temp=root->lchild;root->lchild=temp->rchild;temp->rchild=root;updateh(root);updateh(temp);root=temp;
}void creat_tree(tree* &root,int data){if (root==NULL) {root=creat_node(data);return;}if (datadata) {creat_tree(root->lchild, data);updateh(root);if (get_balance(root)==2) {if (get_balance(root->lchild)==1) {R(root);}else{L(root->lchild);R(root);}}}else{creat_tree(root->rchild, data);updateh(root);if (get_balance(root)==-2) {if (get_balance(root->rchild)==-1) {L(root);}else{R(root->rchild);L(root);}}}
}bool level(tree* root){bool tag=1;queueq;tree* top;q.push(root);while (!q.empty()) {top=q.front();q.pop();if (!top) {break;}printf("%d",top->data);if (--N) {printf(" ");}q.push(top->lchild);q.push(top->rchild);}while (!q.empty()) {top=q.front();q.pop();if (top) {tag=0;printf("%d",top->data);if (--N) {printf(" ");}if (top->lchild) {q.push(top->lchild);}if (top->rchild) {q.push(top->rchild);}}}printf("\n");return tag;
}int main(int argc, const char * argv[]) {int data;tree* root=NULL;scanf("%d",&N);for (int i=0; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！