博客

二叉树的操作集

0.预先准备

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode {
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

1. 遍历树
   
   1.1先序遍历

void PreorderTraversal(BinTree BT)
{
	if (BT) {
		printf("%d ", BT->Data);
		PreorderTraversal(BT->Left);
		PreorderTraversal(BT->Right);
	}
}

1.2中序遍历

void InorderTraversal(BinTree BT)
{
	if (BT) {
		InorderTraversal(BT->Left);
		printf("%d ", BT->Data);
		InorderTraversal(BT->Right);
	}
}

2.树的查找

2.1查找最大值

Position FindMax(BinTree BST) {
	Position temp;
	if (BST == NULL) return BST;
	for (temp = BST; temp->Right != NULL; temp = temp->Right);
	return temp;
}

2.2查找最小值

Position FindMin(BinTree BST) {
	Position temp;
	if (BST == NULL) return BST;
	for (temp = BST; temp->Left != NULL; temp = temp->Left);
	return temp;
}

2.3查找特殊元素

Position Find(BinTree BST, ElementType X) {
	if (!BST)
		return NULL;
	if (X < BST->Data)
		return Find(BST->Left, X);
	else if (X > BST->Data)
		return Find(BST->Right, X);
	else
		return BST;
}

3.树的插入

BinTree Insert(BinTree BST, ElementType X) {
	if (!BST) {
		BST = (BinTree)malloc(sizeof(struct TNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
		return BST;
	}
	if (BST->Data > X) {
		BST->Left = Insert(BST->Left, X);
	}
	else if (BST->Data < X) {
		BST->Right = Insert(BST->Right, X);
	}
	return BST;
}

4.树的删除

BinTree Delete(BinTree BST, ElementType X) {
	if (!BST) {
		printf("Not Found\n");
		return BST;
	}
	if (BST->Data == X) {
		if (BST->Left == NULL && BST->Right == NULL) {
			return NULL;
		}
		else if (BST->Left == NULL) {
			return BST->Right;
		}
		else if (BST->Right == NULL) {
			return BST->Left;
		}
		else {
			BinTree temp;
			temp = FindMin(BST->Right);
			BST->Data = temp->Data;
			BST->Right = Delete(BST->Right, temp->Data);
			return BST;
		}
	}
	else if (BST->Data < X) {
		BST->Right = Delete(BST->Right, X);
	}
	else if (BST->Data > X) {
		BST->Left = Delete(BST->Left, X);
	}
	return BST;
}

这也需要板子？还是太菜了