数据结构--C++版--树的多种类别

数据结构-树
怎么来理解5)呢?
5)解释开始:

先来两张红黑树:

eg1:
eg2:

以eg1为例:
从34出发:一共有七条路径,每条路径都包含了两个黑色节点!

以下为二叉搜索树的代码:
由两个头文件加一个.cpp文件组成

//这部分是tree.h
#include 
#include 
#include "tree.h"
#include "stack.h"



//插入根节点
bool InsertBtree(Btree** root, Bnode* node) {
	//这里定义了两个临时变量
	Bnode* tmp = NULL;
	Bnode* parent = NULL;

	if (!node) {
		return false;//先进行合法性判断,如果传进来的这个节点为空,那就不用插入了
	}
	else {//清空新节点的左右子树
		node->lchild = NULL;
		node->rchild = NULL;
	}

	if (*root) {//存在根节点 
		tmp = *root;//就把根节点放到tmp中
	}
	else {	//不存在根节点
		*root = node; //这个node直接就是根节点
		//注意:我们在main函数里,一开始定义根节点时,根节点就是空,所以,这个else{}必然会执行一次
		return true;//创建了根节点,完成任务,返回true
	}

	//此时,找到了根节点,根节点为tmp
	//要找到插入节点的父节点
	while (tmp != NULL) {

		//我们先假设这个tmp就是那个要找的父节点
		parent = tmp;//保存父节点=>此时,parent和tmp指向的位置是同一个
		printf("父节点： %dn", parent->data);

		if (isLess(node->data, tmp->data)) {//是否插入左子树,如果满足条件要插入左子树,就把tmp就指向左子树,否则就tmp就指向右子树
			//如果当前要插入的节点小于候选的父节点
			tmp = tmp->lchild;//tmp就指向左子树
		}
		else {
			tmp = tmp->rchild;//如果当前要插入的节点大于候选的父节点,tmp就指向右子树
		}
	}

	if (isLess(node->data, parent->data)) {//找到空位置后，进行插入
		parent->lchild = node;
	}
	else {
		parent->rchild = node;
	}

	return true;
}


int findMax(Btree* root)
{

	if (root->rchild == NULL) {
		return root->data;
	}
	return findMax(root->rchild);
}


Btree* DeleteNode(Btree* root, int key, Bnode*& deletedNode) {
	if (root == NULL)return NULL;

	if (root->data > key)
	{
		root->lchild = DeleteNode(root->lchild, key, deletedNode);
		return root;
	}
	if (root->data < key)
	{
		root->rchild = DeleteNode(root->rchild, key, deletedNode);
		return root;
	}

	deletedNode = root;

	//删除节点不存在左右子节点，即为叶子节点，直接删除
	if (root->lchild == NULL && root->rchild == NULL)return NULL;

	//删除节点存在右子节点，直接用右子节点取代删除节点
	if (root->lchild == NULL && root->rchild != NULL)return root->rchild;

	//删除节点存在左子节点，直接用左子节点取代删除节点
	if (root->lchild != NULL && root->rchild == NULL)return root->lchild;

	删除节点存在左右子节点，直接用左子节点最大值取代删除节点 
	int val = findMax(root->lchild);
	root->data = val;
	root->lchild = DeleteNode(root->lchild, val, deletedNode);
	return root;
}


Bnode* QueryByRec(Btree* root, ElemType e) {
	if (isEqual(root->data, e) || NULL == root) {
		return root;
	}
	else if (isLess(e, root->data)) {
		return QueryByRec(root->lchild, e);
	}
	else {
		return QueryByRec(root->rchild, e);
	}
}


Bnode* QueryByLoop(Bnode* root, int e) {
	while (NULL != root && !isEqual(root->data, e)) {
		if (isLess(e, root->data)) {
			root = root->lchild;
		}
		else {
			root = root->rchild;
		}
	}
	return root;
}

void PreOrderRec(Btree* root)
{
	if (root == NULL)
	{
		return;
	}

	printf("- %d -", root->data);
	PreOrderRec(root->lchild);
	PreOrderRec(root->rchild);
}


