二叉树的基本操作:创建、查找、插入、遍历、还原二叉树
程序员文章站
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;
}
上一篇: Android----复制到剪切板