删除二叉树中的度数为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;
}