欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉搜索树(二叉排序树)BST与双向列表的转换

程序员文章站 2022-07-15 16:20:04
...

目录

 

1.二叉排序树(Binary Sort Tree)

1.0 BST树存储结构

 1.1BST查找

1.2BST树插入节点

1.3中序遍历BST树得到有序序列

1.4删除BST树上的一结点

1.5二叉排序树内存的释放_后序遍历删除每一个结点

1.6二叉树的后序遍历_非递归算法

2.将BST转换成双向列表

2.1BST转换成双向列表测试:

3.BST转双向列表变种题


1.二叉排序树(Binary Sort Tree)

二叉排序树又称二叉查找树(Binary Search Tree) BST

二叉排序树或者是一颗空树,或者是满足一下性质的一颗二叉树:

  1. 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
  2. 若它的右子树非空,则右子树上所有结点的值均大于它的根结点的值;
  3. 它的左/右子树分别为二叉排序树

下面是初始序列建立二叉排序树的过程:

{ 4, 2, 6, 1, 3, 5 }:

二叉搜索树(二叉排序树)BST与双向列表的转换 

 

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的指针类型
*/

二叉排序树的基本操作:

  1. 查找key
  2. 插入结点
  3. 删除结点

 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);
	}
}//SearchBST

1.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转双向列表