1135 Is It A Red-Black Tree (30 分) 判断红黑树

骑猪看日落 2024-04-17 20:48 46阅读 0赞

1135 Is It A Red-Black Tree (30 分)

There is a kind of balanced binary search tree named **red-black tree** in the data structure. It has the following 5 properties:

*  (1) Every node is either red or black.
 *  (2) The root is black.
 *  (3) Every leaf (NULL) is black.
 *  (4) If a node is red, then both its children are black.
 *  (5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

<table> 
 <thead> 
  <tr> 
   <th><img alt="rbf1.jpg" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tL2VmZjgwYmQ0LWM4MzMtNDgxOC05Nzg2LTgxNjgwZDFiMzA0YS5qcGc?x-oss-process=image/format,png"></th> 
   <th><img alt="rbf2.jpg" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tL2IxMTE4NGRmLWVhYWItNDUxYy1iN2Q0LTdmYzFkYzgyYjAyOC5qcGc?x-oss-process=image/format,png"></th> 
   <th><img alt="rbf3.jpg" src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzYyNWM1MzJiLTIyZmMtNDdiOS04MGVhLTA1MzdjZjAwZDkyMi5qcGc?x-oss-process=image/format,png"></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Figure 1</td> 
   <td>Figure 2</td> 
   <td>Figure 3</td> 
  </tr> 
 </tbody> 
</table>

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: ###

Yes
    No
    No

**题意：**给定一棵树的前序遍历，负值为红色，判断是否为红黑树。

红黑树的要求：1根节点为黑色；2每个红色结点的子节点为黑色；3点到叶子结点的黑色数相同

**思路：**一开始以为红黑树必是AVL，傻乎乎调整了半年，然而并不需要... 她只是一棵BST...

首先常规BST插入结点操作，然后以此判断条件123

#include<stdio.h>
    #include<math.h>
    #include<string>
    #include<vector>
    #include<string.h>
    #include<iostream>
    #include<sstream>
    #include<algorithm>
    using namespace std;
    int color[100005];
    struct node
    {
    	int data;
    	node *l,*r;
    };
    node *insert(node *root,int data)
    {
    	if(root==NULL)
    	{
    		root=new node();
    		root->data=data;
    		root->l=root->r=NULL;
    	}
    	else if(data<root->data)
    	root->l=insert(root->l,data);
    	else
    	root->r=insert(root->r,data);
    	return root;
    }
    bool dfs(node *root)
    {
    	if(root==NULL) return true; 
    	if(color[root->data])
    	{
    		if(root->l!=NULL&&color[root->l->data])
    		return false;
    		if(root->r!=NULL&&color[root->r->data])
    		return false;
    	}
    	return dfs(root->l)&&dfs(root->r);
    }
    int getNum(node *root) 
    {
    	if (root==NULL) return 0;
    	int left=getNum(root->l);
    	int right=getNum(root->r);
    	return color[root->data]==0 ? max(left,right)+1 : max(left,right);
    }
    bool judge(node *root) 
    {
    	if(root==NULL) return true; 
    	int left=getNum(root->l);
    	int right=getNum(root->r);
    	if(left!=right) return false;
    	return judge(root->l)&&judge(root->r);
    }
    int main()
    {
    	int t,n,x,i;
    	scanf("%d",&t);
    	while(t--)
    	{
    		memset(color,0,sizeof color);
    		node *root=NULL;
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&x);
    			if(x<0) x=-x,color[x]=1;
    			root=insert(root,x);
    		}		
    		if(color[root->data]==1)//判断根节点为黑
    		printf("No\n");
    		else
    		{
    			if(dfs(root)&&judge(root))
    			printf("Yes\n");
    			else
    			printf("No\n");
    		}
    	}	
    }