即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[置顶] c++排序二叉树的出现的私有函数讨论,以及二叉树的删除操作详细解析

编程语言 qq874455953 10℃ 0评论
本文目录
[隐藏]

1.c++排序二叉树的出现的私有函数讨论, 以及二叉树的删除操作详解

标签(空格分隔): c++


1.1.前言

我在c++学习的过程中, 最近打了一个排序二叉树的题目,题目中出现了私有函数成员,当时没有理解清楚这样设置的用意,导致题目没有做出来,后来终于想清楚,所以特地写这一篇来分享给大家,同时加深印象。有出错的地方希望给位朋友斧正。


1.2.题目

先看题目, 给定二叉树类的声明, 要求写出其定义, 并且要求通过各种例子


二叉树类定义

#ifndef BT_TREE
#define BT_TREE
#include 
using namespace std;
struct node {                          
    int ele;
    node* left;
    node* right;
    node(int e) :left(0), right(0) {
        ele = e;
    }
};
class BinaryTree {
private:                        //注意,这里表示一个树是用一个根节点来表示
    node* root;                 //这棵树,而网上绝大多数都是把node的参数
                                //放到类的私有变量里,这也决定了
                                //我们不能用网上的做法来搞
    void MemoryDelete(node* p);
    static void BuildTree(const node* Source_Root, node* &Target_Root);
    static void BuildTree(const int* arr, int len, node* &root);
    static void preorder(const node* p);
public:
    BinaryTree();
    BinaryTree(const BinaryTree&);
    BinaryTree(const int* arr, int len);
    void ResetTree(const int* arr, int len);
    ~BinaryTree();
    void clear();
    void insert(int ele);
    void Delete(int ele);
    void print();
};
#endif


**总起:


这个题主要理解清楚放到私有成员的static函数用意, static 函数,参数是node* 表示树的根节点,可以在没有对象时调用**这样就决定了我们使用递归的时候利用的就是我们的私有成员函数。


1.3.1.私有的 void MemoryDelete(node* p)函数


void BinaryTree::MemoryDelete(node* p) {                 //用于树的数据删除,被析构函数和clear,reset函数调用。    为什么不在clear和reset函数里写呢?
    if (p != NULL) {                                                    //因为我需要用递归,而如果我递归clear和reset是不可能成功的,因为我不可能递归作用于对象的函数(也就是
        MemoryDelete(p->left);                           //先要有对象)
        MemoryDelete(p->right);
        delete p;
        p = NULL;
    }
}

1.4.2.私有的 void BinaryTree::BuildTree(const node* Source_Root, node* &Target_Root) 函数

void BinaryTree::BuildTree(const node* Source_Root, node* &Target_Root) {     // static 函数   参数是node* 表示树的根节点, 可以在没有对象时调用
    if (Source_Root == NULL) {                                               // 但是这里的递归 你要把参数理解成 每个节点 而不是根节点
        Target_Root = NULL;
    }
    else {
        Target_Root = new node(Source_Root->ele);
        BuildTree(Source_Root->left, Target_Root->left);
        BuildTree(Source_Root->right, Target_Root->right);                   //相当于对每个节点进行拷贝, 如果你只是想着传入的是 Source_Root->left, Target_Root , 那么就很难递归了
    }
}   

1.5.3.私有的void BinaryTree::BuildTree(const node* Source_Root, node* &Target_Root)函数

void BinaryTree::BuildTree(const node* Source_Root, node* &Target_Root) {     // static 函数   参数是node* 表示树的根节点, 可以在没有对象时调用
    if (Source_Root == NULL) {                                               // 但是这里的递归 你要把参数理解成 每个节点 而不是根节点
        Target_Root = NULL;
    }
    else {
        Target_Root = new node(Source_Root->ele);
        BuildTree(Source_Root->left, Target_Root->left);
        BuildTree(Source_Root->right, Target_Root->right);                   //相当于对每个节点进行拷贝, 如果你只是想着传入的是 Source_Root->left, Target_Root , 那么就很难递归了
    }
}   

1.6.4.私有的void BinaryTree::BuildTree(const int* arr, int len, node* &root) 函数

void BinaryTree::BuildTree(const int* arr, int len, node* &root) {      // static 函数   参数是node* 表示树的根节点, 可以在没有对象时调用
    for (int i = 0; i < len; i++) {                                     // 这里没有使用递归
        int ele = arr[i];
        node* tmp = root;
        if (tmp == NULL) {
            root = new node(ele);
        }

        while (tmp != NULL) {
            if (ele < tmp->ele && tmp->left == NULL) {
                tmp->left = new node(ele);
                break;
            }
            else if (ele < tmp->ele && tmp->left != NULL) {
                tmp = tmp->left;
            }
            else if (ele > tmp->ele && tmp->right == NULL) {
                tmp->right = new node(ele);
                break;
            }
            else if (ele > tmp->ele && tmp->right != NULL) {
                tmp = tmp->right;
            }
            else {
                return;
            }
        }
    }

}

1.7.5.4.私有的void BinaryTree::BuildTree(const int* arr, int len, node* &root) 函数

void BinaryTree::preorder(const node* p) {                              // static 函数  参数是node* 表示树的根节点, 可以在没有对象时调用
    if (p != NULL) {
        cout << p->ele << " ";
        preorder(p->left);
        preorder(p->right);
    }
}                   // static 函数

1.8.5.排序二叉树删除操作


void BinaryTree::Delete(int ele) {     
    if (root == NULL) {                          //如果树为空的话就直接退出函数, 要是没有这句话,后面
        return;                                  //point->ele就会报错,因为为树为空的时候,root为空
    }
    node* point = root;                          //point表示删除元素在 二叉树中的位置
    node* father = NULL;                           father表示point的父节点
    while (point->ele != ele) {                  //寻找删除元素在树中位置
        father = point;
        if (ele < point->ele) {
            point = point->left;
        }
        else {
            point = point->right;
        }
        if (point == NULL) {
            return;
        }

    }
    //若p没有左结点,直接用p的右结点取代它(把p的父节点原本指向p改变为p的父节点指向p的右节点).
    if (point->left == NULL) {           //  如果是根节点要单独考虑,因为根节点是没有父节点的,
        if (point == root) {
            root = root->right;
        } 
        else {
            if (father->left == point) {       //判断待删除结点是其双亲结点的左节点  
                father->left = point->right;   
            }
            else {
                father->right = point->right;
            }
        }
        delete point; 
        point = NULL;
//如果有左节点,那么找到被删节点左边最大的元素(以被删元素左节点为根的子树的最右边元素),把这个元素的值来替换被删节点的元素值,并且删除被删节点左边最大的元素。
    }else {

        node* r = point->left;                 //r表示被删节点左边最大的元素(以被删元素左节点为根的子树的最右边元素)的位置
        father = point;                             //father表示r的父节点
        while (r->right != NULL) {                  //找到左子树最大元素
            father = r;
            r = r->right;
        }
        if (father == point) {                   //如果father == point 表示while循环没有进去过,就表示被删节点的左节点就是左子树最大值,那么我们删除的这个节点在,所以我们要令父节点和最大元素的左子树连起来
            father->left = r->left;
        }
        else {
            father->right = r->left;       //我们要令父节点和最大元素的右子树连起来
        }
        point->ele = r->ele;
        delete r;
        r = NULL;
    }


}

如需要源码请点我

转载请注明:CodingBlog » [置顶] c++排序二叉树的出现的私有函数讨论,以及二叉树的删除操作详细解析

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情