二叉搜索树(二叉排序树)BST与双向列表的转换
目录
1.二叉排序树（Binary Sort Tree)
二叉排序树又称二叉查找树(Binary Search Tree) BST
二叉排序树或者是一颗空树，或者是满足一下性质的一颗二叉树：
- 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
- 若它的右子树非空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左/右子树分别为二叉排序树
下面是初始序列建立二叉排序树的过程：
{ 4, 2, 6, 1, 3, 5 }：
1.0 BST树存储结构
用二叉链表作为二叉排序树的存储结构！
typedef int KeyType;
typedef int ElemType;
/*二叉树的结点存储结构，二叉链表存储结构*/
typedef struct BiTNode{
KeyType data;
int multiplicity;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
/*
BiTNode:是结构类型
BiTree：是指向结点BiTNode的指针类型
*/
二叉排序树的基本操作：
- 查找key
- 插入结点
- 删除结点
1.1BST查找
/*在跟指针T所指的二叉排序树中递归地查找其关键字等于key的数据元素，
若查找成功，则指针p指向该数据元素结点，并返回true，否则指针p指向查找路径
*问的最后一个结点并放回false，指针f指向T的双亲，其初始调用值为nullptr(空指针）*/
bool SearchBST(BiTree T, KeyType key, BiTree f, BiTree& p)
{
/*在跟指针T所指的二叉排序树中递归地查找其关键字等于key的数据元素，
若查找成功，则指针p指向该数据元素结点，并返回true，否则指针p指向查找路径
*问的最后一个结点并放回false，指针f指向T的双亲，其初始调用值为nullptr*/
if (!T)
{
p = f;
return false;
}
else if (key == T->data)
{
p = T;
return true;
}
else if (key < T->data)
{
return SearchBST(T->lchild, key, T, p);
}
else if (key > T->data)
{
return SearchBST(T->rchild, key, T, p);
}
}//SearchBST1.2BST树插入节点
插入前要先搜索待插入的位置，如果存在值key值相同的节点，则不插入，并返回false。
/*当二叉树上不存在关键字等于e.key的数据元素时，插入e并返回true;
否则返回false;*/
bool InsertBST(BiTree& T, ElemType e)
{
/*当二叉树上不存在关键字等于e.key的数据元素时，插入e并返回true;
否则返回false;*/
BiTree p;
BiTree f = nullptr;
if (!SearchBST(T, e, f, p))//指针p指向查找路径*问的最后一个结点并放回false
{
//BiTree s = (BiTree)malloc(sizeof(BiTNode));
BiTree s = new BiTNode;
s->data = e;
s->multiplicity = 1;
s->lchild = s->rchild = nullptr;
if (!p)
{//被插入结点为新的根结点！
T = s;
}
else if (e < p->data)
{//被插入结点*s为当前结点的左孩子
p->lchild = s;
}
else if (e > p->data)
{//被插入结点*s为当前结点的右孩子
p->rchild = s;
}
return true;
}
else
{//树中已经有关键字相同的结点，不再插入,该结点的重复度+1
p->multiplicity++;
return false;
}
}1.3中序遍历BST树得到有序序列
void printVal(BiTree T)
{
cout << T->data << " ";
}
void InOrderTraverseRecursive(BiTree T, void(*funcPtr)(BiTree))
{//对采用二叉链表表示的二叉树的中序遍历算法
/*中序遍历二叉树T的递归算法！*/
if (T)
{
InOrderTraverseRecursive(T->lchild, funcPtr);
funcPtr(T);
InOrderTraverseRecursive(T->rchild, funcPtr);
}
else
{
return;
}
}
//中序遍历二叉树
/*E2版本的中序遍历结构更加清晰、易懂！*/
void InOrderTraverseLoopE2(BiTree T, void(*funcPtr)(BiTree))
{/*二叉树T采用二叉链表存储结构，中序遍历T的非递归算法，对每一个元素调用funcPtr函数*/
stack<BiTree> biTreeStack;//存储结点指针的栈
BiTree p;
p = T;
while (p || !biTreeStack.empty())
{
if (p)
{//根指针进栈，然后遍历左子树
biTreeStack.push(p);
p = p->lchild;//这里也是一直走到最下边的结点
}
else
{//根指针退栈，访问根结点，然后遍历右子树
p = biTreeStack.top();
biTreeStack.pop();
funcPtr(p);
p = p->rchild;
}
}
}
1.4删除BST树上的一结点
bool Delete(BiTree& p)
{//从二叉排序树中删除结点p，并重接它的左或右子树
if (!p->rchild)
{
BiTree q = p;
p = p->lchild;
delete q;
}
else if (!p->lchild)
{
BiTree q = p;
p = p->rchild;
delete q;
}
else//左右子树均不为空
{
BiTree q = p;
BiTree s = p->lchild;
while (s->rchild)
{//
q = s;
s = s->rchild;
}
p->data = s->data;//s指向被删除结点的前驱
if (q != p)
{
q->rchild = s->lchild;//重接*q的右子树
}
else
{
q->lchild = s->lchild;//重接*q的左子树
}
delete s;
}
return true;
}
bool DeleteBSTKey(BiTree& T, KeyType key)
{/*若二叉排序树T中存在关键字等于key的数据元素，则删除该数据元素结点！*/
if (!T) return false;
else
{
if (key == T->data)
{
return Delete(T);
}
else if (key < T->data)
{
return DeleteBSTKey(T->lchild, key);
}
else if (key > T->data)
{
return DeleteBSTKey(T->rchild, key);
}
}
}//DeleteBST
1.5二叉排序树内存的释放_后序遍历删除每一个结点
bool deteteBiTNode(BiTree p)
{
if (!p)
{
return false;
}
delete p;
p = nullptr;
return true;
}
void PostOrderTraverseRecursive(BiTree T, bool(*funcPtr)(BiTree))
{//对采用二叉链表表示的二叉树的后序遍历算法
/*后序遍历二叉树T的递归算法！*/
if (T)
{
PostOrderTraverseRecursive(T->lchild, funcPtr);
PostOrderTraverseRecursive(T->rchild, funcPtr);
funcPtr(T);
}
else
{
return;
}
}
1.6二叉树的后序遍历_非递归算法
参考我的另一篇博文：二叉树_二叉链表存储_前中后遍历_栈：递归非递归遍历_队列：按层遍历
https://blog.csdn.net/m0_37357063/article/details/81982646
后序遍历的非递归算法：以栈模拟递归的过程:
/*
二叉树的后序遍历--非递归实现
https://www.cnblogs.com/rain-lei/p/3705680.html
https://www.cnblogs.com/rain-lei/p/3705680.html
leetcode中有这么一道题，非递归来实现二叉树的后序遍历。
二叉树的后序遍历顺序为，root->left, root->right, root，
因此需要保存根节点的状态。显然使用栈来模拟递归的过程，
但是难点是怎么从root->right转换到root。
方法1：判断是否轮到栈顶p访问法，设立刚访问结点指针last
对于节点p可以分情况讨论
1. p如果是叶子节点，直接访问（输出）
2. p如果有孩子，且孩子没有被访问过，则按照右孩子，左孩子的顺序依次入栈
3. p如果有孩子，而且孩子都已经访问过，则访问p节点
如何来表示出p的孩是否都已经访问过了呢？
最暴力的方法就是对每个节点的状态进行保存，
这么做显然是可以的，但是空间复杂度太大了。
我们可以保存最后一个访问的节点last，
如果满足 (p->right==NULL && last ==p->left) || last=p->right，
那么显然p的孩子都访问过了，接下来可以访问p
*/
二叉树的后序遍历法1：区别栈顶结点p是否该访问了之设立刚访问结点指针法
void PostOrderTraverseE1(BiTree T, void(*funcPtr)(BiTree))
{
if (!T)
return;
stack<BiTree> biTreeStack;//存储结点指针的栈
BiTree p = T;
BiTree last = T;
biTreeStack.push(p);
while (!biTreeStack.empty())
{
p = biTreeStack.top();
/*情况1：如果p是叶子结点，其左右子树都为空，则可直接访问p;
情况2：如果满足 (p->right==NULL && last ==p->left) || last=p->right，
那么显然p的孩子都访问过了，接下来可以访问p
如果p的右子树为空，并且p的左子树已经访问过了，即(p->right==NULL && last ==p->left)
那么就可以访问p了
如果p的右子树也访问过了即last=p->right，也可以访问p了
*/
if ((p->lchild == nullptr&&p->rchild == nullptr) || (p->rchild == nullptr&&last == p->lchild) || (last == p->rchild))
{
funcPtr(p);//访问p
last = p;//将刚才访问的结点标记为p
biTreeStack.pop();//p出栈
}
else
{
if (p->rchild)
{//如果右子树非空，则右子树结点进栈
biTreeStack.push(p->rchild);
}
if (p->lchild)
{//如果左子树非空，则左子树结点进栈
biTreeStack.push(p->lchild);
}
}
}
}
二叉树的后序遍历法2：区别栈顶结点p是否该访问了同一个结点两次压入两次弹出法：
/*
法2：每个结点两次压入法
其实我们希望栈中保存的从顶部依次是root->left, root->right, root，
当符合上面提到的条件时，就进行出栈操作。有一种巧妙的方法可以做到，
对于每个节点，都压入两遍，在循环体中，每次弹出一个节点赋给p，
如果p仍然等于栈的头结点，说明p的孩子们还没有被操作过，
应该把它的孩子们加入栈中，否则，访问p。
也就是说，第一次弹出，将p的孩子压入栈中，第二次弹出，访问p。
*/
void PostOrderTraverseE2(BiTree T, void(*funcPtr)(BiTree))
{
if (T == NULL) return;
BiTree p = T;
stack<BiTree> sta;
sta.push(p);
sta.push(p);
while (!sta.empty())
{
p = sta.top();
sta.pop();
if (!sta.empty() && p == sta.top())
{
if (p->rchild) sta.push(p->rchild), sta.push(p->rchild);//C：逗号,运算符
if (p->lchild) sta.push(p->lchild), sta.push(p->lchild);
}
else
{
funcPtr(p);
}
}
}
2.将BST转换成双向列表
参考《剑指offer》P191
面试题36：二叉搜索树与双向列表
题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序有序的双向列表。要求不能创建新的结点，只能通过调整树中结点的指针，（没有此要求的情况下，当然可以中序遍历BST然后建立新的双向链表结点，形参有序的双向列表。
void ConvertNode(BiTNode* pNode, BiTNode** pLastNodeInList)
{
if (pNode == nullptr)
{
return;
}
BiTNode* pCurrent = pNode;
if (pCurrent->lchild != nullptr)
{
ConvertNode(pCurrent->lchild, pLastNodeInList);
}
pCurrent->lchild = *pLastNodeInList;
if (*pLastNodeInList != nullptr)
{
(*pLastNodeInList)->rchild = pCurrent;
}
*pLastNodeInList = pCurrent;
if (pCurrent->rchild != nullptr)
{
ConvertNode(pCurrent->rchild, pLastNodeInList);
}
}
BiTNode* Convert(BiTNode* pRootOfTree)
{
BiTNode* pLastNodeInList = nullptr;
ConvertNode(pRootOfTree, &pLastNodeInList);
//pLastNodeInList指向双向列表的尾巴结点
//需求求得该双向列表的头结点
BiTNode* pHeadOfList = pLastNodeInList;
while (pHeadOfList != nullptr && pHeadOfList->lchild != nullptr)
{//向左走到双向列表的头
pHeadOfList = pHeadOfList->lchild;
}
return pHeadOfList;
}
2.1BST转换成双向列表测试：
#include "stdafx.h"
#include<stack>
#include<iostream>
using namespace std;
typedef int KeyType;
typedef int ElemType;
/*二叉树的结点存储结构，二叉链表存储结构*/
typedef struct BiTNode{
KeyType data;
int multiplicity;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
/*
BiTNode:是结构类型
BiTree：是指向结点BiTNode的指针类型
*/
int _tmain(int argc, _TCHAR* argv[])
{
int MyArray[6] = { 4, 2, 6, 1, 3, 5 };
BiTree T=nullptr;
for (int i = 0; i < 6; i++)
{
InsertBST(T, MyArray[i]);
}
InOrderTraverseLoopE2(T, printVal);//1 2 3 4 5 6
//bug! 2018年9月12日bugfixed!
BiTNode* p = Convert(T);
cout << endl;
while (p != nullptr )
{//向左走到双向列表的头
cout << p->data << " ";
p = p->rchild;
}
cout << endl;
system("pause");
return 0;
}
/*
输出：
1 2 3 4 5 6
1 2 3 4 5 6
请按任意键继续. . .
*/3.BST转双向列表变种题
将二叉搜索树转换成一个递增的排序的双向列表：
根据任意输入创建一颗二叉搜索树，第一个原始是根结点原始，且元素可重复（通过在结点中设置元素的重复度multiplicity）
在转换过程中不能创建新结点，只能调整指针，转换完成后从头到尾巴打印双向列表：
二叉排序树BST 二叉树的遍历 BST转双向列表
上一篇： 双向链表的实现