2024-05-30 21:44:51
浏览数 (2)
期末复习(用c 实现二叉树的简单操作)
代码语言：javascript
复制
//
// Created by 13265 on 2023/5/25.
//
#include <queue>
# include "iostream"
# include "vector"
using namespace std;
//todo 完成数据结构中的二叉树章节的相关练习
struct Node{
int val;
Node *left, *right;
Node(int x) : val(x) ,left(nullptr), right(nullptr){};
Node(){};
};
/**
* 创建二叉树的节点
* @param root 根节点
* @return 返回创建的节点
*/
Node* createNode(Node* root, int data) {
if (root == nullptr) {
return new Node(data);
} else if (data <= root->val) {
root->left = createNode(root->left, data);
} else {
root->right = createNode(root->right, data);
}
return root;
}
/**
* 注意： 必须有序的二叉树
* 删除某个二叉树的节点
* 分为三种情况，删除的节点为叶子节点，有一个节点的节点 ，有一个子树的节点
*
*
* @param root 树的根节点
* @param index 要删除的节点val
*/
Node* deleteNode(Node *& root,int index){
if(root == nullptr){
return root;
}
//todo 先遍历找到要删除的节点
else if(root->val > index){
root->left = deleteNode(root->left, index);
}else if (root->val < index){
root->right = deleteNode(root->right, index);
}
//todo 找到了， 开始分情况删除
else{
//case1 : 要删除的节点是叶子节点
if (root->left == nullptr && root->right == nullptr){
delete root;
root = nullptr;
}
//case2 : 要删除的节点上有一个子节点
else if (root->left == nullptr || root->right == nullptr){
Node* temp = root;
//左子节点不为空
if(root->left != nullptr){
root = root->left;
}
//右子节点不为空
else{
root = root->right;
}
delete temp;
}
//case3 : 要删除的节点上有两个子节点
else{/** 为了保持二叉搜索树的性质，我们选择该结点的右子树中的最小值结点来作为替代结点（也可以选择左子树中的最大值结点）。*/
Node* temp = root->right;
/*从该结点的右子树开始，找到右子树中的最小值结点。在这个过程中，我们不断遍历右子树的左子结点，直到找到没有左子结点的结点，即为右子树中的最小值结点。*/
while(temp->left != nullptr){
temp = temp->left;
}
/*然后，我们将该最小值赋值给待删除的结点，并递归地删除该最小值结点（因为该最小值结点已经成为了待删除结点的替代结点，所以要将其从右子树中删除）。*/
root->val = temp->val;
root->right = deleteNode(root->right , temp->val);
}
}
return root;
}
/**
* 更新节点
* @param root 树的根节点
* @param oldVal 原来的节点val
* @param newVal 新的节点val
*/
void updateNode(Node *& root, int oldVal , int newVal){
if (root == nullptr){
return;
}
Node* temp = root;
//因为是有序二叉树，所以需要先删除， 然后在进行插入
deleteNode(root,oldVal);
createNode(root,newVal);
}
/**
* 二叉树的层序遍历
* @param root 二叉树根节点的指针
*/
void listNode(Node *root){
//可以有三种遍历方式
queue<Node*> que ;
que.push(root);
while (!que.empty()){
//先出队列， 然后将值输出 ，然后将该节点的子节点全部入队列
Node * temp = que.front();
que.pop();
cout<<temp->val<<" ";
if (temp->left != nullptr){
que.push(temp->left);
}
if (temp->right != nullptr){
que.push(temp->right);
}
}
}
void preOrder(Node* root){
if (root== nullptr){
return;
}
cout<<root->val<<" -> ";
if (root->left != nullptr){
preOrder(root->left);
}
if(root->right != nullptr){
preOrder(root->right);
}
}
void midOrder(Node* root){
if (root== nullptr){
return;
}
midOrder(root->left);
cout<<root->val<<" -> ";
midOrder(root->right);
}
void postOrder(Node* root){
if (root== nullptr){
return;
}
postOrder(root->left);
postOrder(root->right);
cout<<root->val<<" -> ";
}
int main(){
cout<<"test"<<endl;
//添加节点
Node* root = nullptr;
root = createNode(root, 5);
root = createNode(root, 3);
root = createNode(root, 7);
root = createNode(root, 1);
root = createNode(root, 4);
root = createNode(root, 6);
root = createNode(root, 8);
deleteNode(root,4);
cout<<"n前序遍历: "<<endl;
preOrder(root);
cout<<"n中序遍历: "<<endl;
midOrder(root);
updateNode(root,3,10);
cout<<"n后序遍历: "<<endl;
postOrder(root);
cout<<endl;
cout<<"层序遍历 "<<endl;
listNode(root);
return 0;
}
