数据结构与算法之二叉搜索树
與鏈表不同，樹是一種非線性的數據結構。樹中最常用的是二叉樹，二叉樹限制了子樹的數量，也就是每個結點的子樹至多2個，并且這兩個子樹是有順序的。而二叉搜索樹（二叉查找樹，二叉排序樹）是指根節點的關鍵字大于左子樹的，而小于右子樹，并且，左右子樹也是一顆二叉搜索樹。也就是說中序遍歷一顆二叉搜索樹，它的輸出是從小到大排序好的。
除了普通的二叉搜索樹之外，還有很多關于它的變形。
二叉平衡搜索樹，即即是一顆二叉平衡樹，也是一顆搜索樹，平衡樹即任意一個結點的左子樹的高度與右子樹的高度之差的絕對值不大于1。
紅黑樹，也是一種特殊的二叉查找樹，除了具備查找樹的特點，它的每個結點上還有一個記錄紅黑顏色的元素。
這里我們主要討論一般的二叉搜索樹。
二叉搜索樹，其實就是一顆特殊的樹，任何適用于樹的算法都適用于二叉搜索樹。當然它也是圖，任何適用于圖的算法也適用于二叉搜索樹。圖中的深度優先搜索（DFS）其實就是樹中的前序遍歷，廣度優先搜索（BFS）就是樹中的層序遍歷。當然圖中還有很多其他算法也都適用于樹。
1、二叉樹的數據結構
typedef struct binSrcTreeNode{int element;struct binSrcTreeNode *pLeft;struct binSrcTreeNode *pRight; }BSTNode;2、動態分配一個二叉樹的結點
BSTNode* allocNode(int element){BATNode *pNode = (BSTNode*)malloc(sizeof(BSTNode));if(NULL != pNode){pNode->element = element;pNode->pLeft = NULL;pNode->pRight = NULL;}return pNode; }3、二叉搜索樹的查找
由于二叉搜索樹是已經排序了的二叉樹，所以可以通過二分查找來搜索。先判斷是否等于根節點，如果大于根節點的關鍵字，搜索右子樹，小于根節點的關鍵字，搜索左子樹。
bool searchInBSTree(const BSTNode *pRoot,int element,BSTNode **pNode){if(NULL == pRoot)return false;*pNode = pRoot;if(pRoot->element == element){return true;}else if(pRoot->element > element)return searchInBSTree(pRoot->pLeft,element,pNode);elsereturn searchInBSTree(pRoot->pRight,element,pNode); }4、二叉搜索樹的插入
首先查找二叉樹是是否已經存在該元素，如果已經存在返回false;如果不存在，插入該結點，插入元素大于根節點，則插入右子樹，否則，插入左子樹中。
5、二叉搜索樹的刪除
二叉搜索樹的刪除分為三種情況：
(1) 刪除結點為葉子結點，直接刪除該結點，再修改其父結點的指針（注意分是根結點和不是根節點）。
(2) 刪除結點為單支結點（即只有左子樹或右子樹）。
(3) 刪除結點的左子樹和右子樹均不空。
bool deleteFromBSTree(BSTNode **pRoot,int element){if(NULL == pRoot || NULL == *pRoot)return false;BSTNode **pSrc = NULL;BSTNode **pParent = NULL;if(searchInBSTree(*pRoot,element,pParent,pSrc)){if(NULL == *pSrc->pLeft && NULL == *pSrc->pRight){free(*pSrc);*pSrc = NULL;return true;}else if(NULL == *pSrc->pLeft){if(*pSrc == *pParent->pLeft)*pParent->pLeft = *pSrc->pRight;else if(*pSrc == *pParent->pRight)*pParent->pRight = *pSrc->pRight;free(*pSrc);return true;}else if(NULL == *pSrc->pRight){if(*pSrc == *pParent->pLeft)*pParent->pLeft = *pSrc->pLeft;else if(*pSrc == *pParent->pRight)*pParent->pRight = *pSrc->pLeft;free(*pSrc);return true;}else{BSTNode *pNode = *pSrc;BSTNode *pChild = *pSrc->pLeft;while(pChild->pRight){pNode = pChild;pChild = pChild->pRight;}if(pNode == *pSrc) pNode->pLeft = pChild->pLeft;else pNode->pRight = pChild->pLeft;if(*pSrc == *pParent->pLeft) *pParent->pLeft = pChild;else *pParent->pRight = pChild;pChild->pLeft = *pSrc->pLeft;pChild->pRight = *pSrc->pRight;return true;}}return false; }6、二叉搜索樹的前序中序后序遍歷
/* preOrder to traverse the binarySearchTree.*/ void preOrderBinarySearchTree(const BSTNode *pRoot){if(NULL == pRoot)return ;printf("%d ",pRoot->element);preOrderBinarySearchTree(pRoot->pLeft);preOrderBinarySearchTree(pRoot->pRight); }/* inOrder to traverse the binarySearchTree.*/ void inOrderBinarySearchTree(const BSTNode *pRoot){if(NULL == pRoot)return ;inOrderBinarySearchTree(pRoot->pLeft);printf("%d ",pRoot->element);inOrderBinarySearchTree(pRoot->pRight); }/* posOrder to traverse the binarySearchTree.*/ void posOrderBinarySearchTree(const BSTNode *pRoot){if(NULL == pRoot)return ;posOrderBinarySearchTree(pRoot->pLeft);posOrderBinarySearchTree(pRoot->pRight);printf("%d ",pRoot->element); }?
7、釋放結點
void freeBinarySearchTree(BSTNode *pRoot){if(NULL == pRoot)return ;freeBinarySearchTree(pRoot->pLeft);freeBinarySearchTree(pRoot->pRight);free(pRoot); }?
完整代碼詳見：https://github.com/whc2uestc/DataStructure-Algorithm/tree/master/tree
?
轉載于:https://www.cnblogs.com/whc-uestc/p/4638349.html
總結
以上是生活随笔為你收集整理的数据结构与算法之二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。
