c++ 打印叶节点父二叉树

46scxncf 于 2023-05-30 发布在其他

关注(0)|答案(3)|浏览(182)

我的C++练习是关于打印二叉树中的leave父节点。为了实现这一目标，我想出了两个办法。它们是

思路一

/* Write a program that finds and prints all vertices of a binary tree which have 
 * successor leaves only */

#include <iostream>

class Node{
  public:
    int data;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(int value){data=value;}
};

bool traverse(Node* node);

bool traverse(Node* node){
  if(!node->left&&!node->right)
    return true;

  if (traverse(node->left)||traverse(node->right)) 
      std::cout<<node->data<<'\t';  

  if(node->left)
    traverse(node->left);

  if (node->right) 
    traverse(node->right);  
}//Non-void function does not return a value in all control paths

优点：

我喜欢它的一点是，我不需要添加任何变量，额外的变量。如果我想在另一个树中使用该方法或类似的实现，这是一个巨大的优势，因为Node类是干净的。
缺点
我的traverse函数的主要问题是我不知道如何实现编译器抱怨的缺少的return false;语句。如果我这么做了，在我的理解中就不会有递归了。

思路二

/* Write a program that finds and prints all vertices of a binary tree which have 
 * successor leaves only */

#include <iostream>

class Node{
  public:
    int data;
    Node* left = nullptr;
    Node* right = nullptr;
    bool isLeaf = false;

    Node(int value){data=value;}
};

void traverse(Node* node);

void traverse(Node* node){
  if(!node->left&&!node->right){
    node->isLeaf = true;
    return;
  }

  if (node->left||node->right) 
      std::cout<<node->data<<'\t';  

  if(node->left)
    traverse(node->left);

  if (node->right) 
    traverse(node->right);  
}

优点：

我觉得第二个想法更有效，在某种程度上更少冒险。
缺点
我不喜欢它的地方是它有一个额外的变量，如果我把它放到一个更全面的树类中，这个变量可能不是很有用。简单点说，想法2看起来不如想法1干净

Bug

关于这两个想法，我有一点想不通。为什么不递归循环呢？这两个代码中都有一个return语句，它避免了无限循环，只要right或left子代码退出，就会发生递归调用。谁能告诉我我的traverse函数出了什么问题？

问题

我还想让idea 1工作，因为我喜欢它通过调用自身来检查节点是否是叶子节点的父节点的方式。如何处理编译器希望包含的缺少的return false;语句？

编辑

只是想添加我为它们创建的main函数，这样你们就可以看到我是如何构建树的。

int main(){
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->left->right = new Node (5);
  root->right->left = new Node(6);
  root->right->right = new Node(7);

  traverse(root);
  return 0;
}

c++

来源：https://stackoverflow.com/questions/76345121/print-leaves-node-parent-binary-tree

3条答案

按热度按时间

lskq00tm1#

从外观上看，您正在遍历pre-order中的树（打印，然后“* 遍历 *”树的左右）。
我不完全理解为什么你会在这种情况下使用bool，因为这些函数/方法通常是无效的。你走在正确的道路上，递归是你在Data Structures中最好的朋友。
下面是我对pre-ordertype void的实现：

void traverse(Node* node /*root*/) {
  if(node == nullptr) {
    return; //do nothing
    
  }else if(node != nullptr){ //could just be an else
    std::cout << node -> data << "\t";
    
    traverse(root -> left); //walk left
    
    traverse(root -> right); //walk right
  }
}

下面是我的printLeafNodestype void的实现：

void printLeafNodes(Node* node) {
  if (node == nullptr) {
    return; 
  }

  if (node->left == nullptr && node->right == nullptr) {
    std::cout << node->data << "\t";
  }
  printLeafNodes(node->left); 
  printLeafNodes(node->right); 
}

编辑：

我似乎误解了你的问题摆在首位，我猜你想打印所有顶点的二叉树，只有后继叶。

编码：

void traverse(Node* node) {
    if (!node)
        return;

    if (node->left && !node->left->left && !node->left->right)
        std::cout << node->left->data << '\t';

    if (node->right && !node->right->left && !node->right->right)
        std::cout << node->right->data << '\t';

    traverse(node->left);
    traverse(node->right);
}

我希望这能回答你的问题。
本质上是一样的，但这里要检查它是否实际上是一个叶节点。没有left或right子节点表示leaf节点
我希望你熟悉递归，因为这是 imo 一个非常简单的例子，并且非常不言自明。这不会进入无限循环，因为只要一个子节点== nullptr，它就会返回。
回答你的问题：* 为什么它们不递归地循环？* 没有更多的上下文或没有看到你的主要内容很难说。如果node->left或node->right是nullptr，那么你提前返回，也许你的树是skewed或degenerate。

赞(0）回复(0）举报 2023-05-30

zour9fqk2#

您发布的Idea 1代码非常接近，但编译器警告可能不是唯一的问题。
我认为您倾向于在Node结构中不需要额外数据的解决方案是正确的。Idea 1将被视为non-intrusive解决方案，而Idea 2将被视为intrusive解决方案。

第一个条件返回true，用于没有子节点的情况，即叶节点。所有其他情况都是false，因此只需在函数结束时返回false。
我认为只有当left和right的子节点traverse都返回true时，才需要打印节点，即两个子节点都是叶子节点，但我可能不太理解这个问题。

// Returns true if this node is a leaf, otherwise, false.
bool traverse(Node* node){

  if(!node->left&&!node->right)
    return true;

  // I think you want an `and` here, i.e. both children must be leaves
  if (traverse(node->left)&&traverse(node->right)) 
      std::cout<<node->data<<'\t';  

  if(node->left)
    traverse(node->left);

  if (node->right) 
    traverse(node->right);

  // There are at least some children, so not a leaf.
  return false;  
}

赞(0）回复(0）举报 2023-05-30

0md85ypi3#

我没有看到一个实际的问题，但我遇到了问题，显示树木，一旦他们得到深和宽。我最终使用头优先递归将其“横向”打印出来，这对我来说很好：

void BinTree::showTree(const Node *ptr, const int depth) {
        if(ptr->right != nullptr) {
                showTree(ptr->right, depth + 1);
        }
        cout << string(depth, '\t') << ptr->val << endl;
        if(ptr->left != nullptr) {
                showTree(ptr->left, depth + 1);
        }
}

我的0.02美元

赞(0）回复(0）举报 2023-05-30

我来回答

c++ 打印叶节点父二叉树

思路一

思路二

3条答案

相关问题

热门标签

最新问答