void PreOrder(Btree* root)
{
	Bnode cur;
	if (root == NULL)
	{
		return;
	}
	SqStack	stack; InitStack(stack);
	PushStack(stack, *root);	//头节点先入栈
	while (!(IsEmpty(stack)))	//栈为空，所有节点均已处理
	{
		PopStack(stack, cur);	//要遍历的节点 
		printf("- %d -", cur.data);

		if (cur.rchild != NULL)
		{
			PushStack(stack, *(cur.rchild));	//右子节点先入栈，后处理
		}
		if (cur.lchild != NULL)
		{
			PushStack(stack, *(cur.lchild)); //左子节点后入栈，接下来先处理
		}
	}
	DestroyStack(stack);
}

int main(void) {
	//二叉搜索树
	int test[] = { 19, 7, 25, 5, 11, 15, 21, 61 };	//二叉搜索树的原材料
	Bnode* root = NULL, * node = NULL;//先创建一个根节点和一个准备插入的节点

	node = new Bnode;//创建一个新节点
	node->data = test[0];//把新节点的数据存进去

	

	//通过插入树的接口,把新节点插入树中
	//这里&root是一个二级指针(即指针的地址)
	InsertBtree(&root, node);//插入根节点

	for (int i = 1; i < sizeof(test) / sizeof(test[0]); i++) {
		node = new Bnode;
		node->data = test[i]; if (InsertBtree(&root, node)) {
			printf("节点 %d 插入成功n", node->data);
		}
		else {

		}
	}
	printf("前序遍历结果： n"); PreOrderRec(root); printf("n");
	system("pause");


	printf("--------------------------------------------------------------------------------------n");
	

	//二叉搜索树删除 
	printf("删除节点 15n");
	Bnode* deletedNode = NULL;
	root = DeleteNode(root, 15, deletedNode);
	printf("二叉搜索树删除节点 15, %sn", deletedNode ? "删除成功" : "删除不 成功，节点不存在");
	if (deletedNode) delete deletedNode;


	printf("删除后，再次前序遍历结果： n"); PreOrderRec(root);
	printf("n");

	//二叉搜索树查找节点
	Bnode* node1 = QueryByLoop(root, 20);
	printf("搜索二叉搜索树，节点 20 %sn", node1 ? "存在" : "不存在");


	Bnode* node2 = QueryByLoop(root, 21);
	printf("搜索二叉搜索树，节点 21 %sn", node2 ? "存在" : "不存在");

	system("pause");
	return 0;
}

//这部分是tree.h
#ifndef    TREE_H 	
#define    TREE_H 	

#define  MAX_NODE 1024
#define isLess(a, b) (a 
//这部分是stack.h
#pragma once
#include
#include
#include "tree.h"
#define MaxSize	128	//预先分配空间，这个数值根据实际需要预估确定 
typedef struct _SqStack{
Bnode* base;	//栈底指针 
Bnode *top;	//栈顶指针
}SqStack;


bool InitStack(SqStack& S) //构造一个空栈 S
{
	S.base = new Bnode[MaxSize];//为顺序栈分配一个最大容量为 Maxsize 的空间
		if (!S.base) //空间分配失败 
			return false;
			S.top = S.base; //top 初始为 base，空栈 
		return true;
}


bool PushStack(SqStack& S, Bnode e) // 插入元素 e 为新的栈顶元素

{
	if (S.top - S.base == MaxSize) //栈满 return false;

		*(S.top++) = e; //元素 e 压入栈顶，然后栈顶指针加 1，等价于*S.top=e; S.top++;

	return true;
}


bool PopStack(SqStack& S, Bnode& e) //删除 S 的栈顶元素，暂存在变量 e 中

{
	if (S.base == S.top) { //栈空 return false;
	}
	e = *(--S.top); //栈顶指针减 1，将栈顶元素赋给 e

	return true;
}


Bnode* GetTop(SqStack& S) //返回 S 的栈顶元素，栈顶指针不变
{
	if (S.top != S.base) { //栈非空
		return S.top - 1; //返回栈顶元素的值，栈顶指针不变
	}
	else {
		return NULL;
	}
}

int GetSize(SqStack& S) {//返回栈中元素个数 
	return (S.top-S.base);
}

bool IsEmpty(SqStack& S) {//判断栈是否为空
	if (S.top == S.base){
	return true;
}
else {
return false;
}
}

void DestroyStack(SqStack& S) {//销毁栈
	if(S.base){
	free(S.base);

	S.base = NULL; S.top = NULL;
}
}
 
运行效果: