二叉树和 doubleTree() 函数

Question

我最近学习了二叉树并决定练习一下。我以为我对指针和引用参数的理解相当不错，但后来我遇到了这段代码：

 void doubleTree(struct node* node) { 
  struct node* oldLeft;

  if (node==NULL) return;

  // do the subtrees 
  doubleTree(node->left); 
  doubleTree(node->right);

       // duplicate this node to its left 
     oldLeft = node->left; 
     node->left = newNode(node->data); 
     node->left->left = oldLeft; 
    }

我简直无法理解如何在不使用引用参数或非空函数的情况下更改二叉树的构造。

我已经在互联网上搜索了几天，但没有找到合适的解释。我知道我在使用现有节点时不需要参考参数，但据我所知，这与创建新元素并将其添加到二叉树相同 - 我有使用非空函数！

谁能给我解释一下吗？

Answer 1

好吧，在 C 中根本没有引用参数...所有参数都按值传递。出于这个原因，指针就在手边……并且您将 指向子树根节点的指针传递给函数，它本身就是对根节点的引用。 这确实是你期望的引用，但表示为指向节点的指针。

注意

在您展示的情况下，如果您必须更改传递给根节点的指针（您不能更改它，因为它是按值传递的），则可能会出现问题子树，因为更改指针只会在子例程中局部发生。在这种情况下，您可以传递一个双指针，如

void doubleTree(struct node** node) { ... }

所以你实际上传递了一个指向保存根节点地址的根指针的指针。修改它应该完成：

*node = foo ...;

因此，您将获得对根指针的引用。但是例程中所做的事情只处理节点内容和根节点的 children ....没有指向它的指针，所以你不需要传递对指针的引用全部.

注 2

除了您提出的问题外，显示的代码还有问题。双节点应该作为孙子 left->left child 附加，而不检查左 child 是否实际上有左 children。如果leftchild实际上有一个leftchild，那一点的子树将被新创建的节点替代，产生内存泄漏（所有子树从现在开始将无法访问）并将该子树更改为单个节点。例行程序的奇怪行为应该使树加倍。

我个人同意你的观点，使用 return 复制树的函数会更好，更容易编写：

struct node* doubleTree(struct node* node) 
{ 
    return node != NULL
        ? newNode(node->data, 
                  doubleTree(node->left), 
                  doubleTree(node->right));
        : NULL;
}

（本例newNode()有三个参数，节点数据，左右children附加到它上面）

注 2

我想将加倍节点存储为给定根节点的 child 的目的是将构建的树保存为给定树的子树。但由于上述原因它失败了，所以你实际上需要 return 一个指针才能将一些东西返回给调用代码。传递引用旧树和新树的空白节点的代码的意图失败了，因为当递归调用时，它应该导致所有子树也以这种方式构造，树最终将由支持的空白副本填充原始子树和复制子树的左右副本。您应该需要一个像上面写的那样的递归例程，return引用新创建的子树。

你说的对:)

二叉树和 doubleTree() 函数

Binary trees and doubleTree() function

c

pointers

tree

binary-tree

mirror

注意

注 2

注 2