※数据结构※→☆非线性结构（tree）☆============二叉搜索树（二叉查找树） 链式存储结构（tree Binary Search list）（二十五）
二叉搜索树（二叉查找树）
二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
原理
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).
算法
查找算法
在二叉排序树b中查找x的过程为：
若b是空树，则搜索失败，否则：
若x等于b的根结点的数据域之值，则查找成功；否则：
若x小于b的根结点的数据域之值，则搜索左子树；否则：
查找右子树。
2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。
3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。
树的四种遍历
1.先序遍历 （仅二叉树）
指先访问根，然后访问孩子的遍历方式
2.中序遍历（仅二叉树）
指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式
3.后序遍历（仅二叉树）
指先访问孩子，然后访问根的遍历方式
4.层次遍历
一层一层的访问，所以一般用广度优先遍历。
======================================================================================================
树结点 链式存储结构（tree node list）
结点：
包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。
在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。
数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点
树结点（树节点）：
树节点相关术语：
节点的度：一个节点含有的子树的个数称为该节点的度；叶节点或终端节点：度为0的节点称为叶节点；非终端节点或分支节点：度不为0的节点；双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；节点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；堂兄弟节点：双亲在同一层的节点互为堂兄弟；节点的祖先：从根到该节点所经分支上的所有节点；子孙：以某节点为根的子树中任一节点都称为该节点的子孙。根据树结点的相关定义，采用“双亲孩子表示法”。其属性如下：
2．孩子表示法
1.多重链表：每个结点有多个指针域，分别指向其子树的根
1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域.
2）结点不同构：结点指针个数不等，为该结点的度d
2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表
3．双亲孩子表示法
1.双亲表示法，PARENT（T，x）可以在常量时间内完成，但是求结点的孩子时需要遍历整个结构。
2.孩子链表表示法，适于那些涉及孩子的操作，却不适于PARENT（T，x）操作。
3.将双亲表示法和孩子链表表示法合在一起，可以发挥以上两种存储结构的优势，称为带双亲的孩子链表表示法
4．双亲孩子兄弟表示法 （二叉树专用）
又称为二叉树表示法，以二叉链表作为树的存储结构。
链式存储结构
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).
它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.
链式存储结构特点：
1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
5、每个结点是由数据域和指针域组成。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
C++完整个代码示例（代码在VS2005下测试可运行）
AL_TreeNodeBinSearchList.h
#ifdef TEST_AL_TREEBINSEARCHLIST//AL_TreeBinSearchList<DWORD, DWORD> cTreeSearchBin;AL_TreeBinSearchList<DWORD, DWORD>* pTreeSearchBin = new AL_TreeBinSearchList<DWORD, DWORD>;AL_TreeBinSearchList<DWORD, DWORD>& cTreeSearchBin = *pTreeSearchBin;BOOL bEmpty = cTreeSearchBin.IsEmpty();std::cout<<bEmpty<<std::endl;const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstRootNode = cTreeSearchBin.GetRootNode();AL_TreeNodeBinSearchList<DWORD, DWORD>* pRootNode = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstRootNode);std::cout<<pRootNode<<std::endl;DWORD dwDegree = cTreeSearchBin.GetDegree();std::cout<<dwDegree<<std::endl;DWORD dwHeight = cTreeSearchBin.GetHeight();std::cout<<dwHeight<<std::endl;DWORD dwNodesNum = cTreeSearchBin.GetNodesNum();std::cout<<dwNodesNum<<std::endl;//insert datastruct TestData {DWORD dwData;DWORD dwKey;};DWORD dwData = 0x00;DWORD dwKey = 0x00;TestData sTestData[] = {{0, 65}, {1, 9}, {2, 61}, {3, 66}, {4, 32}, {5, 1}, {6, 39}, {7, 14}, {8, 99}, {9, 68}, {10, 11}, {11, 6}, {12, 94}, {13, 53}, {14, 17}, {15, 67}, {16, 23}, {17, 86}, {18, 7}, {19, 2}};BOOL bInsert = FALSE;for (DWORD dwTestDataCnt=0x00; dwTestDataCnt<(sizeof(sTestData)/sizeof(TestData));dwTestDataCnt++) {bInsert = cTreeSearchBin.Insert(sTestData[dwTestDataCnt].dwData, sTestData[dwTestDataCnt].dwKey);if (FALSE == bInsert) {std::cout<<bInsert<<std::endl;}}BOOL bGet = cTreeSearchBin.Get(23, dwData);std::cout<<bGet<<", "<<dwData<<std::endl;pConstRootNode = cTreeSearchBin.GetRootNode();pRootNode = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstRootNode);std::cout<<pRootNode<<std::endl;const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode = cTreeSearchBin.GetChildNodeLeftAtNode(pRootNode);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode);std::cout<<pTreeNode<<std::endl;const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode20 = cTreeSearchBin.GetChildNodeLeftAtNode(pTreeNode);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode20 = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode20);std::cout<<pTreeNode<<std::endl;const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode31 = cTreeSearchBin.GetChildNodeRightAtNode(pConstTreeNode20);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode31 = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode31);const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode30 = cTreeSearchBin.GetChildNodeLeftAtNode(pConstTreeNode20);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode30 = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode30);const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode999 = cTreeSearchBin.GetChildNodeRightAtNode(pConstTreeNode30);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode999 = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode999);const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode41 = cTreeSearchBin.GetChildNodeRightAtNode(pConstTreeNode31);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode41 = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode41);const AL_TreeNodeBinSearchList<DWORD, DWORD>* pConstTreeNode33 = cTreeSearchBin.GetChildNodeRightAtNode(pTreeNode20);AL_TreeNodeBinSearchList<DWORD, DWORD>* pTreeNode33 = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstTreeNode33);if (NULL != pTreeNode) {std::cout<<pTreeNode->GetLevel()<<" "<<pTreeNode->GetData()<<" "<<pTreeNode->GetDegree()<<std::endl;std::cout<<pTreeNode->IsLeaf()<<" "<<pTreeNode->IsBranch()<<" "<<pTreeNode->IsParent(pTreeNode)<<" "<<pTreeNode->IsParent(pTreeNode33)<<std::endl;}if (NULL != pTreeNode20) {std::cout<<pTreeNode20->GetLevel()<<" "<<pTreeNode20->GetData()<<" "<<pTreeNode20->GetDegree()<<std::endl;std::cout<<pTreeNode20->IsLeaf()<<" "<<pTreeNode20->IsBranch()<<" "<<pTreeNode20->IsParent(pTreeNode)<<" "<<pTreeNode20->IsParent(pTreeNode33)<<std::endl;}if (NULL != pTreeNode33) {std::cout<<pTreeNode33->GetLevel()<<" "<<pTreeNode33->GetData()<<" "<<pTreeNode33->GetDegree()<<std::endl;std::cout<<pTreeNode33->IsLeaf()<<" "<<pTreeNode33->IsBranch()<<" "<<pTreeNode33->IsParent(pTreeNode)<<" "<<pTreeNode33->IsParent(pTreeNode33)<<std::endl;}const AL_TreeNodeBinSearchList<DWORD, DWORD>*pChild = NULL;pChild = cTreeSearchBin.GetChildNodeRightAtNode(pTreeNode);if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(pTreeNode)<<" "<<pChild->IsParent(pTreeNode33)<<std::endl;}pChild = cTreeSearchBin.GetChildNodeLeftAtNode(pTreeNode);if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(pTreeNode)<<" "<<pChild->IsParent(pTreeNode33)<<std::endl;}pChild = cTreeSearchBin.GetChildNodeLeftAtNode(pTreeNode);if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(pTreeNode)<<" "<<pChild->IsParent(pTreeNode33)<<std::endl;}pChild = cTreeSearchBin.GetChildNodeRightAtNode(pTreeNode);if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(pTreeNode)<<" "<<pChild->IsParent(pTreeNode33)<<std::endl;}pChild = cTreeSearchBin.GetChildNodeRightAtNode(pTreeNode);if (NULL != pChild) {std::cout<<pChild->GetLevel()<<" "<<pChild->GetData()<<" "<<pChild->GetDegree()<<std::endl;std::cout<<pChild->IsLeaf()<<" "<<pChild->IsBranch()<<" "<<pChild->IsParent(pTreeNode)<<" "<<pChild->IsParent(pTreeNode33)<<std::endl;}bEmpty = cTreeSearchBin.IsEmpty();std::cout<<bEmpty<<std::endl;dwDegree = cTreeSearchBin.GetDegree();std::cout<<dwDegree<<std::endl;dwHeight = cTreeSearchBin.GetHeight();std::cout<<dwHeight<<std::endl;dwNodesNum = cTreeSearchBin.GetNodesNum();std::cout<<dwNodesNum<<std::endl;AL_ListSingle<DWORD> cListData;AL_ListSingle<DWORD> cListKey;BOOL bSibling = cTreeSearchBin.GetSiblingAtNode(pTreeNode, cListData, cListKey);if (TRUE == bSibling) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();bSibling = cTreeSearchBin.GetSiblingAtNode(pTreeNode20, cListData, cListKey);if (TRUE == bSibling) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();BOOL bAncestor = cTreeSearchBin.GetAncestorAtNode(pRootNode, cListData, cListKey);if (TRUE == bAncestor) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}bAncestor = cTreeSearchBin.GetAncestorAtNode(pTreeNode33, cListData, cListKey);if (TRUE == bAncestor) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();BOOL bDescendant = cTreeSearchBin.GetDescendantAtNode(pRootNode, cListData, cListKey);if (TRUE == bDescendant) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();bDescendant = cTreeSearchBin.GetDescendantAtNode(pTreeNode33, cListData, cListKey);if (TRUE == bDescendant) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();BOOL bOrder = cTreeSearchBin.PreOrderTraversal(cListData, cListKey);if (TRUE == bOrder) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();bOrder = cTreeSearchBin.InOrderTraversal(cListData, cListKey);if (TRUE == bOrder) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();bOrder = cTreeSearchBin.PostOrderTraversal(cListData, cListKey);if (TRUE == bOrder) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();bOrder = cTreeSearchBin.LevelOrderTraversal(cListData, cListKey);if (TRUE == bOrder) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();//cTreeSearchBin.Remove(pTreeNode20);bOrder = cTreeSearchBin.LevelOrderTraversal(cListData, cListKey);if (TRUE == bOrder) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();bEmpty = cTreeSearchBin.IsEmpty();std::cout<<bEmpty<<std::endl;dwDegree = cTreeSearchBin.GetDegree();std::cout<<dwDegree<<std::endl;dwHeight = cTreeSearchBin.GetHeight();std::cout<<dwHeight<<std::endl;dwNodesNum = cTreeSearchBin.GetNodesNum();std::cout<<dwNodesNum<<std::endl;BOOL bRemoveNode = cTreeSearchBin.RemoveNode(66);std::cout<<bRemoveNode<<std::endl;bOrder = cTreeSearchBin.LevelOrderTraversal(cListData, cListKey);if (TRUE == bOrder) {for (DWORD dwCnt=0; dwCnt<cListData.Length(); dwCnt++) {if (TRUE == cListData.Get(dwCnt, dwData) && TRUE == cListKey.Get(dwCnt, dwKey)) {std::cout<<"["<<dwData<<", "<<dwKey<<"]"<<", ";}}std::cout<<std::endl;}cListData.Clear();BOOL bRemove = cTreeSearchBin.Remove(65);std::cout<<bRemove<<std::endl;bEmpty = cTreeSearchBin.IsEmpty();std::cout<<bEmpty<<std::endl;pConstRootNode = cTreeSearchBin.GetRootNode();pRootNode = const_cast<AL_TreeNodeBinSearchList<DWORD, DWORD>*>(pConstRootNode);std::cout<<pRootNode<<std::endl;dwDegree = cTreeSearchBin.GetDegree();std::cout<<dwDegree<<std::endl;dwHeight = cTreeSearchBin.GetHeight();std::cout<<dwHeight<<std::endl;dwNodesNum = cTreeSearchBin.GetNodesNum();std::cout<<dwNodesNum<<std::endl;delete pTreeSearchBin;pTreeSearchBin = NULL;#endif
