-
2020-11-20 16:39:54
哈罗哈罗!叨叨Chen又来分享学习所得了。今天给大家分享的算法是如何在构建好的二叉树中删除用户指定的结点及以它为根的子树。注意要释放相应空间喔~
话不多说,beginning!
Punchline-------------------------------------------------------------------
Task:根据输入的广义表形式,创建二叉树,再删除二叉树指定data值为x的结点,并删除以x为根结点的子树,递归实现,注意释放内存。
Input:输入两行,第一行为表示二叉树的广义表形式,第二行为待删除子树根结点的元素x。
Output:输出一行,为删除后的树的广义表达式。
Realize:
- 创建二叉树(CreateBiTree):这里根据输入二叉树的广义表形式,结合栈的思想实现二叉树的创建(非递归算法),创建的思路如下:
- 遇到data,则建立新的结点,将结点的值指向data,结点的左右指针为NULL;
- 遇到 '(' :将前一步建立的结点入栈,设置标记flag=1表示下一步可能会有左孩子;
- 遇到 ',':设置flag=2表示下一步将会有右孩子;
- 遇到 ')':出栈,表示返回上一层,i.e.回到当前结点的父结点。
2.递归删除子树(DeleteTree):递归实现,删除思路如下:
- 如果树为NULL(也表示当递归到叶结点的时候),则返回上一层;
- 如果遇到data的值==x,则设置标记fl=1,会返回给上一层表示是x是在父结点的左孩子还是右孩子,进而删除以x为根结点的子树。
3.广义表输出删除后的二叉树(print):递归实现。
------------------------------------------------------------------------------
Let's get it!
//加载头文件;这里设置的MaxInitSIze是为限制输入的广义表的长度。
#include
//定义树结点,这里NodeTree便于结点指针的声明;
typedef
//主要功能
//创建二叉树
//main函数
int
这里的main函数设置为以上的形式,是为了满足用户输入的各类广义表形式。读者还可以在return 0前设置一个清除clear函数,将创建的二叉树清除掉,释放内存,在叨叨Chen的其他算法的文章会涉及。
关于这个算法,叨叨Chen今天先写在这里,欢迎读者提出批评和建议,叨叨Chen会采纳好的建议追加在此算法后面。
2020.10.08------------------------------------------------------------------It still comes---
更多相关内容 -
二叉树删除子树
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。输入数据保证各结点数据值互不相等,且删除子树后二叉树不为空。
输出格式:
输出为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; }
-
数据结构与算法【基础版】:4.6删除二叉树的子树
2021-09-17 10:42:23链式存储的二叉树: 删除节点分两种情况: case1:要删除的就是根节点 让根节点 == null case2:要删除一个子树 想要删除某个节点,就找到他的父节点,让父节点不再指向子节点,就删掉了链式存储的二叉树:
删除节点分两种情况:
case1:要删除的就是根节点
- 让根节点 == null
case2:要删除一个子树 - 想要删除某个节点,就找到他的父节点,让父节点不再指向子节点,就删掉了
代码:
1:测试类[TestBinaryTree]中先写好要遍历的树,然后写出对应的方法【其余代码看4.4】
/** * 删除二叉树子树操作 */ //删除一个子树 System.out.println("======="); binTree.delete(3); //检查是否删掉了5 binTree.frontShow();
2:创建二叉树[BinaryTree](写出根节点对应的方法)
public void delete(int i) { //删除一个子树 if(root.value == i){ root = null; }else { root.delete(i); } }
3:创建树节点[TreeNode](根据对应的方法,写出他的实现代码)
public void delete(int i) { //删除一个子树 TreeNode parent = this; //判断左儿子 if(parent.leftNode != null && parent.leftNode.value == i){ parent.leftNode = null; return; } //判断右儿子 if(parent.leftNode != null && parent.rightNode.value == i){ parent.rightNode = null; return; } //递归检查并删除左儿子 parent = leftNode; if(parent != null){ parent.delete(i); } //递归检查并删除右儿子 parent = rightNode; if(parent != null){ parent.delete(i); } }
结果:当删除7时候,对应子节点被删除
结果:当删除3时候,左子树下的子节点也应该删除
- 让根节点 == null
-
c++ 删除二叉树的子树_二叉树遍历
2020-11-23 14:42:50按照根的访问顺序不同,分为先序、中序、后序遍历三种,根在前面称为先序遍历...算法步骤:如果二叉树为空,则空操作,否则(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树;先序遍历秘籍:访问根,先序...按照根的访问顺序不同,分为先序、中序、后序遍历三种,根在前面称为先序遍历(DLR),根在中间称为中序遍历(LDR),根在最后称为后序遍历(LRD)。
先序遍历(根->左子树->右子树)是指先访问根,然后先序遍历左子树,再先序遍历右子树,即DLR。
算法步骤:
如果二叉树为空,则空操作,否则
(1)访问根结点;
(2)先序遍历左子树;
(3)先序遍历右子树;
先序遍历秘籍:访问根,先序遍历左子树,左子树为空或已遍历才可以遍历右子树。
如图1:先序遍历结果为:A-B-D-E-C-F-G
图1.二叉树 先序遍历程序:
void
中序遍历(左子树->根->右子树)是指中序遍历左子树,然后访问根,在中序遍历右子树,即LDR。
算法步骤;
如果二叉树为空,则空操作,否则
(1)中序遍历左子树;
(2)访问根结点;
(3)中序遍历右子树;
中序遍历秘籍:中序遍历左子树,左子树为空或已遍历才可以访问根,终须遍历右子树。
如图2.二叉树中序遍历序列为:D-B-E-A-F-G-C
图2.二叉树 后序遍历(左子树->右子树->根)是指后序遍历左子树,后序遍历右子树,然后访问根,即LRD。
算法步骤:
如果二叉树为空,则空操作,否则
(1)后序遍历左子树;
(2)后序遍历右子树;
(3)访问根结点。
后序遍历秘籍:后序遍历左子树,后序遍历右子树,左子树、右子树为空或已遍历才可以访问根。
如图3.后序遍历结果为:D-E-B-G-F-C-A
图3.二叉树 层次遍历:从左向右、从上往下一层一层遍历。
如图4.二叉树遍历结果为:A-B-C-D-E-F-G
图4.二叉树 例:二叉树如图5.写出该二叉树的先序、中序、后序、层次遍历序列。
图5.二叉树 解答:
先序遍历序列结果:A-B-C-D-E-F-G-H-J-I 中序遍历序列结果:B-C-D-A-F-E-J-H-I-G 后序遍历序列结果:D-C-B-F-J-I-H-G-E-A 层次遍历序列结果:A-B-E-C-F-G-D-H-J-I
二叉树创建
补空法是指如果左子树或右子树为空时,则用特殊字符补空,如“#”。然后按照先序遍历的顺序,得到先序遍历序列,根据该序列递归创建二叉树。
算法步骤:
(1)输入补空后的二叉树先序遍历序列;
(2)如果ch=='#',T=NULL;否则创建一个新结点T,令T->data=ch;递归创建T的左子树;递归创建T的右子树。
二叉树补空 typedef
二叉树还原:
例如:已知一棵二叉树的先序序列ABDECFG和中序序列DBEAFGC,画出这棵二叉树。
算法步骤:
(1)先序序列的第一个字符为根;
(2)在中序序列中,以根为中心划分左右子树;
(3)还原左右子树。
秘籍:先序找根(排在前面为树根),中序分左右子树。
解答:
(1)先序序列第一个结点A表示树根;中序序列中按照先序序列找到的树根A,分为左右子 树,如图6;
图6.先序找根,中序分左右子树 (2)然后左子树的三个结点DBE在先序序列排在最前面的是左子树的树根为B,代入中序序列分为左右子树D和E;对右子树重复上述操作,可得右子树树根为C,右子树的左子树为FG,右子树的右子树为空,如图7;
图7.先序找根,中序分左右子树 (3)继续对右子树的左子树结点FG重复上述操作,得根结点为F,G为右子树。最终可以确定二叉树的结构如图8.
图8.先序找根,中序分左右子树 程序:
BiTree
练习:已知一棵二叉树的后序序列DEBGFCA和中序序列DBEAFGC,画出这棵二叉树。
算法步骤:
(1)后序序列的最后一个字符为根;
(2)在中序序列中,以根为中心划分左右子树;
(3)还原左右子树。
秘籍:后序找根(排在后面为树根),中序分左右子树。
解答:
(1)后序序列最后一个结点A表示树根;中序序列中按照后序序列找到的树根A,分为左右子树,如图10;
图10.后续找根,中序分左右 (2)左子树的三个结点DBE在先序序列排在最前面的是左子树的树根为B,代入中序序列分为左右子树D和E;对右子树重复上述操作,可得右子树树根为C,右子树的左子树为FG,右子树的右子树为空,如图11;
图11.后续找根,中序分左右 (3)继续对右子树的左子树结点FG重复上述操作,得根结点为F,G为右子树。最终可以确定二叉树的结构如图12.
图12.后续找根,中序分左右 程序:
BiTree
完整程序:
1.树的遍历:
https://github.com/xinhai2017/Data-Structures-and-Algorithms/blob/master/6.3.traverse.cppgithub.com2.树的还原:
https://github.com/xinhai2017/Data-Structures-and-Algorithms/blob/master/6.2.preincreatebitree.cppgithub.com -
递归删除二叉树中以x为根的子树
2020-08-26 06:30:49今天小编就为大家分享一篇关于递归删除二叉树中以x为根的子树,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧 -
7-3 二叉树删除子树
2021-11-16 19:31:567-3 二叉树删除子树 (5 分) 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 ... -
数据结构PTA第四次练习题 二叉树删除子树
2020-11-23 17:31:03二叉树删除子树 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: ... -
PTA 二叉树删除子树 (5 分)
2022-03-28 14:56:01二叉树删除子树 (5 分) 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入... -
c++ 删除二叉树的子树_二叉树!!!数据结构与算法 看完这篇文终于搞明白了
2020-11-21 14:15:08树定义树(Tree) 是n(n>...、Tn,其中每一个集合本身又是一棵树,并且称为根的子树。此外,树的定义还需要强调以下两点:n>0时根结点是唯一的,不可能存在多个根结点,数据结构中的树只能有一个... -
leetcode树之二叉树分裂子树
2022-04-03 00:28:29文章目录1145、二叉树着色游戏1339、分裂二叉树的最大乘积 1145、二叉树着色游戏 有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中,给出二叉树的根节点 root,树上总共有 n 个节点,且 n 为奇数,其中每个... -
c语言实现递归删除二叉树的的子树
2019-10-17 16:11:29# include ...这里还有快捷的方式,就是不用递归删除子树,而是当找到要删除的结点时,修改该结点的指向左右孩子指针为NULL;这等于直接切掉了该子树。但该子树还是存在内存中。 测试结果 -
7-7 二叉树删除子树 (5 分)
2022-04-21 22:03:377-7 二叉树删除子树 (5 分) 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 ... -
【无标题】7-53 二叉树删除子树 (5 分)
2021-12-02 14:36:287-53 二叉树删除子树 (5 分) -
删除二叉树中元素值为x的结点及其子树
2020-09-22 15:32:28void DeleteTree(BiTree T) { if(T) { DeleteTree(T->lchild); DeleteTree(T->rchild); free(T); } } void Search(BiTree T,ElemType x) { SqQueue Q; if(T) { if(T->data==x) .... -
删除二叉树中所有以x为值的子树
2021-06-08 15:34:56} } //先序遍历到值为x的子树的根结点,将其删除 //否则就继续遍历 //由于对树进行删改,要用引用类型 void PreOrder2(BTree& T, int x) { if (T != NULL) { if (T->data == x) DeleteIt(T); else { PreOrder2(T->... -
c++ 删除二叉树的子树_【自考】数据结构第四章树和二叉树,期末不挂科指南,第6篇
2020-11-16 00:58:40章节简介前5篇博客写的都是线性结构,对于有层级结构的数据需要用树形结构来描述本章的重要知识点理解有关树的基本概念和二叉树的基本概念掌握二叉树的存储结构以及遍历方法掌握树的存储结构以及树、森林、二叉树的... -
【数据结构】(二叉树)二叉树删除结点值为x的子树
2019-08-01 11:17:27删除结点值为x的子树 方法一递归: -
CG.删除二叉树中以值x结点为根的子树
2021-11-01 00:42:39问题描述】编写递归算法,对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。 【输入形式】 先序序列构造二叉树,结点数据类型为字符型,空结点用'#'表示。 输入要删除的结点值。 【输出... -
Java数据结构之二叉树(Binary Tree)
2021-03-11 12:54:18顾名思义, 二叉树的每个节点最多只能包含两个子节点, 一个节点可以包含0-2个子节点, 如果是两个子节点, 也就是通常我们说的左节点和右节点, 通常子树被称作“左子树” 和“右子树”二叉树的应用很多, 也是项目... -
删除二叉树中以x为根的子树
2017-11-11 22:19:20名称:删除二叉树中以x为根的子树 说明:此程序的大部分内容,注释都解释的较为详细了。在这里需要提及一点的是此处递归函数flag传递的不是上篇中讲的引用,而是普通的变量,因为在向下传递参数(当前结点是否是x... -
数据结构习题——二叉树叶子结点的删除/删除以元素X为根的子树
2020-04-29 13:32:06二叉树叶子结点的删除 之前我认为的是,只要free()掉叶子结点就可以了,但是为了避免野指针的出现,我们还需要将指向叶子结点的双亲的左右指针置为NULL! 代码 void Del_0(BiTree T) //删除叶子结点 { BiTNode *p =... -
java使用归并删除法删除二叉树中节点的方法
2020-09-03 16:35:23主要介绍了java使用归并删除法删除二叉树中节点的方法,实例分析了java二叉树算法的相关操作技巧,需要的朋友可以参考下 -
java-二叉树中节点查找与删除子树
2022-01-07 07:40:41二叉树中节点的查找 实现的步骤:递归实现先查找当前节点,在查找当前节点的子节点,在查找当前节点的右节点。 /** * 二叉树中节点的查找 * @param rootNode * @param str */ public static Node search... -
【算法题目】【DFS】【一点资讯面试题】二叉树删除节点剩余子树数量
2022-05-12 10:38:57写一个函数,输入是树的根节点和要删除的节点的集合,删除某个节点意味着去除掉和这个节点的关联,剩下的都是子树,函数返回剩余子树数量。 input:root,{1} output:2 input:root,{1,2,5} output:2 input:... -
二叉树基础及二叉树顺序结构
2022-02-10 22:02:44二叉树基础及二叉树顺序结构 -
平衡二叉树AVL树定义、插入以及调整最小不平衡子树(C语言)
2021-07-28 18:11:08平衡二叉树(Balanced Binary Tree),简称平衡树(AVL树)——树上任一结点的左子树和右子树的高度之差不超过1。 结点的平衡因子=左子树高-右子树高。 //平衡二叉树结点 typedef struct AVLNode{ int key; //... -
求二叉树叶子结点个数交换二叉树左右子树结果不对
2017-01-04 01:49:23printf("\n请按照先序的次序输入二叉树(如:ab三个空格表示以a为根节点,b为左子树的二叉树):\n"); CreateBiTree(T);//建立二叉树T printf("\n建立二叉树后,树的深度为:%d\n", BiTreeDepth(T)); printf("先序... -
二叉树的删除操作-java
2021-08-11 07:04:38二叉树的删除操作,其中删除最小值最大值比较容易,就是一直不停的遍历二叉树的左子树和右子树,一直找到没有其左子树和右子树。然后直接将其删除就可以了 一、删除最小值(假定这个二叉树的构造是左节点小于父节点,...