hdu3999The order of a Tree(BST)
2713 단어 두 갈래 나무
As we know,the shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:
1. insert a key k to a empty tree, then the tree become a tree with
only one node;
2. insert a key k to a nonempty tree, if k is less than the root ,insert
it to the left sub-tree;else insert k to the right sub-tree.
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.
Input
There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.
Output
One line with n intergers, which are the order of a tree that generate the same tree with the least lexicographic.
Sample Input
4
1 3 4 2
Sample Output
1 3 2 4
Source
2011 Multi-University Training Contest 16 - Host by TJU
#include<stdio.h>
#include<malloc.h>
typedef struct tree
{
struct tree *lchilde,*rchilde;
int w;
}tree,*Tree;
void creaRoot(Tree &root)//
{
root=(Tree)malloc(sizeof(tree));
root->lchilde=root->rchilde=NULL;
}
void printTree(Tree root,int k)//
{
if(root==NULL) return ;//
if(k==0)
printf("%d",root->w);
else
printf(" %d",root->w);
printTree(root->lchilde,k+1);//
printTree(root->rchilde,k+1);//
}
void InTree(Tree &node,int x)// ， ，
{
Tree T;
if(node==NULL)// ，
{
T=(Tree)malloc(sizeof (tree));
T->w=x; T->lchilde=T->rchilde=NULL;//
node=T;
}
else// ，
{
if(x<=node->w)
InTree(node->lchilde,x);
else
InTree(node->rchilde,x);
}
}
int main()
{
Tree root;
int n,i,x;
while(scanf("%d",&n)>0)
{
if(n==0)continue;
creaRoot(root);
scanf("%d",&x);
root->w=x;
for(i=2;i<=n;i++)
{
scanf("%d",&x);
InTree(root,x);
}
printTree(root,0);
printf("
");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
