本文主要是介绍删除二叉树中的度数为1的所有结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
要求：结点删除后其唯一的子节点代替它的位置。
这里用到了递归的方法，不断遍历每个节点的左右子树，将度数为一的结点删除。
#include <iostream>using namespace std;struct Node
{int v;Node* left;Node* right;
};void print_div(int p)
{for(int i=0; i < p; i++){cout<<"-";}
}void print_tree(Node* node, int p)
{if(node != NULL){print_div(p);cout<<node->v<<endl;if(node->left != NULL || node->right != NULL){print_tree(node->left, p+1);print_tree(node->right, p+1);}}else{print_div(p);cout<<endl;}
}void print_tree(Node* node)
{print_tree(node, 0);
}void delete_one_degree_node(Node*& node)
{if(node == NULL)return;if(node->left != NULL && node->right == NULL) //只有左子树{node = node->left;delete_one_degree_node(node);}else if(node->right != NULL && node->left == NULL) //只有右子树{node = node->right;delete_one_degree_node(node);}else if(node->left != NULL && node->right != NULL) //左右子树均存在{delete_one_degree_node(node->left);delete_one_degree_node(node->right);}
}int main()
{Node n[10] = {0};Node* tree = n;for(int i=0; i < 10; i++){n[i].v = i;}tree[0].left = &tree[1];tree[0].right = &tree[2];tree[1].left = &tree[3];tree[1].right = &tree[4];tree[2].left = NULL;tree[2].right = &tree[6];tree[3].left = &tree[7];tree[3].right = &tree[8];tree[4].left = &tree[9];cout<<"Original:"<<endl;print_tree(tree);delete_one_degree_node(tree);cout<<"After:"<<endl;print_tree(tree);return 0;
}
这篇关于删除二叉树中的度数为1的所有结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
