浙大pta:Build A Binary Search Tree

4709 ワード

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

  • Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

    Input Specification:


    Each input file contains one test case. For each case, the first line gives a positive integer N (\le≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format  left_index right_index , provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

    Output Specification:


    For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

    Sample Input:

    9
    1 6
    2 3
    -1 -1
    -1 4
    5 -1
    -1 -1
    7 -1
    -1 8
    -1 -1
    73 45 11 58 82 25 67 38 42
    

    Sample Output:

    58 25 82 11 38 67 45 73 42

    1. binary search tree(BST)

    2. value ,

    3. value BST

    4. levelorder

    1. BST , i ( 0 ) BST i node

    2. value BST , visit node , ,

    , BST

    /**********************************************************
     * Author        : XiaoXiong
     * Email         : [email protected]
     * Create time   : 2016-10-28 18:14
     * Last modified : 2016-10-28 18:14
     * Filename      : 5.2.c
     * Description   : 
     * *******************************************************/
    
    #include
    #include
    #include
    
    typedef struct node *tree;
    struct node{
    	int value;
    	tree left;
    	tree right;
    };
    
    int *val;
    int k=0;
    
    void sort(int *val, int n);
    void levelOrder(tree T,int n);
    void insertValue(tree T);
    
    int main()
    {
    	int n;
    	int i;
    	int l, r;
    	tree T;
    
    	scanf("%d", &n);
    	getchar();
    
    	T = (tree)malloc(sizeof(struct node)*n);
    	val = (int *)malloc(sizeof(int)*n);
    
    	if(n==0)
    		return 1;
    
    	/*** index ****/
    	for(i = 0; i < n; i++){
    		scanf("%d %d", &l, &r);
    		getchar();
    		if(l != -1){
    			T[i].left = T+l;
    		}
    		else{
    			T[i].left = NULL;
    		}
     		if(r != -1){
    			T[i].right = T+r;
    		}
    		else{
    			T[i].right = NULL;
    		}
    	}
    	
    	for(i = 0; i < n; i++){
    		scanf("%d", &val[i]);
    		getchar();	
    	}
    
    	sort(val,n);
    	insertValue(T);
    	levelOrder(T,n);
    		
    	return 0;
    }
    
    /********** ************/
    void insertValue(tree T)
    {
    	if(T){
    		insertValue(T->left);
    		T->value=val[k];
    		k++;
    		insertValue(T->right);
    	}	
    	return ;
    }
    
    /************* **************/
    void levelOrder(tree T, int n)
    {
    	int i=0,t=1;
    	tree* queue;
    
    	queue = (tree *)malloc(sizeof(tree)*n);
    
    	if(T){
    		queue[0]=T;
    	}
    
    	for(i=0;ivalue);
    		}
    		else{
    			printf(" %d", queue[i]->value);
    		}
    		if(queue[i] -> left){
    			queue[t++] = queue[i]->left;
    		}
    		if(queue[i] -> right){
    			queue[t++] = queue[i]->right;
    		}
    	}	
    }
    
    /*** ***/
    void sort(int *val, int n)
    {
    	int i=0,j=0;
    	int tmp;
    	int min;
    	for(i=0;i