用于修剪二叉树的代码

Question

我正在尝试编写一个代码，用于移除树的叶子并打印树的其余部分。

在平衡树的情况下，我能够获得适当的输出。例如

1
/ 
2   3
/     
4  5     6

该树的输出必须为213(当按顺序打印时)

当它是一棵不平衡的树时，我没有得到想要的输出。对于前

1
/ 
2   3
/     
4  5     6
/ 
7   8

我正在获取4 3 2 5 1 3. which is wrong.

correct answer is 4 2 1 3.(printed inorder)

有人能帮我一下我犯了什么错误吗？

程序的代码是

//prune a tree

#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *left;
struct Node *right;
};
struct Node *follower=NULL;
struct Node *create_node(int item)
{
struct Node *newNode=NULL;
newNode= new Node;
newNode->data=item;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
void extract_leaves_binary_tree(struct Node *root)
{
int na=0;
if(root==NULL)
return;
if(root->left==NULL && root->right==NULL)
{
na=1;
}   
else
{
follower=root;
}
if(na==1 )
{       
if(follower->left==root)
follower->left=NULL;            
if(follower->right==root)
follower->right=NULL;                   
na=0;
}   
extract_leaves_binary_tree(root->left);
extract_leaves_binary_tree(root->right);
}

void print(struct Node *root)
{
if(root==NULL)
return;
print(root->left);
cout<<root->data;
print(root->right);
}
void driver(struct Node *root)
{
extract_leaves_binary_tree(root);
}
int main()
{
struct Node *root=NULL;
root  = create_node(1);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(4);
root->left->right = create_node(5);
root->right->right = create_node(6);
root->left->left->left = create_node(7);
root->left->left->right = create_node(8);
driver(root);
cout<<"inordrer"<<endl;
print(root);
return 0;
}

Answer 1

在我的脑海中，我认为这样做会简单得多：

Node* internal_extract_leaves(struct Node* root)
{
if(root == NULL)
return NULL;
if(root->left==NULL && root->right==NULL)
return NULL;
root->left = internal_extract_leaves(root->left);
root->right = internal_extract_leaves(root->right);  
return root;
}
void extract_leaves_binary_tree(struct Node *root)
{
root = internal_extract_leaves(root);
}

Answer 2

行if(root->left==NULL && root->right==NULL)检查两个子元素是否都是NULL，但是元素2只有一个子元素NULL，因此它被跳过，元素5永远不会被删除。右侧的元素3也是如此。你需要对每一侧进行单独检查。

编辑：以上信息是错误的。问题是追随者是全球性的所以你改变它，当你从左边的递归回到节点2去递归时，右边的跟随者不再是节点2。这意味着你不能删除它。

Answer 3

我必须承认，我对你在这里尝试的算法没有太多的理解。我想我很困惑，因为我不知道你所说的following或na是什么意思，也因为你把每个节点都称为root。而且，通过使用全局变量，你给了我一层我不想考虑的复杂性。

如果我不理解你的意图，那么当你在6个月后返回自己的代码时，你也不会理解。

它可以帮助创建具有解释性名称的函数，如这里的isLeaf()。这是一种称为"函数分解"的技术——通过将算法分解成更小的函数，使其更容易理解。函数分解也倾向于产生更高效的代码，因为它为优化编译器提供了更多的结构。

我认为下面的代码就像递归代码一样不言自明：

• 如果孩子存在。。。
  • 。。。它是一片叶子，删除它
  • 。。。否则它就不是一片叶子：下弯到里面

---

bool isLeaf(struct Node* node) {
// assumes we will never be passed NULL. 
return (node->left == NULL) && (node->right == NULL);
}
void remove_leaves(struct Node* node) {
// assumes we will never be passed NULL. Certainly never passes itself NULL!
if(node->left != NULL) {
if(isLeaf(node->left)) {
node->left = NULL;
} else {
remove_leaves(node->left);
}
}
if(node->right != NULL) {
if(isLeaf(node->right)) {
node->right = NULL;
} else {
remove_leaves(node->right);
}
}
}
int main() {
struct Node *root=create_node(1);
// create tree as before
remove_leaves(root);
print(root);
}

---

或者(由下面的注释提示)您可以复制树，省略叶子：

• 使用与源相同的数据创建新节点
• 如果源的子级存在并且不是叶，请创建子级的副本，并使其成为副本的子级

---

struct Node* copy_minus_leaves(struct Node *node) {
// assume we are never passed NULL
struct Node* copy = create_node(node->data);
if(node->left != NULL && !isLeaf(node->left)) {
copy->left = copy_minus_leaves(node->left);
}
if(node->right!= NULL && !isLeaf(node->right)) {
copy->right= copy_minus_leaves(node->right);
}
return copy;
}
int main() {
struct Node *root=create_node(1);
// create tree as before
struct Node *copy = copy_minus_leaves(root);
print(copy);
}

---

注意，这两种算法都不会删除树的根，即使它是一个叶子(即树只包含一个节点)。这可能是可取的，也可能不是可取的，这取决于你使用树的目的。您需要将零节点树视为一种特殊情况。

还要注意的是，此代码并没有free()分配给已删除叶子的内存。与其把代码弄得一团糟，我还是把它留给你练习。

你往往知道什么时候递归代码是正确的，因为它突然看起来非常简单。