二叉排序树的插入，删除和遍历

不想再多介绍了，直接上代码吧。

// Tree.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
using namespace std;


typedef int datatype;
#define  rootFlag -1;

typedef struct  node
{
	datatype data;
	node*    leftChild;
	node*   rightChild;
}Node,*Pnode;

//初始化树，生成一个根节点
Pnode InitializeTree() {
	Pnode root=NULL;
	root = (Pnode)malloc(sizeof(Node));
	root->leftChild = NULL;
	root->rightChild = NULL;
	root->data = rootFlag;
	return root;
}

//生成新的节点
Pnode createNode(datatype data) {
	Pnode newNode = NULL;
	newNode = (Pnode)malloc(sizeof(Node));
	newNode->data = data;
	newNode->leftChild = NULL;
	newNode->rightChild = NULL;
	return newNode;
}

//排序二叉树的插入,将新节点插入到排序二叉树中
void InsertNode(Pnode node, Pnode newNode) {
	if(newNode->data>node->data) {
		if (node->rightChild == NULL) {
			node->rightChild = newNode;
		}
		else {
			InsertNode(node->rightChild, newNode);
		}
	}
	if (newNode->data<node->data){
		if (node->leftChild == NULL) {
			node->leftChild = newNode;
		}
		else {
			InsertNode(node->leftChild, newNode);
		}
	}
}

void InsertData(Pnode root, datatype data) {
	Pnode newNode = createNode(data);
	InsertNode(root, newNode);
}

//遍历输出二叉树
void printTreeChild(Pnode node) {
	if (node !=NULL){
		if (node->leftChild != NULL) {
			printf("%d is %d's leftChild.n", node->leftChild->data, node->data);
			printTreeChild(node->leftChild);
		}
		if (node->rightChild != NULL) {
			printf("%d is %d's rightChild.n", node->rightChild->data, node->data);
			printTreeChild(node->rightChild);
		}
	}
}

void printTree(Pnode root) {
	if (root->rightChild == NULL) {
		printf("树为空！n");
	}
	else {
		printf("root value is:%dn", root->rightChild->data);
		printTreeChild(root->rightChild);
	}
}

//删除节点
void deleteNode(Pnode root, datatype deldata) {
	if (root->rightChild == NULL) {
		printf("树为空！n");
	}
	Pnode currentNode = root->rightChild;
	Pnode currentParent = root;
	//找到待删除节点的位置
	bool isLeft = false;
	while (currentNode->data != deldata) {
		currentParent = currentNode;
		if (currentNode->data < deldata) {
			currentNode = currentNode->rightChild;
			isLeft = false;
		}
		else {
			currentNode = currentNode->leftChild;
			isLeft = true;
		}
	}
	//没找到该节点
	if (currentNode == NULL) {
		printf("树中不存在值为%d的节点！n", deldata);
	}
	//找到的话，分三种情况讨论，待删除节点仅仅包含一个子节点，不包含子节点，包含左右两个节点
	if ((currentNode->leftChild == NULL) && (currentNode->rightChild == NULL)) {   //不包含子树
		printf("del：%dn", currentNode->data);
		if (isLeft) currentParent->leftChild = NULL;
		else currentParent->rightChild = NULL;
		free(currentNode);
	}else if (currentNode->leftChild != NULL && currentNode->rightChild != NULL) {      //包含左右节点
		printf("del：%dn", currentNode->data);
		//查找右子树的最小值
		Pnode minNode = currentNode->rightChild;
		Pnode minParent = currentNode;
		while (minNode->leftChild != NULL) {
			minParent = minNode;
			minNode = minNode->leftChild;
		}
		if (minNode == currentNode->rightChild) {            //右子树的最小值就是右子树的根节点
			minNode->leftChild = currentNode->leftChild;
			if (isLeft) currentParent->leftChild = minNode;
			else currentParent->rightChild = minNode;
			free(currentNode);
		}
		else {                                               //右子树的最小值在左分支上
			minParent->leftChild = minNode->rightChild;
			minNode->leftChild = currentNode->leftChild;
			minNode->rightChild = currentNode->rightChild;
			if (isLeft)currentParent->leftChild = minNode;
			else currentParent->rightChild = minNode;
			free(currentNode);
		}
	}else if (currentParent->rightChild != NULL ) {   //仅包含右子树
		printf("del：%dn", currentNode->data);
		if (isLeft) currentParent->leftChild = currentNode->rightChild;
		else currentParent->rightChild = currentNode->rightChild;
		free(currentNode);
	}else{  //仅含有左子树
		printf("del：%dn", currentNode->data);
		if (isLeft) currentParent->leftChild = currentNode->leftChild;
		else currentParent->rightChild = currentNode->leftChild;
		free(currentNode);
	}
}


int main()
{
	int dataArray[11] = { 56,42,45,32,23,36,90,65,80,87,100 };
	Pnode treeRoot = InitializeTree();
	for (int i = 0; i < 11; i++)
	{
		InsertData(treeRoot, dataArray[i]);
	}
	printTree(treeRoot);
	int delvalue;
	while (treeRoot->rightChild) {
		printf("请输入要删除的值：");
		scanf("%d", &delvalue);
		deleteNode(treeRoot, delvalue);
		printTree(treeRoot);
	}
    return 0;
}

最后

以上就是勤恳大米为你收集整理的二叉排序树的插入，删除和遍历的全部内容，希望文章能够帮你解决二叉排序树的插入，删除和遍历所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。