1135 Is It A Red-Black Tree
发布时间:2020-12-14 03:48:45 所属栏目:大数据 来源:网络整理
导读: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
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:
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:
Yes
No
No
?
题意:
给出k个二叉搜索树的前序序列,判断该树是否为红黑树。
?
思路:
红黑树的定义:
红黑树的判断:
代码:
#include <cstdio> #include <algorithm> using namespace std; #define BLACK 1 #define RED 0 struct Node{ int val; int color; Node *lchild,*rchild; Node(int v){ val=v>0?v:-v; color=v>0?BLACK:RED; lchild=rchild=nullptr; } }; void insert(Node* &root,int val) { if(root==nullptr){ root=new Node(val); return; } if(abs(val)<root->val) insert(root->lchild,val); else insert(root->rchild,val); } //深度遍历,计算黑色结点的个数以及判断是否会出现连续两个红色结点 int totalBlackCnt=0; bool flag=true; void dfs(Node* root,int cnt) { if(root==nullptr){ if(cnt!=totalBlackCnt) flag=false; return; } if(root->color==BLACK) cnt++; else{ if(root->lchild && root->lchild->color==RED) flag=false; if(root->rchild && root->rchild->color==RED) flag=false; } //printf("val:%d color:%d cnt:%dn",root->val,root->color,cnt); dfs(root->lchild,cnt); dfs(root->rchild,cnt); } int main() {int k,n,val; scanf("%d",&k); while(k--){ scanf("%d",&n); Node* root=nullptr; for(int i=0;i<n;i++){ scanf("%d",&val); insert(root,val); } if(root->color==RED){ printf("Non"); continue; } totalBlackCnt=0;//记录从根结点到任意一个叶结点的简单路径上黑色结点的个数 //此处计算最左端的路径 Node* p=root; while(p){ if(p->color==BLACK) totalBlackCnt++; p=p->lchild; } flag=true;//初始化 dfs(root,0); printf("%sn",flag?"Yes":"No"); } return 0; } ?
?【疑问】
按照我自己的想法,dfs()函数我是这么写的,然而这么写会有两个测试点通不过!还没搞清楚!!!
void dfs(Node* root,int cnt) { if(root==nullptr) return; if(root->color==BLACK) cnt++; else{ if(root->lchild && root->lchild->color==RED) flag=false; if(root->rchild && root->rchild->color==RED) flag=false; } if(root->lchild==nullptr && root->rchild==nullptr){ if(cnt!=totalBlackCnt) flag=false; } //printf("val:%d color:%d cnt:%dn",root->color,cnt); dfs(root->lchild,cnt); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |