数据结构实战

        首先我们来简单的学习一下二叉树的存储结构：

        二叉树是普通树的一种特殊形式，二叉树的每一个数据节点都有一个节点称作父节点（或双亲节点）和两个子节点，称作左孩子和右孩子。当然，对于根节点来说，它的父节点必为空。而对于所有非根节点来说，父节点必然存在。对于最底层叶子节点来说，它们的左右孩子节点必为空。其它节点的左右孩子节点可以为空也可以非空。下面来看一下二叉树的数据结构：

//二叉树节点
typedef struct s_node
{
	//数据指针
	void *data;
	//父节点
	struct s_node *parent;
	//左孩子节点
	struct s_node *left_child;
	//右孩子节点
	struct s_node *right_child;
} s_node;

//二叉树数据结构
typedef struct s_tree
{
	//根节点
	s_node *root;
	//访问函数指针
	void (*visit_node)();
	//释放内存函数指针
	void (*free_node)();
} s_tree;

        接下来实现二叉树的一些常用功能函数：

//初始化树
bool tree_init(s_tree *tree, void (*visit_node)(), void (*free_node)())
{
	if (tree == null)
	{
		return false;
	}

	tree->root = null;
	tree->visit_node = visit_node;
	tree->free_node = free_node;

	return true;
}

//销毁树
bool tree_destroy(s_tree *tree)
{
	if (tree == null)
	{
		return false;
	}

	//清空树
	tree_clear(tree, tree->root);

	//根节点置空
	tree->root = null;

	return true;
}

//清空树
void tree_clear(s_tree *tree, s_node *node)
{
	if (node == null)
	{
		return;
	}

	//递归清空左子树
	tree_clear(tree, node->left_child);
	//递归清空右子树
	tree_clear(tree, node->right_child);

	//如果数据项不为空
	if (node->data != null)
	{
		//释放数据项内存
		tree->free_node(node->data);
	}

	node->left_child = null;
	node->right_child = null;

	if (node == tree->root)
	{
		tree->root = null;
	}

	//释放当前节点内存
	free(node);
}

//取得根节点
s_node* tree_root(s_tree *tree)
{
	if (tree == null)
	{
		return null;
	}

	return tree->root;
}

//找到数据项在树中的节点
bool tree_find_node(s_node *node, s_node **node_f, void *data)
{
	if (node == null)
	{
		return false;
	}

	if (node_f == null)
	{
		return false;
	}

	if (data == null)
	{
		return false;
	}

	//找到同地址数据项，返回当前节点
	if (node->data == data)
	{
		*node_f = node;
		return true;
	}

	//递归查找左子树
	if (tree_find_node(node->left_child, node_f, data))
	{
		return true;
	}
	//递归查找右子树
	if (tree_find_node(node->right_child, node_f, data))
	{
		return true;
	}

	return false;
}

//找到数据项在树中的父节点
s_node* tree_parent(s_tree *tree, void *data)
{
	if (tree == null)
	{
		return null;
	}

	if (data == null)
	{
		return null;
	}

	//找到数据项所在的节点
	s_node *node_find = null;
	tree_find_node(tree->root, &node_find, data);
	if (node_find == null)
	{
		return null;
	}

	//返回父节点
	return node_find->parent;
}

//找到数据项在树中的左孩子
s_node* tree_left_child(s_tree *tree, void *data)
{
	if (tree == null)
	{
		return null;
	}

	if (data == null)
	{
		return null;
	}

	//找到数据项所在的节点
	s_node *node_find = null;
	tree_find_node(tree->root, &node_find, data);
	if (node_find == null)
	{
		return null;
	}

	//返回左孩子节点
	return node_find->left_child;
}

//找到数据项在树中的右孩子
s_node* tree_right_child(s_tree *tree, void *data)
{
	if (tree == null)
	{
		return null;
	}

	if (data == null)
	{
		return null;
	}

	//找到数据项所在的节点
	s_node *node_find = null;
	tree_find_node(tree->root, &node_find, data);
	if (node_find == null)
	{
		return null;
	}

	//返回右孩子节点
	return node_find->right_child;
}

//找到数据项在树中的左兄弟
s_node* tree_left_brother(s_tree *tree, void *data)
{
	if (tree == null)
	{
		return null;
	}

	if (data == null)
	{
		return null;
	}

	//找到数据项所在的节点
	s_node *node_find = null;
	tree_find_node(tree->root, &node_find, data);
	if (node_find == null)
	{
		return null;
	}

	if (node_find->parent == null)
	{
		return null;
	}

	if (node_find == node_find->parent->left_child)
	{
		return null;
	}

	//返回左兄弟
	return node_find->parent->left_child;
}

//找到数据项在树中的右兄弟
s_node* tree_right_brother(s_tree *tree, void *data)
{
	if (tree == null)
	{
		return null;
	}

	if (data == null)
	{
		return null;
	}

	//找到数据项所在的节点
	s_node *node_find = null;
	tree_find_node(tree->root, &node_find, data);
	if (node_find == null)
	{
		return null;
	}

	if (node_find->parent == null)
	{
		return null;
	}

	if (node_find == node_find->parent->right_child)
	{
		return null;
	}

	//返回右兄弟
	return node_find->parent->right_child;
}

