上海网站设计团队,wordpress标签关注,宁波专业网站定制制作服务,南京网站开发选南京乐识好什么是二叉搜索树#xff1f;
顾名思义#xff0c;一颗二叉搜索树是基于二叉树来组织的#xff0c;它包括许多动态集合操作#xff08;Search#xff0c;MiniNum, MaxiNum, Prodecessor, Successor, Insert 和Delete等#xff09;。二叉搜索树上的基本操作所花费的时间与…什么是二叉搜索树
顾名思义一颗二叉搜索树是基于二叉树来组织的它包括许多动态集合操作SearchMiniNum, MaxiNum, Prodecessor, Successor, Insert 和Delete等。二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比对呀有n个节点组成的完全二叉树来说这些操作的最坏的运行时间是O(lg n。 如图所示是一个搜索二叉树的结构。一个二叉树每一个节点就是一个对象包含的属性有左结点left右结点right和父结点parent以及这个节点的关键值key。在上图中根节点的关键值是6左结点是5右结点是8父节点为空。这是一颗完全除叶子结点外所有节点都存在左右结点的搜索二叉树要注意的是二叉搜索树的左结点值小于等于根结点的值而右结点的值大于等于根结点的值。搜索二叉树的性质允许我们通过一个简单的递归算法中序遍历就可以得到树中的所有关键字。一个二叉树结构在C中可以表示成如下
struct BinaryTreeNode{int val; //keyBinaryTreeNode *left; //left NodeBinaryTreeNode *right; //right Node
}; 搜索二叉树的遍历
中序遍历左——根——右根结点在中间遍历上图中二叉树经过中序遍历得到的是4556789.
前序遍历根——左——右根结点在前面的遍历上图中二叉树经过前序遍历得到的是6545878。
后序遍历左——右——根根结点在后面的遍历上图中二叉树经过后序遍历得到的是4557986.
//前序遍历二叉树
void TreeWalk(BinaryTreeNode *root)
{ if(rootnullptr) return;vectorinttree;tree.push_back(root-val);if(root-left) TreeWalk(root-left);if(root-right) TreeWalk(root-right);return;
}//中序遍历二叉树
void TreeWalk(BinaryTreeNode *root)
{ vectorinttree; if(root-left!nullptr)TreeWalk(root-left);tree.push_back(root-val);TreeWalk(root-right);return;
}//后序遍历二叉树
void TreeWalk(BinaryTreeNode *root)
{ vectorinttree; if(root-left!nullptr)TreeWalk(root-left);TreeWalk(root-right);tree.push_back(root-val);return;
}
查询二叉搜索树
如何查询二叉搜索树中的最小值最大值或者任意一个值
查询最小值根据二叉搜索树的性质可以知道搜索二叉树的最小值为最左边叶子结点的值。同理我们知道二叉搜索树的最大值为最右边叶子结点的值。代码如下
//最小值
int GetMiniNum(BinaryTreeNode* root)
{ while(root-left!nullptr) rootroot-left;return root-val;
}//最大值
int GetMaxiNum(BinaryTreeNode *root)
{while(root-right!nullptr) rootroot-right;return root-val;
}
查询二叉搜索树中的任意一个值相当于数组查询的二分法时间复杂度最差为O(depthdepth为二叉树的深度。代码如下
BinaryreeNode * Search(BinaryTreeNode *root,int k)
{if(rootnullptr||root-valk) return root;if(kroot-val)Search(root-left,k);elseSearch(root-right,k);
}二叉搜索树的插入和删除
要将一个新值x插入到二叉搜索树中需要调用Search操作。
void InsertTreeNode(BinaryTreeNode *root, k)
{BinaryTreeNode *ToBeInsertnew BinaryTreeNode(k);BinaryTreeNode *pCurroot;while(pNode!nullptr){ BinaryTreeNode *pNodepCur;if(pCur-valk){ pCurpCur-left;if(pCurnullptr)pCur-leftToBeInsert;}else {pCurpCur-right;if(pCurnullptr)pCur-rightToBeInsert;}}
}
