PAT 1135 Is It A Red-Black Tree
There is a kind of balanced binary search tree named?red-black tree?in the data structure. It has the following 5 properties:
For example,the tree in Figure 1 is a red-black tree,while the ones in Figure 2 and 3 are not.
For each given binary search tree,you are supposed to tell if it is a legal red-black tree. Input Specification:Each input file contains several test cases. The first line gives a positive integer K (≤30) which is the total number of cases. For each case,the first line gives a positive integer N (≤30),the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers,we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1,2 and 3. Output Specification:For each test case,print in a line "Yes" if the given tree is a red-black tree,or "No" if not. Sample Input:3 9 7 -2 1 5 -4 -11 8 14 -15 9 11 -2 1 -7 5 -4 8 14 -15 8 10 -7 5 -6 8 15 -11 17 Sample Output:
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 #define max(a,b)((a>b)?(a):(b)) 7 #define abs(a)((a<0)?(0-a):(a)) 8 9 struct Node{ 10 int val; 11 bool isRed; 12 Node *left,*right; 13 }; 14 15 Node* insert(Node* root,int val){ 16 if(root==NULL){ 17 root = new Node(); 18 root->val = val; 19 root->isRed = val<0 ? true : false; 20 root->left = root->right = NULL; 21 } 22 else if(abs(val)<abs(root->val)) root->left = insert(root->left,val); 23 else root->right = insert(root->right,val); 24 return root; 25 } 26 //判断条件3,4 27 bool isRedBlack(Node* root){ 28 if(root==NULL) return true; 29 if(root->isRed && ((root->left!=NULL && root->left->isRed)||(root->right!=NULL && root->right->isRed))) return false; 30 return isRedBlack(root->left) && isRedBlack(root->right); 31 } 32 //计算路径上黑节点的个数 33 int pathLength(Node* root){ 34 if(root==NULL) return 0; 35 int l=pathLength(root->left),r=pathLength(root->right); 36 return root->isRed ? max(l,r) : max(l,r)+1; 37 } 38 //判断条件5 39 bool pathEqual(Node* root){ 40 if(root==NULL) return true; 41 int l=pathLength(root->left),r=pathLength(root->right); 42 if(l!=r) return false; 43 return pathEqual(root->left) && pathEqual(root->right); 44 } 45 46 int main(){ 47 int n,i,j; 48 scanf("%d",&n); 49 for(i=0; i<n; i++){ 50 int cnt; 51 scanf("%d",&cnt); 52 vector<int> v(cnt); 53 Node *root = NULL; 54 for(j=0; j<cnt; j++){ 55 scanf("%d",&v[j]); 56 root = insert(root,v[j]); 57 } 58 if(!root->isRed && isRedBlack(root) && pathEqual(root)) printf("Yesn"); 59 else printf("Non"); 60 } 61 return 0; 62 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |