UVa122关于二叉树的代码问题（竞赛代码不懂）

Question

 #include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
char s[1<<10];                                       // 存放输入进去的字符串
bool failed=false;                                   // 用开关表示输出树还是输出not complete
struct Node{                                           //结构体 树的节点
      bool have_value;                              // 是否有值
      int v;                                                 // 值为多少
      Node *left, *right;                            // 每一个节点都可能会有一个左子树和一个                                                                   右子树
      Node(): have_value(false),left(NULL),right(NULL) {}     //构造函数 默认初始值
};
Node *root;                                        //根节点

Node* newnode(){ return new Node(); }   //！！为什么newnode()函数传回的值是
                                                                                                                                                Node*？ Node*不是值吗？

void addnode(int v,char *s){
      int n = strlen(s);
      Node *u = root;                   //！！在此处新建的节点u，root将什么传给了u，                                                               是地址还是值？
      for(int i = 0 ; i<n ; i++){
          if(s[i]=='L'){
             if(u->left==NULL) u->left = newnode();
             u = u->left;
          }
          if(s[i]=='R'){
             if(u->right == NULL) u->right = newnode();
             u = u->right;
          }
      }
      if(u->have_value==true) failed=true;
           u->v = v;
           u->have_value = true;
}

void remove_tree(Node* u){
     if(u==NULL)  return;
     if(u->left) remove_tree(u->left);
     if(u->right) remove_tree(u->right);
     delete u;
}

bool read_input(){
       int v;
       failed = false;
       remove_tree(root);
       root = newnode();
       for(;;){
            if( scanf("%s",s)!=1 ) return false;
            if(!strcmp(s,"()")) break;
            sscanf(&s[1],"%d",&v);
            addnode(v,strchr(s,',')+1);
       }
       return true;
}

bool bfs(vector<int> &ans){
     queue<Node*>q;
     ans.clear();
     q.push(root);
     while(!q.empty()){
         Node *u = q.front() ; q.pop();
         if(!u->have_value) return false;
         ans.push_back(u->v);
         if(u->left!=NULL) q.push(u->left);
         if(u->right!=NULL)  q.push(u->right);
     }
     return true;
}

int main(){
    freopen("in3.txt","r",stdin);
    vector<int>ans;
    while(read_input()){
          if(!bfs(ans)) failed = 1;
          if(failed) printf("not complete\n");
          else{
              for(int i = 0 ; i<ans.size() ; i++){
                   if(i) printf(" ");
                   printf("%d",ans[i]);
              }
              printf("\n");
          }
    }
    return 0;
}

两处有很多问题想问：
1. 在newnode()处，函数为什么传回的值是Node* ， 在我仅有的一点基 础内，只明白*Node应该是个值，而&Node才是地址。

                             2. 在addnode()下 Node*u = root是什么操作？ 是将根节点的什么东西
                                 传给u？ 是地址吗？为什么可以这样做？

Answer 1

看你的问题描述，你可能需要补一补指针方面的知识
1、new用于开辟内存空间保存变量，它的返回类型是指向这个内存空间的指针，例如int* a = new int()就是开辟一块内存，保存int变量，返回值a是指向这个变量的指针；
2、Node* u = root;指针的赋值，指针是一类特殊变量，它保存的是指针所指向变量的地址，这个赋值就是把root保存的地址赋给了u，这样root和u保存相同地址，两者共同指向根节点；