BST(二)： minmaxsuccessordecessor

求一个二叉排序树的最小值和最大值，

以及求某一个节点的中序后继，中序前继节点。

这都是常用操作。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct stBinary_Search_Tree
{int key;struct stBinary_Search_Tree* pP;/*指向父节点*/struct stBinary_Search_Tree* pL;struct stBinary_Search_Tree* pR;
}BST;BST* bst_new_node(int key)
{BST* newNode = (BST*)malloc(sizeof(BST));if (newNode == NULL){printf("malloc fail for new node: %d \n", key);return NULL;}(void)memset(newNode, 0, sizeof(BST));newNode->key = key;return newNode;
}/*处理一个节点插入到某二叉树中，就是单纯的插入，
不负责某某节点在不在的查找逻辑*/
void bst_insert(BST** ppTree, BST* pNewNode)
{BST* pTree = *ppTree;BST* pLoopNode = pTree;BST* pParentNode = pTree;while (pLoopNode){pParentNode = pLoopNode;if (pLoopNode->key >= pNewNode->key){pLoopNode = pLoopNode->pL;}else{pLoopNode = pLoopNode->pR;}}/*1 维护子父关系*/pNewNode->pP = pParentNode;/*2 parent为空说明是空树，维护父子关系*/if (pParentNode == NULL){*ppTree = pNewNode;}else if (pParentNode->key >= pNewNode->key){pParentNode->pL = pNewNode;}else{pParentNode->pR = pNewNode;}
}/*中序遍历树打印*/
void bst_inorder_print(BST** ppTree)
{BST* pTree = *ppTree;if (pTree){bst_inorder_print(&pTree->pL);printf("%d \t",pTree->key);bst_inorder_print(&pTree->pR);}
}BST *bst_find(BST** ppTree, int key)
{BST* pTree = *ppTree;BST* pLoopNode = pTree;while (pLoopNode){if (pLoopNode->key == key){return pLoopNode;}else if (pLoopNode->key > key){pLoopNode = pLoopNode->pL;}else{pLoopNode = pLoopNode->pR;}}return pLoopNode;
}/*树的最小节点，按照bst特性，往左子树一直遍历
返回的节点也有可能为空，使用注意*/
BST* bst_minum(BST** ppTree)
{BST* pLoopNode = *ppTree;BST* pParentNode = pLoopNode;while (pLoopNode){pParentNode = pLoopNode;pLoopNode = pLoopNode->pL;}return pParentNode;
}BST* bst_maxum(BST** ppTree)
{BST* pLoopNode = *ppTree;BST* pParentNode = pLoopNode;while (pLoopNode){pParentNode = pLoopNode;pLoopNode = pLoopNode->pR;}return pParentNode;
}/*目标节点的中序后继节点*/
BST* bst_inorder_succesor(BST* pObjNode)
{/*1 如果右子树非空，则返回右子树的最小节点即为目标节点的中序后继*/if (pObjNode->pR){return bst_minum(&pObjNode->pR);}/*2 不满足父子关系是父右子关系的最小祖宗节点即是后继*/BST* pParent = pObjNode->pP;while (pParent && pParent->pR == pObjNode){pObjNode = pParent;pParent = pParent->pP;}return pParent;
}/*目标节点的中序前继节点*/
BST* bst_inorder_predecessor(BST* pObjNode)
{/*1 如果右子树非空，则返回右子树的最小节点即为目标节点的中序前继*/if (pObjNode->pL){return bst_maxum(&pObjNode->pL);}/*2 不满足父子关系是父左子关系的最小祖宗节点即是前继*/BST* pParent = pObjNode->pP;while (pParent && pParent->pL == pObjNode){pObjNode = pParent;pParent = pParent->pP;}return pParent;
}BST* g_bst_tree = NULL;void test_bst_oper()
{int arr[] = { 4,2,5,1,3 };/*42     51   3*/for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){BST* pNewNode = bst_new_node(arr[i]);bst_insert(&g_bst_tree,pNewNode);}printf("bst inorder print\n");bst_inorder_print(&g_bst_tree);printf("\n");BST* findNode = bst_find(&g_bst_tree,2);printf("node 2 parent is %d (should 4) \n",findNode->pP->key);printf("node 2 pL is %d (should 1) pR is %d (should 3) \n", findNode->pL->key, findNode->pR->key);printf("\n#Min&Max test \n");BST* pMinNode = bst_minum(&g_bst_tree);printf("min node is %d (should 1) \n", pMinNode->key);BST* pMaxNode = bst_maxum(&g_bst_tree);printf("max node is %d (should 5) \n",pMaxNode->key);printf("\n#Successor test \n");BST* pSuccessor = bst_inorder_succesor(pMaxNode);if (pSuccessor) printf("error maxnode should no successor\n");else printf("maxnode has no successor,  right\n");pSuccessor = bst_inorder_succesor(findNode);printf("node2 successor is %d (should 3) \n", pSuccessor->key);printf("\n#Predecessor test \n");BST* pPredecessor = bst_inorder_predecessor(pMinNode);if (pPredecessor) printf("error maxnode should no predecessor\n");else printf("minode has no successor,  right\n");pPredecessor = bst_inorder_predecessor(findNode);printf("node2 predeceessor is %d (should 1) \n", pPredecessor->key);
}int main()
{test_bst_oper();return 0;
}