精华内容
下载资源
问答
  • 二叉树删除子树

    2021-01-10 17:03:04
    编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: 输入第1行为一...

    编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。

    输入格式:

    输入第1行为一组用空格间隔的整数,表示带空指针信息的二叉树先根序列,其中空指针信息用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m,表示要进行的删除操作次数。接下来m行,每行一个不等于0的整数K,表示要删除以K为根的子树。m不超过100,二叉树结点个数不超过5000。输入数据保证各结点数据值互不相等,且删除子树后二叉树不为空。

    PA567.jpg

    输出格式:

    输出为m行,每行为一组整数,表示执行删除操作后剩余二叉树的中根序列(中根序列中每个整数后一个空格)。若要删除的子树不在当前二叉树中,则该行输出0(0后无空格)。

    输入样例:

    1 5 8 0 0 0 6 0 0
    3
    5
    8
    6

    输出样例:

    1 6 
    0
    1 

    
    #include<bits/stdc++.h>
    using namespace std;
    
    struct BNode 
    {
    	string data;
    	BNode* lch, * rch;
    	BNode(string item):data(item), lch(NULL), rch(NULL){}
    };
    
    void PreOderBuild(BNode*& BT) {  //建树
        string s;
        cin>>s;
    	if (s == "0") {
    		BT = NULL;
    	}
    	else {
    		BT = new BNode(s);
    		PreOderBuild(BT->lch);
    		PreOderBuild(BT->rch);
    	}
    }
    void midOrder(BNode* root) {
    	if (!root) return;
    	midOrder(root->lch);
        cout<<root->data<<" ";
    	midOrder(root->rch);
    }
    void deletNode(BNode*& root, string goal, bool& flag) {
    	if (!root) {
    		flag |= false;
    		return;
    	}
    	if (root->data == goal) {
    		root = NULL;
    		flag |= true;
    		return;
    	}
    	deletNode(root->lch, goal, flag);
    	if(!flag) deletNode(root->rch, goal, flag);
    }
    int main() {
        BNode* BT;
    	PreOderBuild( BT);	
    	int m;
    	cin >> m;
    	string child;
    	while (m--) {
    		cin >> child;
            bool flag = false;
    		deletNode(BT, child, flag);
    		if (flag) {
    			midOrder(BT);
    			cout << endl;
    		}
    		else {
    			cout << 0 << endl;
    		}
    	}
    	return 0;
    }

     

    展开全文
  • 二叉树删除子树 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: ...

    编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。

    输入格式:

    输入第1行为一组用空格间隔的整数,表示带空指针信息的二叉树先根序列,其中空指针信息用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m,表示要进行的删除操作次数。接下来m行,每行一个不等于0的整数K,表示要删除以K为根的子树。m不超过100,二叉树结点个数不超过5000。输入数据保证各结点数据值互不相等,且删除子树后二叉树不为空。

    PA567.jpg

    输出格式:

    输出为m行,每行为一组整数,表示执行删除操作后剩余二叉树的中根序列(中根序列中每个整数后一个空格)。若要删除的子树不在当前二叉树中,则该行输出0(0后无空格)。

    输入样例:

    1 5 8 0 0 0 6 0 0
    3
    5
    8
    6
    

    输出样例:

    1 6 
    0
    1 
    

    题解:

    这题主要就是构建出一颗二叉树,然后进行遍历操作,而构建二叉树可以利用数组或结构体来实现,这里我都一一讲一下,并且说一下各自的利弊。

    完全二叉树的思路

    首先是用存储完全二叉树的思路去构建二叉树。node 表示当前节点,如果根节点从 0 开始算的话,那么它的左孩子就是 2*node+1,右孩子就是 2*node+2,参考下图理解一下,随便任意一个节点的编号乘以 2 再加 1就是左孩子的编号,加2就是右孩子的编号。

    在这里插入图片描述

    所以我们就可以利用一个数组,数组的下标就对应节点的编号,这种做法的好处是代码简单,容易理解,代码如下。

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N = 1e6+5;
    int data[N], ans[N], len;
    // data 存储节点的数据
    // ans 储存题目要求输出的中序遍历
    // len 记录ans数组中节点的个数
    
    void build_tree(int node) {
        int lnode = 2*node + 1; //计算左孩子节点的下标
        int rnode = 2*node + 2; //计算右孩子节点的下标
        int x;
        cin >> x; //读入当前节点数据
        data[node] = x; 
        if(x == 0) return ; //如果x == 0是结束标志,返回
        build_tree(lnode); //构建当前节点的左子树
        build_tree(rnode); //构建当前节点的右子树
    }
    
    bool solve(int node, int x) {
        if(data[node] == 0) return false; //data[node] == 0是结束标志,返回false
        if(data[node] == x) { //找到了需要切掉的子树的根,将data[node]修改为0
            data[node] = 0;	  //之后递归到这里就会直接返回,相当于切掉了该子树
            return true;	  //找到了要切掉的子树,返回true
        }
        bool flag = false;
        int lnode = 2*node + 1;
        int rnode = 2*node + 2;
        flag |= solve(lnode, x); //等价于flag = flag|solve(lnode,x)
        ans[len++] = data[node]; //记录中序遍历
        flag |= solve(rnode, x); // ‘|’是或运算符,如flag = true|false,则flag = true
        return flag; //返回有没有找到需要切掉的子树
    } 
    
    int main() {
        build_tree(0); //构建二叉树
        int t;
        cin >> t;
        while(t--) {
            int x;
            cin >> x;
            len = 0;
            if(!solve(0, x)) cout << 0 << endl; //没有找到,输出0,行末无空格
            else {
                for(int i=0; i < len; i++) //找到了要切的子树,输出中序遍历,行末有空格
                    cout << ans[i] << ' ';
                cout << endl; //记得换行
            }
        }
        return 0;
    }
    

    上述代码写了两个函数,一个是构建二叉树,一个是对二叉树进行中序遍历,不过要注意的就是在中序遍历时,如果遍历到了要切掉的子树的根时,也要返回,因为被切掉的子树不需要遍历。OK,提交代码后完美地来了段错误。

    在这里插入图片描述

    不难发现,这题的节点个数保证不超过5000个,也就是说最坏情况下,我们需要的data数组大小是2^5000。所以打算用完全二叉树的思路水过这道题的计划失败,老老实实写个链式存储。

    链式存储实现二叉树

    我们要用结构体去定义一个节点,一个节点有三个属性,数据 data,指向左孩子的指针 lson,指向右孩子的指针 rson。其实就是数据结构课上教的实现方法,代码如下。

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N = 5e3+5;
    int ans[N], len;
    
    struct Node {
        int data; //记录当前节点数据
        Node *lson; //左孩子指针
        Node *rson; //右孩子指针
    };
    
    Node * build_tree() {
        int x;
        cin >> x;
        if(x == 0) return NULL; //结束标志,返回NULL
        Node *p = new Node(); //申请当前节点内存空间
        p->data = x; 
        p->lson = build_tree(); //构建左子树
        p->rson = build_tree(); //构建右子树
        return p;
    }
    
    void delete_tree(Node *p) {
        if(p == NULL) return ;
        delete_tree(p->lson); //删除左子树
        delete_tree(p->rson); //删除右子树
        delete p; //释放当前节点
    }
    
    bool solve(Node *p, int x) {
        if(p == NULL) return false; //找不到要切的子树,返回false
        if(p->data == x) { //找到了要切的子树
            delete_tree(p); //调用函数删除该子树
            return true; //返回true表示找到了该子树
        }
        bool flag = false;
        int t = -1;
        if(p->lson != NULL) t = p->lson->data; //记录下左子树的根的数据
        flag |= solve(p->lson, x); 
        if(t == x) p->lson = NULL; //如果左子树为要切的子树,则将p->lson赋值为NULL,不然就变成野指针了
        ans[len++] = p->data;
        t = -1;
        if(p->rson != NULL) t = p->rson->data;
        flag |= solve(p->rson, x);
        if(t == x) p->rson = NULL;
        return flag;
    } 
    
    int main() {
        Node *head = build_tree(); //构建二叉树,并记录根节点地址
        int t;
        cin >> t;
        while(t--) {
            int x;
            cin >> x;
            len = 0;
            if(!solve(head, x)) cout << 0 << endl; //没有找到,输出0,行末无空格
            else {
                for(int i=0; i < len; i++) //找到了要切的子树,输出中序遍历,行末有空格
                    cout << ans[i] << ' ';
                cout << endl;
            }
        }
        delete_tree(head); //记得释放申请的所有空间
        return 0;
    }
    

    主要思路还是不变的,在中序遍历时如果找到了要切除的子树,则调用delete_tree函数释放掉该子树,但是有一点很麻烦的就是释放掉该子树后,原先指向该子树的指针没有修改成NULL,这样就会导致段错误。所以可以发现我在递归调用左右子树的时候加了好几段可读性很差的代码。

    利用内存池去简化代码

    上面代码我觉得主要难写的是释放要切除的子树后,还要想办法去把指向这个子树的指针修改为NULL,如果换成一道复杂的题,这个bug可能就要找好久了。还有就是动态分配的内存需要释放掉就很烦,所以内存池就是解决这些问题的。内存池可以理解成我们事先申请一整块内存,然后需要用到一个节点的时候我们就分一点给它,这样我们在写代码的时候就不需要去考虑管理这些内存了,直接在程序最后结束的时候一次性全部释放掉就行了。可能还有点抽象,看下面的代码和注释理解一下。

    const int N = 5e3+5;
    
    struct Node {
    	int data;
        Node *lson;
        Node *rson;
    }node[N]; //申请一个节点数组作为内存池
    
    Node * newnode() { //这个函数每次调用,就从内存池中拿一个新的节点并返回。
        static int cnt = -1; //静态变量,记录最后一次申请的节点的下标
        return &node[++cnt]; //返回一块内存
    }
    
    /* 看不懂上面的静态变量的可以看一下下面这个,两个等效的
    int cnt = -1;
    Node * newnode() {
    	cnt = cnt + 1;
    	return &node[cnt];
    }
    */
    

    有了上面的代码,我们就可以不用去管理内存了,在做切除子树操作时,只需要把 data 标记为 0, 代表结束的标志,而不用真正地去释放这颗子树的内存。整体的代码就像完全二叉树的思路里的代码一样了,代码如下。

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N = 5e3+5;
    int ans[N], len;
    
    struct Node {
        int data;
        Node *lson;
        Node *rson;
    }node[N]; //申请一个节点数组作为内存池
    
    Node * newnode() { //从内存池中申请一块新的内存
        static int cnt = -1;
        return &node[++cnt];
    }
    
    Node * build_tree() { //构建二叉树
        int x;
        cin >> x;
        if(x == 0) return NULL;
        Node *p = newnode(); //申请新节点
        p->data = x;
        p->lson = build_tree(); //构建左子树
        p->rson = build_tree(); //构建右子树
        return p; //返回当前构建好的这棵树
    }
    
    bool solve(Node *p, int x) {
        if(p == NULL || p->data == 0) return false; //当前树为空树或这棵树被标记为被切掉了
        if(p->data == x) { //找到了要切掉的子树的树根
            p->data = 0; //标记一下这棵树被切掉了
            return true; //返回true表示找到了要切的树
        }
        //中序遍历
        bool flag = false;
        flag |= solve(p->lson, x); //到左子树中找
        ans[len++] = p->data;
        flag |= solve(p->rson, x); //到右子树中找
        return flag;
    } 
    
    int main() {
        Node *head = build_tree(); //构建二叉树,并记录根的地址
        int t;
        cin >> t;
        while(t--) {
            int x;
            cin >> x;
            len = 0;
            if(!solve(head, x)) cout << 0 << endl; //没有找到要切除的子树,输出0,行末无空格
            else {
                for(int i=0; i < len; i++) //输出切除子树后的中序遍历序列,行末有空格
                    cout << ans[i] << ' ';
                cout << endl; //记得换行
            }
        }
        //在程序结束的时候,申请来的节点数组node[]就会被自动释放了
        return 0;
    }
    
    展开全文
  • 章节简介前5篇博客写的都是线性结构,对于有层级结构的数据需要用树形结构来描述本章的重要知识点理解有关树的基本概念和二叉树的基本概念掌握二叉树的存储结构以及遍历方法掌握树的存储结构以及树、森林、二叉树的...

    5bb16e2dc937be30cddf007da677716f.png

    章节简介

    前5篇博客写的都是线性结构,对于有层级结构的数据需要用树形结构来描述

    本章的重要知识点

    1. 理解有关树的基本概念和二叉树的基本概念
    2. 掌握二叉树的存储结构以及遍历方法
    3. 掌握树的存储结构以及树、森林、二叉树的相互转换方法
    4. 梳理掌握哈夫曼树构造方法和哈夫曼编码的设计方法

    树的基本概念

    核心一句话

    线性结构中一个结点至多只有一个直接后继,树形结构一个结点可以有一个或多个直接后继

    认识树

    看图即可,你要能区分出来哪些是树,哪些不是树

    0f363dc0e9bad6a43aefee53337db165.png

    树的相关术语

    1. 结点的度:树上任意结点所拥有的子树的数目称为该结点的度

    49cd921f9604013443c744c607d77935.gif
    1. 叶子:度为0的结点称为叶子或者终端结点

    a82362a99f9b37a1abd7f6ed3bc4cd99.gif
    1. 树的度:一棵树中所有结点的度的最大值称为该树的度,就是把所有结点的度求和
    2. 结点的层次:从根算起,根的层次为1,其余结点的层次为其双亲的层次加1

    a35d6d3cd06543feaae75c5dc53c0326.gif
    1. 树的高度:一棵树中所有结点层次数的最大值称为该树的高度或深度
    2. 还有一些小概念:有序树、无序树
    树的相关术语,一定要一开始就明确清晰,后面才好学习

    二叉树

    官方概念:二叉树是n(n≥0)个元素的有限集合,该集合或者为空,或者由一个根及两棵互不相交的左子树和右子树组成,其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树(它们中的任何一个都可以是空子树),并且这两棵子树之间有次序关系,交换位置就成为一棵不同的二叉树。

    左子树和右子树,也有的叫做左孩子和右孩子

    二叉树五种基本形态,方块表示子树

    6892eb75dba86a22296f480e582f7c3c.png

    二叉树的基本运算(不写代码,了解重点函数即可)

    1. 初始化
    2. 求双亲
    3. 求左孩子
    4. 求右孩子
    5. 建二叉树
    6. 先序遍历!!!
    7. 中序遍历!!!
    8. 后序遍历!!!
    9. 层次遍历!!! 先序遍历,中序遍历,后序遍历在考试中一般不要求手写代码,但是需要你能通过一棵树结构,输出最终的结果,这个博客结尾给大家看一下例题

    二叉树性质(很重要,细碎知识点很多)

    性质1:二叉树第i(i≥1)层上至多有2^i-1^个结点。

    不需要死记硬背,实际需要的时候画一个二叉树就可以求出来了

    性质2:深度为k(k≥1)的二叉树至多有2^k^-1个结点

    依旧可以推导出来 深度为1的二叉树 结点最多为1 深度为2的二叉树 结点最多为3 深度为3的二叉树 结点最多为7 深度为k的二叉树 结点最多为2^k^-1

    性质3:对任何一棵二叉树,若度数为0的结点(叶结点)个数为n~0~,度数为2的结点个数为n~2~,则n~0~ = n~2~+1

    这个性质需要稍微推导一下 先回答一个问题,你知道树的度数,怎么计算树的结点数 例如 树的度数为2,结点树为几,这个不难想象,会出现如下情况

    7a11f79f4f074830888e4f0f7eea6f30.png

    看到这里不难发现,存在一个公式为 树的度数+1=树的结点树 那么我们开始推导上述公式 假设 二叉树的0度,1度,2度结点个数为n~0~,n~1~,n~2~,结点总数为T T = n~0~+n~1~+n~2~ 树的度数+1 = T 树的度数怎么求?n~0~0+n~1~1+n~2~2 是树的度数 继续n~0~0+n~1~1+n~2~2 +1 = T = n~0~+n~1~+n~2~ ===> 2n~2~+1=n~0~+n~2~ ===>n~0~=n~2~+1

    好了,上述过程,争取看明白吧

    性质4:含有n个结点的完全二叉树的深度为 log~2~n +1

    这个地方引出了一个新的概念完全二叉树

    说明什么是完全二叉树之前,需要理解什么是满二叉树

    满二叉树 深度为k(k≥1)且有2^k^-1个结点的二叉树称为满二叉树

    完全二叉树 如果对满二叉树按从上到下,从左到右的顺序编号,并在最下一层删除去部分结点(删除最后一层仍有结点),如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点,那么这棵二叉树就是完全二叉树 注意 x 这个符号,表示不大于x的最大整数

    教材中,给了几个范例,偷懒我用一下

    1fe08ac595937a9fe7dd4fadd75b4691.png

    关于性质4的证明,有兴趣的自行研究一下吧

    性质5:如果将一棵有n个结点的完全二叉树按层编号,按层编号是指:将一棵二叉树中的所有n个结点按照从第一层到最大层,每层从左到右的顺序依次标记为1,2,....,n。则对任意编号i(1≤i≤n)的结点A有:

    (1)若i=1,则结点A是根;若i>1,则A的双亲编号为 i/2 。(注意 x 这个符号,表示不大于x的最大整数)

    (2)若2*i>n,则结点A既无左孩子,也无右孩子;否则A的左孩子的编号为2*i。 (

    3)若2*i+1>n,则结点A无右孩子;否则,A的右孩子编号为2*i+1;

    这个性质5有点意思,先验证一下

    36e92be7f071f866e9190ae489280cee.png

    所以这个性质稍微配合着图看一下就可以完美学会

    二叉树存储结构

    二叉树也是两类存储结构:顺序存储和链式存储

    先看顺序存储结构

    这个地方对于初学者你来说,理解即可

    对一棵完全二叉树上的所有结点按层编号,然后按照编号存储到一维数组里面即可。

    书中有个比较好的例子了,直接截图,理解一下

    af125c00c6a43ac8e2a581ac1c6aeffb.png

    重点是下面,如果一个树不是完全二叉树咋办

    教材中给的方案是,添加虚拟结点,说白了,就是凑成完全二叉树,不过注意这种解决方案缺点就是浪费空间

    21bdfe05ba8485d7d34e0464417359d6.png

    二叉树的链式存储,记住常用的叫做 二叉链表 和 三叉链表 即可,其他的在自考和期末考试中不是重点部分,选择性的看不到吧。

    二叉树的遍历

    这个有点意思了,是考试的重点,但是不是叫你写代码哦~而是手动遍历。 请注意,二叉树遍历有六种可能,我们核心关注三种

    分别是

    1. 先序遍历
    2. 中序遍历
    3. 后序遍历

    直接看图解释吧,先画一个二叉树

    31d160e7a89cc69df762da1414f2b9bd.png

    为了解决遍历问题,你要先划分好区域,找到左子树、右子树还有根

    bad50e3851484b935906be0b60de17b0.png

    先序遍历走起 1. 访问根结点 (==根结点在开头==) 2. 先序遍历左子树 3. 先序遍历右子树

    ee90db21f0b2de64eefbb73cb2abd164.gif

    中序遍历走起 4. 中序遍历左子树 5. 访问根结点 (==根结点在中间==) 6. 中序遍历右子树

    5ddb51967fe749fec96dda6389e7e9c0.gif

    后序遍历走起 1. 后序遍历左子树 2. 后序遍历右子树
    3. 访问根结点(==根结点在后头==)

    304f90f6899c3fb196239f18cedc404e.gif

    这种题就多练就可以啦~

    当然还有一种需要会,叫做二叉树的按层遍历,这个就比较简单了,自行学习一下就可以掌握

    自考真题

    二叉树遍历在自考中是一个比较重要的题目,来几道真题吧

    9c1e770a1b8aec6439fcd09ddc3dbdaa.png

    bbfcddfff9e4c817410127d386d40984.png

    50921957840a083a7f66bc51a8081d25.png

    在评论区写上你的答案吧

    与梦想老师建立关系时间

    更多内容,欢迎关注 https://dwz.cn/r4lCXEuL

    展开全文
  • printf("\n请按照先序的次序输入二叉树(如:ab三个空格表示以a为根节点,b为左子树二叉树):\n"); CreateBiTree(T);//建立二叉树T printf("\n建立二叉树后,树的深度为:%d\n", BiTreeDepth(T)); printf("先序...
  • c语言实现递归删除二叉树的的子树

    千次阅读 2019-10-17 16:11:29
    # include ...这里还有快捷的方式,就是不用递归删除子树,而是当找到要删除的结点时,修改该结点的指向左右孩子指针为NULL;这等于直接切掉了该子树。但该子树还是存在内存中。 测试结果

    在这里插入图片描述

    #include<stdio.h>
    #include <stdlib.h>
    typedef struct BiTNode{                //定义结点结构 
    	char data;
    	struct BiTNode *lchild,*rchild;    //指向左右孩子的指针 
    }BiTNode,*BiTree;                    //命名结点类型名,和指向结点的指针类型 
    
    void Release(BiTree &T){            //递归删除该结点及以下结点 
    	if(T!=NULL){
    	Release(T->lchild);
    	Release(T->rchild);
    	free(T);
    	T=NULL;		//因为free只是告诉系统这块内存我们不用了而不是物(释放了该结点,不在连接到树上) 
    						//理上面的释放所以我们要手动赋值NULL;  (虽然释放了该结点,但里面还有存放这值,这里置空) 
    	}
    }
    
    void Delete_X(BiTree &T,char x){    //递归寻找要删除的结点 
    	if(T==NULL)                    //1、树为空 
    		return;
    	
    	if(T->data==x){       //2、若T的data为想要删除的元素 则进行删除
    			Release(T);   //删除包括根节点
    		
    	}
    	if(T!=NULL){		 //3、以上情况都不是,递归向左右孩子寻找 
    		Delete_X(T->lchild, x);
    		Delete_X(T->rchild, x);
    	}
    
    }
    void CreateBiTree(BiTree &T){  //先序建立二叉树  
    	char ch;
    	scanf("%c",&ch);          
    	if(ch=='#') T=NULL;      //#代表该结点为空 ,也就是父节点没有这个孩子结点 
    	else
    	{
    		T=new BiTNode;
    		T->data=ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    void FirstTraver(BiTree T){  //先序遍历 
    	if(T){
    		printf("%c",T->data);
    		FirstTraver(T->lchild);
    		FirstTraver(T->rchild);
    	}
    } 
    
    int main()
    {
    	BiTree T; 
    	printf("请建立表:\n");
    	
    	CreateBiTree(T);
    	char ch;                
        ch=getchar();        //接收输入数据后回车的影响 
    //	BiTree K=T;
    	FirstTraver(T);     //先序遍历创建的树 
    	printf("\n");
    	printf("请输入要删除的节点:\n");
    	char del;
    	scanf("%c",&del);
    	Delete_X(T,del);      //删除该结点及其子树 
    	FirstTraver(T);       //先序遍历删除后的结果 
    	
    }             
    

    这里还有快捷的方式,就是不用递归删除子树,而是当找到要删除的结点时,修改该结点的指向左右孩子指针为NULL;这等于直接切掉了该子树。但该子树还是存在内存中。


    测试结果
    在这里插入图片描述

    展开全文
  • 今天小编就为大家分享一篇关于递归删除二叉树中以x为根的子树,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: 输入第1行为一组...
  • int IsSubTree(BiTree* root1, BiTree* root2)//判断root2是否是root1的子树 { //写自己的代码 } 思想:首先找到root1中和root2根节点相等的节点,再从该节点开始比较是否每个节点都相等 #include using ...
  • 删除二叉树中以x为根的子树

    千次阅读 2017-11-11 22:19:20
    名称:删除二叉树中以x为根的子树 说明:此程序的大部分内容,注释都解释的较为详细了。在这里需要提及一点的是此处递归函数flag传递的不是上篇中讲的引用,而是普通的变量,因为在向下传递参数(当前结点是否是x...
  • 删除节点、子树代码 本例实现逻辑为直接删除节点及其子节点,未处理存在有左右子节点并需移动逻辑,故将标题命名为为直接删除篇 存在左节点或者右节点,删除后需要对子节点移动将在善后删除篇中更新 同时存在...
  • 删除结点值为x的子树 方法一递归:
  • } } //先序遍历到值为x的子树的根结点,将其删除 //否则就继续遍历 //由于对树进行删改,要用引用类型 void PreOrder2(BTree& T, int x) { if (T != NULL) { if (T->data == x) DeleteIt(T); else { PreOrder2(T->...
  • 二叉树的建立、先中后遍历以及层次遍历,交换左右子树,凹入打印二叉树删除结点
  • 题目的地址:[url]...method=showdetail&id=1021[/url] 题目的描述: 二叉树复制和左右子树互换 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:272 测试通过:174 ...
  • void release(BiTree T) { if(!T) return; release(T->leftchild); release(T->rightchild); free(T); } void delX(BiTree T, ElemType x) { if(T==NULL) return; if(T->data==x) ... }.
  • 二叉树存储结构: typedef struct Tnode { char data; struct Tnode *lnode; struct Tnode *rnode; }Tnode; typedef Tnode* type; 问题求解: void del_release11(Tnode *root,char k) { //应该...
  • 链式存储创建二叉树: 创建一棵树: public static void main(String[] args) { //创建一棵树 BinaryTree binTree = new BinaryTree(); } 这样就完成了一棵树的创建,可能大家会疑惑,这里面什么都...
  • 二叉树删除以值x为根结点的子树

    千次阅读 2018-12-05 16:10:15
    现输入其扩展二叉树的前序遍历序列,建立二叉树,设计一个子函数,要求在该二叉树中查找值为x的结点(假设该结点一定存在),并删除以值x为根结点的子树(包括结点本身,最后输出删除后的二叉树的前序遍历序列)。...
  • //任务:删除二叉树中,所有结点值为x的结点,删去以他为根的子树。 //算法思想:要删除次结点,必须先删除他的左右子树,故应该使用后序遍历, //根据层次遍历,找到本结点的左孩子和右孩子判断左孩子右孩子的值,...
  • 删除二叉树

    千次阅读 2015-09-01 11:53:55
    删除一个二叉树很简单,但是通常我们是用递归的方式,若用迭代的方式则需要额外的空间来保存信息。如何在O(N)的时间内使用O(1)的空间来完成二叉树空间的释放呢?这是我在面试中遇到的一个问题.Morris中序遍历利用...
  • 经修改,下列代码可以释放以调用对象为根的左右子树,但找不到方法删除对象本身。 void BSTree::destory() { //释放以this为根的左右子树 if(this){ if(this->LChild){ this->LChild->...
  • 二叉树

    2021-03-28 22:06:19
    二叉树是每个结点最多有两个子树的有序树。 注意:在有序树中,虽然一个节点的孩子之间是有左右次序的,但是若该节点只有一个孩子,就无须区 分其左右次序。而在二叉树中,即使是一个孩子也有左右之分。 二叉树的5种...
  • 二叉树叶子结点的删除 之前我认为的是,只要free()掉叶子结点就可以了,但是为了避免野指针的出现,我们还需要将指向叶子结点的双亲的左右指针置为NULL! 代码 void Del_0(BiTree T) //删除叶子结点 { BiTNode *p =...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,295
精华内容 18,918
关键字:

删除二叉树的子树