java - Java 中的 Tree 实现是否保存整个下一个节点 v/s 仅保存 C 中的地址

Question

注意在C版本中，只保存了节点的地址，即Node*，而在Java版本中，保存了整个Node。

这是否意味着运行的 Java 代码比 C 代码占用更多的内存？

C 版

#include <stdio.h>
#include <malloc.h>

typedef struct node
{
 int data;
 struct node* left;
 struct node* right;
}Node;
Node* root;

void inorder(Node* node)
{
 if(node == NULL)
  return;

 inorder(node->left);
 printf("%d ",node->data);
 inorder(node->right);
}

void insert(int data)
{
printf("inside insert, data == %d",data);    

 Node* node = malloc(sizeof(Node));
 node->data = data;
 node->left = NULL;
 node->right = NULL;

 if(root == NULL)
 {
     printf("inserting %d as root",node->data);
     root = node;
 }
 else
 { 
  Node* trav = root;
  Node* pretrav = root;
  while(trav != NULL)
  {
   pretrav = trav;
   if(node->data < trav->data)
    trav = trav->left;
   else
    trav = trav->right;
  }

  if(node->data < pretrav->data)
  {
      printf("inserting %d to the left of %d",node->data, pretrav->data);
   pretrav->left = node;   
  }
  else
  {
      printf("inserting %d to the right of %d",node->data, pretrav->data);
   pretrav->right = node;   
  }
 }  
}

int main(void)
{
 int a[] = {10,5,15,1,20,100};
 int i = 0; 

 for(i = 0;i<sizeof(a)/sizeof(a[0]);i++)
 {
  insert(a[i]);
  printf("\n");
 }

 inorder(root);

 return 0;
}

Java 版本

package lastcommon;

public class TreeExample {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Tree tree = new Tree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(1);
        tree.insert(20);
        tree.insert(100);

        System.out.println("Printing inorder... ");
        tree.inorder(tree.root);
    }

}

class Node
{
    int data;
    Node left;
    Node right;

    public Node() {
        // TODO Auto-generated constructor stub
        left = right = null;
    }
}

class Tree
{
    Node root;

    public Tree() {
        // TODO Auto-generated constructor stub
        root = null;
    }

    void inorder(Node node)
    {
        if(node == null)
            return;

        inorder(node.left);
        System.out.println(node.data);
        inorder(node.right);
    }

    void preorder(Node node)
    {
        if(node == null)
            return;

        System.out.println(node.data);
        preorder(node.left);
        preorder(node.right);
    }

    void postorder(Node node)
    {
        if(node == null)
            return;

        postorder(node.left);
        postorder(node.right);
        System.out.println(node.data);
    }

    void insert(int data)
    {
        Node node = new Node();
        node.data = data;

        if(root == null)
        {
            root = node;
            return;
        }

        Node trav = root;
        Node pretrav = root;
        while( trav != null )
        {
            pretrav = trav;
            if(node.data < trav.data)
            {
                trav = trav.left;
            }
            else
            {
                trav = trav.right;
            }
        }

        if(node.data < pretrav.data)
            pretrav.left = node;
        else
            pretrav.right = node;
    }
}

Answer 1

Java 使用引用的方式与 C 使用指针的方式非常相似。它们是相关的，但您不能像操纵指针那样操纵引用，从而使它们使用起来更安全(您的程序不太可能崩溃)。

每次调用 new 时都会创建一个引用。查看 insert 方法，您可以看到 new Node(...) 被调用，创建一个新对象并返回对新对象的引用。

每当您在自己的代码中使用这样的引用时，保存在变量中的只是“指针”，而不是整个对象。