*ppTreeNode = pNode->left;
}else{
pLeftMaxParent = get_parent_of_one(*ppTreeNode, pLeftMax);
pNode->data = pLeftMax->data;
pLeftMaxParent->right = NULL;
pNode = pLeftMax;
}
}
goto final;
}
pNode = _delete_node_from_tree(*ppTreeNode, pNode);
final:
set_link_for_delete(pNode);
free(pNode);
return TRUE;
}
其中，寻找最大值节点和寻找父节点的代码如下所示：
TREE_NODE* get_max_node_of_one(TREE_NODE* pNode)
{
if(NULL == pNode)
return NULL;
while(pNode->right)
pNode = pNode->right;
return pNode;
}
TREE_NODE* get_parent_of_one(TREE_NODE* root, TREE_NODE* pNode)
{
if(NULL == root || NULL == pNode)
return NULL;
while(root){
if(pNode == root->left || pNode == root->right)
return root;
else if(pNode->data < root->data)
root = root->left;
else
root = root->right;
}
return NULL;
}
TREE_NODE* get_max_node_of_one(TREE_NODE* pNode)
{
if(NULL == pNode)
return NULL;
while(pNode->right)
pNode = pNode->right;
return pNode;
}
TREE_NODE* get_parent_of_one(TREE_NODE* root, TREE_NODE* pNode)
{
if(NULL == root || NULL == pNode)
return NULL;
while(root){
if(pNode == root->left || pNode == root->right)
return root;
else if(pNode->data < root->data)
root = root->left;
else
root = root->right;
}
return NULL;
}
总结：
（1）排序二叉树的序列化关键就是在二叉树节点添加前向指针和后继指针
（2）排序二叉树是空间换时间的典型案例
（3）排序二叉树是很多结构的基础，写多少遍都不为多，有机会朋友们应该多加练习
（4）测试用例的编写是代码编写的关键，编写程序的目的就是为了消除bug，特别是低级bug