二叉搜索树

数据结构

struct BST
{
    int data;
    BST *left;
    BST *right;
    BST *parent;
};

前序遍历：A,B,C

中序遍历：B,A,C

后续遍历：B,C,A

递归

前序遍历

void PreOrderTraversal(BST *root)
{
    if (root == NULL)
        return;

    cout << root->data << " ";
    PreOrderTraversal(root->left);
    PreOrderTraversal(root->right);
}

中序遍历

void InOrderTraversal(BST *root)
{
    if (root == NULL)
        return;

    InOrderTraversal(root->left);
    cout << root->data << " ";
    InOrderTraversal(root->right);
}

后续遍历

void PostOrderTraversal(BST *root)
{
   if (root == NULL)
        return;

    PostOrderTraversal(root->left);
    PostOrderTraversal(root->right);
    cout << root->data << " ";
}

插入

BST* InsertBST(BST *root, int data)
{
	static BST *prev = NULL;

	if (root == NULL)
	{
		BST *n = new BST;
		memset(n, 0, sizeof(BST));
		n->data = data;

		if (prev == NULL)
			;
		else if (data > prev->data)
			prev->right = n;
		else
			prev->left = n;

        n->parent = prev;

		return n;
	}
	
	prev = root;
	if (data > root->data)
		InsertBST(root->right, data);
	else
		InsertBST(root->left, data);

	return root;
}

---

删除有三种情况：

• 删除的是叶子节点
• 删除节点包含1个孩子节点
• 删除节点包含2个孩子节点

删除

void DeleteBST(int data)
{

}

非递归

前序遍历

void PreOrderTraversal
{

}

中序遍历

void InOrderTraversal
{

}

后序遍历

void PostOrderTraversal
{

}

插入

BST* InsertBST(BST *root, int data)
{
    BST *n = new BST;
    memset(n, 0, sizeof(BST));
    n->data = data;

    if (root == NULL)
        root = n;
    else
    {
        BST *next = root;
        BST *prev = NULL;
        while(next)
        {
            prev = next;
            if (data > next->data)
                next = next->right;
            else
                next = next->left;
        }

        if (data > prev->data)
            prev->right = n;
        else
            prev->left = n;

        n->parent = prev;
    }

    return n;
}

删除

void DeleteBST(int data)
{

}

DEMO

#include "pch.h"
#include <iostream>
#include <memory.h>

using namespace std;

class BST;
void Delete(BST *root);
BST *gRoot = NULL;

class BST
{
public:
	int data;
	BST *left;
	BST *right;
	BST *parent;

	BST()
	{
	
	}
	BST(int data)
	{
		this->data = data;
		left = NULL;
		right = NULL;
		parent = NULL;
	}

	~BST()
	{
	
	}
};


#if 0
BST* InsertBST(BST *root, int data)
{
	BST *n = new BST;
	memset(n, 0, sizeof(BST));
	n->data = data;

	if (root == NULL)
		root = n;
	else
	{
		BST *next = root;
		BST *prev = NULL;
		while (next)
		{
			prev = next;
			if (data > next->data)
				next = next->right;
			else
				next = next->left;
		}

		if (data > prev->data)
			prev->right = n;
		else
			prev->left = n;

		n->parent = prev;
	}

	return n;
}
#endif

BST* InsertBST(BST *root, int data)
{
	static BST *prev = NULL;

	if (root == NULL)
	{
		BST *n = new BST(data);

		if (prev == NULL)
			;
		else if (data > prev->data)
			prev->right = n;
		else
			prev->left = n;

		n->parent = prev;

		return n;
	}
	
	prev = root;
	if (data > root->data)
		InsertBST(root->right, data);
	else
		InsertBST(root->left, data);

	return root;
}

void PreOrderTraversal(BST *root)
{
	if (root == NULL)
		return;

	cout << root->data << " ";
	PreOrderTraversal(root->left);
	PreOrderTraversal(root->right);
}

void InOrderTraversal(BST *root)
{
	if (root == NULL)
		return;
	InOrderTraversal(root->left);
	cout << root->data << " ";
	InOrderTraversal(root->right);
}

void PostOrderTraversal(BST *root)
{
	if (root == NULL)
		return;

	PostOrderTraversal(root->left);
	PostOrderTraversal(root->right);
	cout << root->data << " ";
}

void DeleteBST(BST *root, int data)
{
	if (root == NULL)
		return;

	if (data == root->data)
		return Delete(root);
	else if (data > root->data)
		DeleteBST(root->right, data);
	else
		DeleteBST(root->left, data);
}

BST * RightAdjustNode(BST *node)
{
	while (node->left)
		node = node->left;

	return node;
}

void Delete(BST *root)
{
	if (root == NULL)
		return;

	BST *AdjustNode = NULL;

	//status 1 删除叶子节点
	if (root->left == NULL && root->right == NULL)
	{
		if (root->parent == NULL)
			;
		else if (root->parent->left == root)
			root->parent->left = NULL;
		else
			root->parent->right = NULL;

		delete root;
	}
	//status 2 有两个孩子节点 采用后驱节点
	else if (root->left != NULL && root->right != NULL)
	{
		//查找后驱节点
		AdjustNode = RightAdjustNode(root->right);
		//后驱节点替换删除节点的值
		if (root->parent == NULL)
			gRoot->data = AdjustNode->data;
		else if (root->parent->left == root)
			root->parent->left->data = AdjustNode->data;
		else
			root->parent->right->data = AdjustNode->data;
		//删除后驱节点
		Delete(AdjustNode);
	}
	//status 3 有一个孩子节点
	else
	{
		//查找孩子节点
		AdjustNode = (root->left != NULL ? root->left : root->right);
		//孩子节点替换删除节点
		if (root->parent == NULL)
			gRoot = AdjustNode;
		else if (root->parent->left == root)
			root->parent->left = AdjustNode;
		else
			root->parent->right = AdjustNode;
		//删除孩子节点
		delete root;
	}

	return;
}




int main()
{
	int data;
	bool flag = false;

	while (cin >> data)
	{
		if (flag == false)
		{
			gRoot = InsertBST(gRoot, data);
			flag = true;
		}
		else
		{
			InsertBST(gRoot, data);
		}
	}

	cout << "PreOrder " << endl;
	PreOrderTraversal(gRoot);
	cout << endl;
	cout << "InOrder " << endl;
	InOrderTraversal(gRoot);
	cout << endl;
	cout << "PostOrder " << endl;
	PostOrderTraversal(gRoot);

	cout << endl;
	cout << "Input a data to delete:" << endl;
#if 0
	cout << endl;
	cout << "delete 1" << endl;
	DeleteBST(gRoot, 1);
	InOrderTraversal(gRoot);
#endif
#if 0
	cout << endl;
	cout << "delete 3" << endl;
	DeleteBST(gRoot, 3);
	InOrderTraversal(gRoot);
#endif
#if 1
	cout << endl;
	cout << "delete 6" << endl;
	DeleteBST(gRoot, 6);
	InOrderTraversal(gRoot);
#endif

	return 0;
}

1
3
5
2
6
^Z
PreOrder
1 3 2 5 6
InOrder
1 2 3 5 6
PostOrder
2 6 5 3 1

ending