首页 > 代码库 > 二叉树学习二：二叉搜索树
二叉树学习二：二叉搜索树
二叉搜索树（Binary Search Tree），或者是一棵空树，或者：
1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）二叉搜索树的左、右子树也分别为二叉搜索树。
搜索二叉树相关的算法实现：
1）搜索二叉树的创建与转化为双链表实现：
1 #include "stdafx.h" 2 #include<iostream> 3 using namespace std; 4 5 /*二无查找树结构定义*/ 6 typedef struct BSTreeNode 7 { 8 int m_nValue; 9 BSTreeNode *m_pLeft;10 BSTreeNode *m_pRight;11 12 }BSTreeNode, *BSTree;13 14 BSTreeNode *m_pHead = NULL;//指向循环队列头结点15 BSTreeNode *m_pPre = NULL;//指向前一个结点16 17 void addBSTreeNode(BSTreeNode *&m_pRoot, int value);18 void inOrderBSTree(BSTreeNode *m_pRoot);19 void covertBSTree(BSTreeNode *m_pRoot);20 21 /****************创建二叉搜索树*****************/22 void addBSTreeNode(BSTreeNode *&m_pRoot, int value){23 if (m_pRoot == NULL)24 {25 BSTreeNode *m_pBSTree = new BSTreeNode();26 m_pBSTree->m_nValue =http://www.mamicode.com/ value;27 m_pBSTree->m_pLeft = NULL;28 m_pBSTree->m_pRight = NULL;29 m_pRoot = m_pBSTree;30 }31 else if (m_pRoot->m_nValue<value)32 {33 addBSTreeNode(m_pRoot->m_pRight, value);34 }35 else if (m_pRoot->m_nValue>value)36 {37 addBSTreeNode(m_pRoot->m_pLeft, value);38 }39 }40 41 /****************中序遍历二叉搜索树*****************/42 void inOrderBSTree(BSTreeNode *m_pRoot)43 {44 if (NULL == m_pRoot)45 {46 return;47 }48 if (NULL != m_pRoot->m_pLeft)49 {50 inOrderBSTree(m_pRoot->m_pLeft);51 }52 covertBSTree(m_pRoot);53 if (NULL != m_pRoot->m_pRight)54 {55 inOrderBSTree(m_pRoot->m_pRight);56 }57 }58 59 /****************调整指针位置*****************/60 void covertBSTree(BSTreeNode *m_pRoot)61 {62 m_pRoot->m_pLeft = m_pPre; //使当前结点的左指针指向双向链表中最后一个结点63 if (NULL == m_pPre)64 {65 m_pHead = m_pRoot;66 }67 else68 {69 m_pPre->m_pRight = m_pRoot;70 }71 m_pPre = m_pRoot;72 cout << m_pRoot->m_nValue << "\t";73 }74 75 int main()76 {77 BSTreeNode *m_pRoot = NULL;78 addBSTreeNode(m_pRoot, 10);79 addBSTreeNode(m_pRoot, 7);80 addBSTreeNode(m_pRoot, 15);81 addBSTreeNode(m_pRoot, 5);82 addBSTreeNode(m_pRoot, 9);83 addBSTreeNode(m_pRoot, 12);84 addBSTreeNode(m_pRoot, 1);85 inOrderBSTree(m_pRoot);86 return 0;87 }
2）判断一个数组是否为一个二叉搜索树实现：
1 #include "stdafx.h" 2 #include<iostream> 3 using namespace std; 4 5 bool VertBST(int Arr[], int length) 6 { 7 if (Arr == NULL || length <= 0) 8 { 9 return false;10 }11 int root = Arr[length - 1];12 //在左子树中查找小于根节点13 int i = 0;14 for (; i < length - 1; ++i)15 {16 if (Arr[i]>root)17 {18 break;19 }20 }21 //在右子树中查找大于根结点22 int j = i;23 for (; j < length-1; ++j)24 {25 if (Arr[j]<root)26 {27 return false;28 }29 }30 //判断左子树是不是二叉搜索树31 bool left = true;32 if (i>0)33 {34 left = VertBST(Arr, i);35 }36 //判断右子树是不是二叉搜索树37 bool right = true;38 if (i<length-1)39 {40 right = VertBST(Arr + i, length - i - 1);41 }42 return(left&&right);43 }44 void main()45 {46 int a[7] = {3, 6, 5, 4, 11, 9, 8};47 bool result;48 result = VertBST(a, 7);49 cout << result << endl;50 }
对二叉搜索树的优化一般采用平衡二叉树实现。
二叉树学习二：二叉搜索树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。