acm ----树 ----problem 1

青旅半醒 2021-12-21 07:27 168阅读 0赞

数据结构：  二叉树

运用递归的方法构造二叉树，二叉树的根节点root代表一棵二叉树。

#include <cstdlib>
    #include <iostream>
    /*
      Name:          Binary Tree template 
      Copyright: 
      Author: 
      Date: 28-04-10 11:26
      Description:     construct a binary tree
    */
    
    using namespace std;
    /**tree structure*/
    struct TreeNode
    {
           int val;  //data area 
           TreeNode *left, *right;  //point area
    };
    /**insert a val to a tree, return the root of the tree*/
    TreeNode *InsertTree(TreeNode *root, int val )
    {
             TreeNode *newNode;
             if(root==NULL)   //border value 
             {
                           newNode=new TreeNode;
                           newNode->val=val;
                           newNode->left=NULL;
                           newNode->right=NULL;
                           return newNode;
             }
             if(val<=root->val)
             {
                           root->left=InsertTree(root->left,val);
             }
             else
             {
                           root->right=InsertTree(root->right,val);
             }
             
             return root;
    }
    /**linear time*/
    void DelTree(TreeNode *root)
    {
         if(root->left!=NULL) DelTree(root->left);
         if(root->right!=NULL) DelTree(root->right);
         delete root;
    }
    /**depth-first traversal*/
    void printTree(TreeNode *root, char offset[])
    {
         char str[81];
         printf("%s%d\n",offset,root->val);
         sprintf(str,"%s%s",offset," ");   //write format data to string
         
         if(root->left!=NULL)
             printTree(root->left,str);
         else
             printf("%s$\n",str);
         
         if(root->right!=NULL)
             printTree(root->right,str);
         else
             printf("%s$\n",str);
         
    }
    
    int main(int argc, char *argv[])
    {
        FILE *fin;
        TreeNode *root;
        int val;
        char inFile[30], str[81];
          
        scanf("%s",inFile);
        fin=fopen(inFile,"r");  //open file in current directory
        
        root=NULL;
        while(fscanf(fin,"%d",&val)!=EOF)   //scan all elem in the file
        {
              root=InsertTree(root,val);
        }
        fclose(fin);
        
        sprintf(str,"%s","");
        printTree(root,str);
        DelTree(root);
        system("PAUSE");
        return EXIT_SUCCESS;
    }

递归方法理解的还不够深刻。下一次从递归开始训练

转载于:https://www.cnblogs.com/ggppwx/archive/2010/04/28/1722986.html