[점적 학습 - 데이터 구조 - 이 진 트 리] 이 진 트 리 에서 (min + max) / 2 이상 의 노드 를 찾 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define LEAF -1

typedef struct BTreeNode{
     BTreeNode* lchild;
     BTreeNode* rchild;
     int value;       
        
}BTreenode,*Btree;

BTreenode* createTree(){
     BTreeNode* T;
     int t;  
     scanf("%d",&t);
     if(t==LEAF){
          T = NULL;
     }else{
          T = (BTreeNode *) malloc(sizeof(BTreeNode));
          T->value = t;
          T->lchild = createTree();
          T->rchild = createTree();    
     }
     return T;
}

int f(BTreeNode * maxNode,BTreeNode * minNode){
    return (maxNode->value + minNode->value)/2;
}

//     key      
BTreeNode * findTheNode(BTreeNode* root,int key){
    if(root == NULL){
        return NULL;        
    }
    //     1:       。       
    if(key == root->value){
        return root;       
    }
    else if(key > root->value){
         if(root->rchild ==NULL){
              return root;           
         }else{
              BTreeNode * node =  findTheNode(root->rchild,key);
              return node->value >= key?node : root; 
         }  
    }
    //      2:       。       
    else{
         if(root->lchild == NULL){
              return root;                
         }
         BTreeNode * node = findTheNode(root->lchild,key);
         return node->value >= key? node:root; 
    }  
}

BTreeNode * getMinNode(BTreeNode * root){
    BTreeNode * min = root;
    while(min->lchild != NULL){
         min = min->lchild;   
    }
    return min;      
} 

BTreeNode * getMaxNode(BTreeNode * root){
    BTreeNode * max = root;
    while(max->rchild != NULL){
        max= max->rchild;
    } 
    return max;    
} 


main(){
    BTreeNode * root,* min,* max,*result;
    int key;
    root = createTree();
    min =  getMinNode(root);
    max =  getMaxNode(root);
    key =  f(min,max);
    printf("min:%d ,max:%d,f:%d
",min->value,max->value,key); result = findTheNode(root,key); printf("result :%d
",result->value); system("pause"); return 0; }

좋은 웹페이지 즐겨찾기