java - 在没有指针的情况下用 C 编写二叉搜索树

Question

是否可以在没有指针的情况下用 C 语言编写二叉搜索树？

我使用指针编写如下。

使用指针在 C 中工作 BST 代码

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

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

int insert(int);
int display(Node*);

int main(void)
{
 int n = 0;

 while(1)
 {
  printf("Enter data : ");
  scanf("%d",&n);

  if(n == -1)
   break;

  insert(n);
 }

 display(root);

 return 0;
}

int insert(int data)
{
 Node* node = malloc(sizeof(Node));
 node->data = data;
 node->left = NULL;
 node->right = NULL; 
 Node* parent;
 Node* trav;

 if(root == NULL)
  root = node;
 else
 {
  trav = root;

  while(trav != NULL)
  {
   parent = trav;

   if(node->data < trav->data)
    trav = trav->left;
   else
    trav = trav->right;
  }

  if(node->data < parent->data)
   parent->left = node;
  else
   parent->right = node;
 }
}

int display(Node* node)
{
 if(node == NULL)
  return 0;

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

有没有可能在没有指针的情况下只使用节点来编写 BST。所以，我想以 node.left 的形式访问左边，而不是 node->left 等等。连结构节点的成员都应该是这样的

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

节点成员将被声明为

Node root; Node node;

不像

Node* root; Node* node;

如果不能使用上述结构编写 BST，为什么会这样？是不是因为，NULL 是一个指针，它有一个保留值，用于指示该指针未引用有效对象。所以，如果我们只使用一个结构，我们就不知道什么时候停止。因此，我注释掉了上面代码中的 NULL 行，并进行了更改以作为结构成员而不是指针进行访问。我期待它至少可以编译，尽管它在某些地方会是一个无限循环。但是，它也给了我一些编译错误。

在不使用指针的情况下尝试在 C 中编写 BST 代码，无法编译

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

typedef struct node
{
 int data;
 struct node left;
 struct node right; 
}Node;
//Node root = NULL;
Node root;

int insert(int);
int display(Node);
int rootformed = 0;

int main(void)
{
 int n = 0;

 while(1)
 {
  printf("Enter data : ");
  scanf("%d",&n);

  if(n == -1)
   break;

  insert(n);
 }

 display(root);

 return 0;
}

int insert(int data)
{
 Node node = malloc(sizeof(Node));
 node.data = data;
 node.left = NULL;
 node.right = NULL; 
 Node parent;
 Node trav;

 if(rootformed == 0)
 {
  root = node;
  rootformed = 1;
 }
 else
 {
  trav = root;

  //while(trav != NULL)
  while(1)
  {
   parent = trav;

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

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

int display(Node node)
{
 //if(node == NULL)
  //return 0;

 display(node.left);
 printf("%d ",node.data);
 display(node.right);
}

但是，我正在研究如何在 Java 中实现二叉搜索树，如下所示。如下所示，使用点符号访问成员。我很想知道它是如何在这里完成的。

If class is a structure, can I say that an object is a pointer to the structure. The only difference being that in C, a pointer to a structure uses the notation -> to access the internal members of the structure, whereas, an object just uses . to access the internal memebers of the structure(class)

Java 中的工作 BST 代码，它使用 .符号，让我思考如何在 C 中模拟它以使用 .符号而不是 ->

public class BinarySearchTree 
{
    public Node root;
    public BinarySearchTree()
    {
        this.root = null;
    }

    public boolean find(int id)
    {
        Node current = root;
        while(current!=null)
        {
            if(current.data == id)
            {
                return true;
            }
            else if(id < current.data)
            {
                current = current.left;
            }
            else
            {
                current = current.right;
            }
        }

        return false;
    }

    public boolean delete(int id)
    {
        Node parent = root;
        Node current = root;
        boolean isLeftChild = false;

        while(current.data != id)
        {
            parent = current;
            if(id < current.data)
            {
                isLeftChild = true;
                current = current.left;
            }
            else
            {
                isLeftChild = false;
                current = current.right;
            }
            if(current ==null)
            {
                return false;
            }
        }
        //if i am here that means we have found the node
        //Case 1: if node to be deleted has no children
        if(current.left==null && current.right==null)
        {
            if(current==root)
            {
                root = null;
            }
            if(isLeftChild ==true)
            {
                parent.left = null;
            }
            else
            {
                parent.right = null;
            }
        }
        //Case 2 : if node to be deleted has only one child
        else if(current.right==null)
        {
            if(current==root)
            {
                root = current.left;
            }
            else if(isLeftChild)
            {
                parent.left = current.left;
            }
            else
            {
                parent.right = current.left;
            }
        }
        else if(current.left==null)
        {
            if(current==root)
            {
                root = current.right;
            }
            else if(isLeftChild)
            {
                parent.left = current.right;
            }
            else
            {
                parent.right = current.right;
            }
        }
        else if(current.left!=null && current.right!=null)
        {   
            //now we have found the minimum element in the right sub tree
            Node successor   = getSuccessor(current);
            if(current==root)
            {
                root = successor;
            }
            else if(isLeftChild)
            {
                parent.left = successor;
            }
            else
            {
                parent.right = successor;
            }           
            //successor.left = current.left;
        }       
        return true;        
    }

    public Node getSuccessor(Node deleteNode)
    {
        Node successsor =null;
        Node successsorParent =null;
        Node current = deleteNode.right;
        while(current!=null)
        {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        //check if successor has the right child, it cannot have left child for sure
        //if it does have the right child, add it to the left of successorParent.
        //successsorParent
        if(successsor!=deleteNode.right)
        {
            successsorParent.left = successsor.right;
            successsor.right = deleteNode.right;
        }

        if(successsor==deleteNode.right)
        {
            /* Then no more right tree */

        }

        successsor.left = deleteNode.left;
        return successsor;
    }

    public void insert(int id)
    {
        Node newNode = new Node(id);
        if(root==null)
        {
            root = newNode;
            return;
        }
        Node current = root;
        Node parent = null;
        while(true)
        {
            parent = current;
            if(id < current.data)
            {               
                current = current.left;
                if(current==null)
                {
                    parent.left = newNode;
                    return;
                }
            }
            else
            {
                current = current.right;
                if(current==null)
                {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

    public void display(Node root)
    {
        if(root != null)
        {
            display(root.left);
            System.out.print(" " + root.data);
            display(root.right);
        }
    }

    public static void main(String arg[])
    {
        BinarySearchTree b = new BinarySearchTree();

        b.insert(3);b.insert(8);
        b.insert(1);b.insert(4);b.insert(6);b.insert(2);b.insert(10);b.insert(9);
        b.insert(20);b.insert(25);b.insert(15);b.insert(16);

        System.out.println("Original Tree : ");
        b.display(b.root);      
        System.out.println("");
        System.out.println("Check whether Node with value 4 exists : " + b.find(4));
        System.out.println("Delete Node with no children (2) : " + b.delete(2));        
        b.display(root);
        System.out.println("\n Delete Node with one child (4) : " + b.delete(4));       
        b.display(root);
        System.out.println("\n Delete Node with Two children (10) : " + b.delete(10));      
        b.display(root);
    }
}

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

    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
}

Answer 1

代替指向内存对象的指针，您可以分配一个大数组 Node对象并将索引存储到 left 中的此数组中和 right成员。

数组条目 0是根节点。您必须跟踪第一个未使用的数组元素以存储新的 Node .您可以使用 calloc分配数组和realloc扩大数组。

您必须跟踪已删除的项目:跟踪第一个并放入 left下一个删除项目的索引(一种链表)。您还可以跟踪最后删除的项目以快速将另一个删除的项目追加到列表中。