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

二叉树的基本操作:创建、查找、插入、遍历、还原二叉树

程序员文章站 2022-05-16 11:26:31
...

1、创建二叉树的节点(使用指针)
2、二叉树的查找
3、二叉树的创建
4、二叉树的插入操作
5、二叉树的前序、后序、中序、层序遍历
6、根据前序遍历和中序遍历还原二叉树
7、根据中序遍历和后序遍历还原二叉树

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 二叉树节点结构体
struct node
{
	int data;		// 数据域
	int layer;		// 当前节点的层次:层序遍历时,记录当前层号
	node* lchild;	// 左子树
	node* rchild;	// 右子树
};

// 二叉树节点的创建
node* newNode(int v)
{
	node* Node = new node;
	Node->data = v;
	Node->lchild = Node->rchild = nullptr;
	return Node;
}

// 二叉树的查找
void searchNode(node* root, int x, int newData)
{
	if (root == nullptr) return;

	if (root->data == x) root->data = newData;

	searchNode(root->lchild, x, newData);
	searchNode(root->rchild, x, newData);
}

// 二叉树节点的插入
void insertNode(node*& root, int x)
{
	if (root == nullptr)
	{
		root = newNode(x);
		return;
	}

	// 可根据具体性质的不同,选择插入的条件
	if (root->data > x)
		insertNode(root->lchild, x);
	else
		insertNode(root->rchild, x);
}

// 创建一颗二叉树
node* CreateNode(vector<int>& v)
{
	node* root = nullptr;
	int len = v.size();
	for (int i = 0; i < len; ++i)
	{
		insertNode(root, v[i]);
	}
	return root;
}

// 先序遍历:根-左子树-右子树
void preorder(node* root)
{
	if (root == nullptr) return;
	printf("%d\n", root->data);
	preorder(root->lchild);
	preorder(root->rchild);
}

// 中序遍历: 左子树-根-右子树
void inorder(node* root)
{
	if (root == nullptr) return;
	preorder(root->lchild);
	printf("%d\n", root->data);
	preorder(root->rchild);
}

// 后序遍历: 左子树-右子树-根
void postorder(node* root)
{
	if (root == nullptr) return;
	preorder(root->lchild);
	preorder(root->rchild);
	printf("%d\n", root->data);
}

// 层序遍历
void LayerOrder(node* root)
{
	queue<node*> q;
	q.push(root);
	root->layer = 1;	// 根节点位于第一层
	while (!q.empty())
	{
		node* now = q.front();
		q.pop();
		printf("layer = %d, data = %d\n", now->layer, now->data);

		if (now->lchild != nullptr)
		{
			now->lchild->layer = now->layer + 1;	// 左子树层号
			q.push(now->lchild);
		}
		if (now->rchild != nullptr)
		{
			now->rchild->layer = now->layer + 1;	// 右子树层号
			q.push(now->rchild);
		}
	}
}

vector<int> preOrder;	  // 先序遍历数组
vector<int> inOrder;	  // 中序遍历数组
vector<int> postOrder;    // 后序遍历数组

// 重建二叉树:根据二叉树的先序遍历和中序遍历
node* rebuildBinaryTreeFromPreOrderAndInOrder(int preL, int preR, int inL, int inR)
{
	if (preL > preR) return nullptr;

	node* root = new node;
	root->data = preOrder[preL];

	int k;
	for (k = inL; k <= inR; ++k)
	{
		if (inOrder[k] == preOrder[preL])
			break; // 在中序序列中,找到了根节点的位置(根据二叉树性质不同,比较的方式也不同)
	}

	int numLeft = k - inL; // 左子树的结点个数

	// 左子树区间
	root->lchild = rebuildBinaryTreeFromPreOrderAndInOrder(preL + 1, preL + numLeft, inL, k - 1);

	// 右子树区间
	root->rchild = rebuildBinaryTreeFromPreOrderAndInOrder(preL + numLeft + 1, preR, k + 1, inR);

	return root;
}

// 重建二叉树:根据二叉树的中序遍历和后序遍历
node* rebuildBinaryTreeFromInOrderAndPostOrder(int inL, int inR, int postL, int postR)
{
	if (postL > postR) return nullptr;

	node* root = new node;
	root->data = postOrder[postR];

	int k;
	for (k = inL; k <= inR; ++k)
	{
		if (inOrder[k] == postOrder[postR])
			break; // 在后序序列中,找到了根节点的位置(根据二叉树性质不同,比较的方式也不同)
	}

	int numLeft = k - inL; // 左子树的结点个数

	// 左子树区间
	root->lchild = rebuildBinaryTreeFromInOrderAndPostOrder(inL, k - 1, postL, postL + numLeft - 1);

	// 右子树区间
	root->rchild = rebuildBinaryTreeFromInOrderAndPostOrder(k + 1, inR, postL + numLeft, postR - 1);

	return root;
}

int main()
{
	return 0;
}