纯C++代码详解二叉树相关操作
介绍
二叉树是一种非常常见的数据结构，适用于处理需要具有层级关系的数据。在本文中，我们将详细讲解如何使用C++来实现二叉树的基本操作，包括创建、遍历、插入、删除等。
创建二叉树
定义二叉树节点
在C++中实现二叉树的概念，需要先定义二叉树节点的结构，代码如下：
struct BinaryTreeNode
{
int value; // 节点的值
BinaryTreeNode* left; // 左子节点
BinaryTreeNode* right; // 右子节点
};
创建二叉树
创建一个二叉树对象，需要一个根节点，代码如下：
BinaryTreeNode* root = new BinaryTreeNode;
root->value = 1;
root->left = new BinaryTreeNode;
root->left->value = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = new BinaryTreeNode;
root->right->value = 3;
root->right->left = NULL;
root->right->right = NULL;
这个二叉树的结构是这样的：
1
/ \
2 3
遍历二叉树
遍历二叉树有三种常见的方法：前序遍历、中序遍历、后序遍历。以下分别为三种遍历方式的代码。
前序遍历
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
void PreOrderTraversal(BinaryTreeNode* node)
{
if(node)
{
cout << node->value << "->";
PreOrderTraversal(node->left);
PreOrderTraversal(node->right);
}
}
中序遍历
中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
void InOrderTraversal(BinaryTreeNode* node)
{
if(node)
{
InOrderTraversal(node->left);
cout << node->value << "->";
InOrderTraversal(node->right);
}
}
后序遍历
后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
void PostOrderTraversal(BinaryTreeNode* node)
{
if(node)
{
PostOrderTraversal(node->left);
PostOrderTraversal(node->right);
cout << node->value << "->";
}
}
插入节点
插入左子节点
如果一个节点没有左子节点，我们可以通过如下代码给它插入一个：
BinaryTreeNode* node = new BinaryTreeNode;
node->value = 4;
node->left = NULL;
node->right = NULL;
root->left->left = node;
这个二叉树的结构变成了这样：
1
/ \
2 3
/
4
插入右子节点
如果一个节点没有右子节点，我们可以通过如下代码给它插入一个：
BinaryTreeNode* node = new BinaryTreeNode;
node->value = 5;
node->left = NULL;
node->right = NULL;
root->left->right = node;
这个二叉树的结构变成了这样：
1
/ \
2 3
/ \
4 5
删除节点
删除叶子节点
如果要删除一个叶子节点，只需要把它的父节点的指针指向NULL即可。
delete root->left->right;
root->left->right = NULL;
这个二叉树的结构变成了这样：
1
/ \
2 3
/
4
删除非叶子节点
删除非叶子节点需要注意两种情况：被删除节点有一个子节点或两个子节点。对于只有一个子节点的节点，我们将其子节点向上移动即可。对于有两个子节点的节点，我们需要找到其后继节点，用后继节点替换被删除节点。
// 寻找一个节点的后继节点
BinaryTreeNode* GetSuccessor(BinaryTreeNode* node)
{
if(node->right == NULL)
return NULL;
BinaryTreeNode* p = node->right;
while(p->left != NULL)
p = p->left;
return p;
}
// 删除节点
void DeleteNode(BinaryTreeNode* root, int value)
{
if(!root)
return;
if(root->value == value)
{
if(!root->left && !root->right)
{
delete root;
root = NULL;
}
else if(root->left && !root->right)
{
BinaryTreeNode* temp = root->left;
*root = *temp;
delete temp;
}
else if(!root->left && root->right)
{
BinaryTreeNode* temp = root->right;
*root = *temp;
delete temp;
}
else
{
BinaryTreeNode* successor = GetSuccessor(root);
root->value = successor->value;
DeleteNode(root->right, successor->value);
}
}
else if(root->value > value)
DeleteNode(root->left, value);
else
DeleteNode(root->right, value);
}
示例
下面是一个完整的二叉树的示例，显示了如何创建、遍历、插入和删除二叉树节点。
#include <iostream>
using namespace std;
struct BinaryTreeNode
{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
};
void PreOrderTraversal(BinaryTreeNode* node)
{
if(node)
{
cout << node->value << "->";
PreOrderTraversal(node->left);
PreOrderTraversal(node->right);
}
}
void InOrderTraversal(BinaryTreeNode* node)
{
if(node)
{
InOrderTraversal(node->left);
cout << node->value << "->";
InOrderTraversal(node->right);
}
}
void PostOrderTraversal(BinaryTreeNode* node)
{
if(node)
{
PostOrderTraversal(node->left);
PostOrderTraversal(node->right);
cout << node->value << "->";
}
}
BinaryTreeNode* GetSuccessor(BinaryTreeNode* node)
{
if(node->right == NULL)
return NULL;
BinaryTreeNode* p = node->right;
while(p->left != NULL)
p = p->left;
return p;
}
void DeleteNode(BinaryTreeNode* root, int value)
{
if(!root)
return;
if(root->value == value)
{
if(!root->left && !root->right)
{
delete root;
root = NULL;
}
else if(root->left && !root->right)
{
BinaryTreeNode* temp = root->left;
*root = *temp;
delete temp;
}
else if(!root->left && root->right)
{
BinaryTreeNode* temp = root->right;
*root = *temp;
delete temp;
}
else
{
BinaryTreeNode* successor = GetSuccessor(root);
root->value = successor->value;
DeleteNode(root->right, successor->value);
}
}
else if(root->value > value)
DeleteNode(root->left, value);
else
DeleteNode(root->right, value);
}
int main()
{
BinaryTreeNode* root = new BinaryTreeNode;
root->value = 1;
root->left = new BinaryTreeNode;
root->left->value = 2;
root->left->left = NULL;
root->left->right = NULL;
root->right = new BinaryTreeNode;
root->right->value = 3;
root->right->left = NULL;
root->right->right = NULL;
cout << "preorder traversal: ";
PreOrderTraversal(root);
cout << endl;
cout << "inorder traversal: ";
InOrderTraversal(root);
cout << endl;
cout << "postorder traversal: ";
PostOrderTraversal(root);
cout << endl;
BinaryTreeNode* node = new BinaryTreeNode;
node->value = 4;
node->left = NULL;
node->right = NULL;
root->left->left = node;
cout << "preorder traversal after inserting 4: ";
PreOrderTraversal(root);
cout << endl;
BinaryTreeNode* node2 = new BinaryTreeNode;
node2->value = 5;
node2->left = NULL;
node2->right = NULL;
root->left->right = node2;
cout << "preorder traversal after inserting 5: ";
PreOrderTraversal(root);
cout << endl;
DeleteNode(root, 2);
cout << "preorder traversal after deleting 2: ";
PreOrderTraversal(root);
cout << endl;
return 0;
}
这个程序输出的结果如下：
preorder traversal: 1->2->3->
inorder traversal: 2->1->3->
postorder traversal: 2->3->1->
preorder traversal after inserting 4: 1->2->4->3->
preorder traversal after inserting 5: 1->2->4->5->3->
preorder traversal after deleting 2: 1->4->5->3->
可以看到，通过这个代码示例，我们实现了(1) 创建一个二叉树；(2) 实现三种遍历方式；(3) 向二叉树中插入节点；(4) 删除二叉树中的节点。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：纯C++代码详解二叉树相关操作 - Python技术站
微信扫一扫 
支付宝扫一扫 