二叉搜索树和AVL树的常见节点结构

Question

我想为二叉搜索树(BST)和AVL树定义一个公共(public)的节点结构。为了实现这一点，我在 CommonNode.h 文件中定义了以下结构。

struct CommonNode{
int data;
struct CommonNode *left, *right;
};
typedef struct CommonNode node;

在另一个文件BST.h中，我定义了BST节点的结构

struct bsTree{
node *nodePtr;
};
typedef struct bsTree bst;

在另一个文件AVL.h中，我定义了AVL节点的结构

struct AVLTree{
node *nodePtr;
int balanceFactor;
};
typedef struct AVLTree avl;

考虑以下代码(在树中搜索值的代码)

avl *p;
p = root; // assume that pointer to root is given
while(p!=NULL){
    if(value < p->nodePtr->data)  // value
        p = p->nodePtr->left;
    else
        p = p->nodePtr->right;
}

此方法不正确，因为 p->nodePtr->left; 指向结构体 CommonNode 而 p 是指向结构体 AVLTree。 我的问题是，为这个问题定义公共(public)节点结构的正确方法是什么？

Answer 1

这可能对你有帮助

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

struct CommonNode{
int data;
struct CommonNode *left, *right;
};

typedef struct CommonNode node;

struct bsTree{
node *nodePtr;
};

typedef struct bsTree bst;

struct AVLTree{
node *nodePtr;
int balanceFactor;
};

typedef struct AVLTree avl;


int main()
{
avl *p;
p = (struct AVLTree*)malloc(sizeof(struct AVLTree));
p->nodePtr = (node*)malloc(sizeof(node));
p->nodePtr->data = 20;
printf("The data value is %d\n",p->nodePtr->data);
return 0;
}


OUTPUT:
The data value is 20