二叉树节点故障

Question

这是节点定义:

struct node{
    int data;
    stuct node * left;
    struct node * right;
};

我要做的是列出指向祖先节点的所有节点.在发布错误的解决方案并从答案中获取建议后,我的新解决方案是:

递归遍历二叉树.将当前节点添加到节点数组,然后检查当前节点的子节点是否指向任何先前的祖先节点.

默认情况是节点为NULL.如果发生这种情况,函数返回.

它应该如何工作:

将节点添加到阵列

检查左子项是否为NULL.

如果不是,则将子进程与之前的每个节点进行比较.

如果发现故障,则报告.

如果不是,则以子节点作为参数调用该函数.

重复直到完成.(二叉树的rhs也一样)

问题:

• 数组是存储节点的最佳选择吗？
• 这有用吗？for(i = 0; i <sizeof(arrOfNodes)/ sizeof(node); i ++)
• 因为函数是递归的,所以数组和数组索引不能在函数内初始化(或者它们可以是？)所以它们应该是全局的吗？
• 有两个阵列会更好吗？(一个用于LHS,一个用于RHS)

代码:

void findFault(node * root){
    if (root == NULL){
      return;
    }

    arrOfNodes[index++] == root; // array of nodes

    if (root->left != NULL){
      for (i = 0; i < sizeof(arrOfNodes) / sizeof(node); i++){
         if (ar[i] == root->left){
             printf("%d", root->left);
             return;
         }
       }
       findFault(root->left);
    } else return;

    if (root->right != NULL){
      for (i = 0; i < sizeof(ar) / sizeof(node); i++){
         if (ar[i] == root->right){
             printf("%d", root->right);
             return;
         }
      }
      findFault(root->right);
    } else return;
}

Answer 1

我不知道递归,但是这个:

if (&root->left->left == &root){

在我可以描述的更多方面是错误的,但无论如何这里有三个问题:

• 你为什么要取根的地址？
• 为什么不测试第一个左指针是否为空？
• 你可以简单地使用std :: map,但学习如何实现二叉树也是一个好主意.

Answer 2

这是解决问题的错误方法.Neil Butterworth已经注意到你的代码,我会注意到算法.

您的算法仅检查一个非常具体的情况 - 孙子节点是否指向其祖父母.你应该做的是在一个节点的路上收集父母,看看节点的孩子不是它的父母之一.

有很多方法可以做到这一点.一种是在节点结构中添加一个计数器,并在开始遍历树之前将所有节点的计数器设置为零.每当到达节点时,确保计数器为零,然后将其增加1.这意味着如果您看到一个计数器不为零的孩子,您已经访问过它,因此该树无效.