//将node_ins插入node的左或右节点，原节点做为node_ins的右节点
bool tree_insert(s_tree *tree, s_node *node, int leftright, s_node *node_ins)
{
	if (tree == null)
	{
		return false;
	}

	if (node_ins == null)
	{
		return false;
	}

	//如果是一棵空树
	if (tree->root == null)
	{
		//将节点做为树的根节点
		tree->root = node_ins;
		node_ins->parent = null;
		return true;
	}

	//被插入节点的右子树必须为空
	if (node_ins->right_child != null)
	{
		return false;
	}

	//如果插入目标节点的左节点
	if (leftright == 0)
	{
		//插入左节点
		s_node *p_temp = node->left_child;
		node->left_child = node_ins;
		node_ins->parent = node;
		//将原左子树挂接到新节点的右子树上
		node_ins->right_child = p_temp;
		if (p_temp != null)
		{
			p_temp->parent = node_ins;
		}
	}
	//如果插入目标节点的右节点
	else if (leftright == 1)
	{
		//插入右节点
		s_node *p_temp = node->right_child;
		node->right_child = node_ins;
		node_ins->parent = node;
		//将原右子树挂接到新节点的右子树上
		node_ins->right_child = p_temp;
		if (p_temp != null)
		{
			p_temp->parent = node_ins;
		}
	}

	return true;
}

//删除节点
void tree_delete_node(s_tree *tree, s_node *node)
{
	if (node == null)
	{
		return;
	}

	//递归删除左子树
	tree_delete_node(tree, node->left_child);
	//递归删除右子树
	tree_delete_node(tree, node->right_child);

	if (node->data != null)
	{
		tree->free_node(node->data);
	}

	//删除左节点
	node->left_child = null;
	//删除右节点
	node->right_child = null;

	//如果是根节点则清空树
	if (node == tree->root)
	{
		tree->root = null;
	}

	free(node);
}

//删除树的节点
bool tree_delete(s_tree *tree, s_node *node, int leftright)
{
	if (tree == null)
	{
		return false;
	}

	if (node == null)
	{
		return false;
	}

	//删除左子树
	if (leftright == 0)
	{
		tree_delete_node(tree, node->left_child);
		node->left_child = null;
	}
	//删除右子树
	else if (leftright == 1)
	{
		tree_delete_node(tree, node->right_child);
		node->right_child = null;
	}

	//如果是根节点则清空树
	if (node == tree->root)
	{
		tree->root = null;
	}

	return true;
}

        对于树这种数据结构来说，很多函数通常都使用递归来实现的，这与树的数据结构一致。因为树的一个叶子节点可以看做是另外一棵树，而这棵树的每一个节点同样也都可以看作是另外的树。

        最后来编写一个main函数对二叉树的数据结构做一些测试：

//删除整数函数
void free_int(int *i)
{
	if (i != null)
	{
		free(i);
	}
}

//访问整数函数
void visit_int(int *i)
{
	if (i != null)
	{
		printf("%d", *i);
	}
}

int main(int argc, char **args)
{
	int *t0 = (int *) malloc(sizeof(int));
	int *t1 = (int *) malloc(sizeof(int));
	int *t2 = (int *) malloc(sizeof(int));

	*t0 = 0;
	*t1 = 1;
	*t2 = 2;

	//初始化树
	s_tree tree;
	tree_init(&tree, &visit_int, &free_int);

	s_node *n0 = (s_node *) malloc(sizeof(s_node));
	s_node *n1 = (s_node *) malloc(sizeof(s_node));
	s_node *n2 = (s_node *) malloc(sizeof(s_node));

	n0->parent = null;
	n0->left_child = null;
	n0->right_child = null;
	n0->data = t0;

	n1->parent = null;
	n1->left_child = null;
	n1->right_child = null;
	n1->data = t1;

	n2->parent = null;
	n2->left_child = null;
	n2->right_child = null;
	n2->data = t2;

	//插入根节点
	s_node *node = tree.root;
	tree_insert(&tree, node, 0, n0);
	//插入根节点的左孩子
	node = tree.root;
	tree_insert(&tree, node, 0, n1);
	//插入根节点的右孩子
	node = tree.root;
	tree_insert(&tree, node, 1, n2);

	//得到根节点
	s_node *p = tree_root(&tree);
	visit_int(p->data);
	printf("\n");

	//得到父节点
	p = tree_parent(&tree, t1);
	visit_int(p->data);
	printf("\n");

	//得到父节点
	p = tree_parent(&tree, t2);
	visit_int(p->data);
	printf("\n");

	//得到左孩子
	p = tree_left_child(&tree, t0);
	visit_int(p->data);
	printf("\n");

	//得到右孩子
	p = tree_right_child(&tree, t0);
	visit_int(p->data);
	printf("\n");

	//得到左兄弟
	p = tree_left_brother(&tree, t2);
	visit_int(p->data);
	printf("\n");

	//得到右兄弟
	p = tree_right_brother(&tree, t1);
	visit_int(p->data);
	printf("\n");

	//删除根节点的左孩子
	tree_delete(&tree, tree.root, 0);
	p = tree_left_child(&tree, t0);
	if (p == null)
	{
		printf("Left child of the root node is null.\n");
	}

	//删除根节点的右孩子
	tree_delete(&tree, tree.root, 1);
	p = tree_right_child(&tree, t1);
	if (p == null)
	{
		printf("Right child of the root node is null.\n");
	}

	//销毁树
	tree_destroy(&tree);

	return 0;
}

        运行结果：

0
0
0
1
2
1
2
Left child of the root node is null.
Right child of the root node is null.

        本例代码：

code path   chapter.05/e.g.5.1/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure