1
是否有可能用C編寫一個二叉搜索樹而沒有指針？用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中實現，如下所示。如下所示，使用點符號訪問成員。我很想知道它是如何完成的。
如果class是一個結構，我可以說一個對象是一個指向 結構的指針。唯一的區別是在C中，指向 結構的指針使用符號 - >來訪問 結構的內部成員，而對象只是使用該符號。訪問結構（類）的內部 承包商，客人
工作BST代碼在Java中，其使用。符號，讓我想到如何在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;
}
}
您可以使用數組，爲null鏈接保留索引「-1」。如何回收已刪除的項目？通過有可用節點的第二個「鏈接列表」。 –
@WeatherVane，謝謝你。就像我上面提到的那樣，想要了解整個指針/地址概念是如何在Java中引發的。所以，如果類是一個結構，我可以說一個對象是一個指向結構的指針。唯一的區別是在C中，指向結構的指針使用符號 - >來訪問結構的內部成員，而對象只是使用。訪問結構（類） – PepperBoy