精华内容
下载资源
问答
  • //删除二叉树中所有叶子节点 void DeleteLev(BiTree T,BiTree f,bool flag){ if(T){//T is not NULL if(T->l){ DeleteLev(T->l,T,true); } if(T->r){ DeleteLev(...
    //删除二叉树中的所有叶子节点
    void DeleteLev(BiTree T,BiTree f,bool flag){
        if(T){//T is not NULL
            if(T->l){
                DeleteLev(T->l,T,true);
            }
            if(T->r){
                DeleteLev(T->r,T,false);
            }else{//T is a level node
                free(T);
                if(f){// T is not root
                    if(flag)f->l = NULL;
                    else f->r = NULL;
                }
                
            }
        }
    }
    
    void main(){
        Init(T);
        DeleteLev(T,NULL,true);
    }
    
    展开全文
  • #include #include using namespace std; template class BinaryTreeNode{ public: ... cout 删除叶子结点后的二叉树先序序列为:" ; t->deletelea(root,pre); t->preOrder(root); return 0; }  
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    template<class T>
    class BinaryTreeNode{
    public:
        T data;
        BinaryTreeNode<T> *leftchild;
        BinaryTreeNode<T> *rightchild;
        BinaryTreeNode(T data = 0){
            this->data = data;
            this->leftchild = rightchild = NULL;
        }
    };
    
    template<class T>
    class BinaryTree{
    private:
        BinaryTreeNode<T> *root;
    public:
        BinaryTree(){
            this->root = NULL;
        }
        void visit(BinaryTreeNode<T> *p){
            cout << p->data << "   ";
        }
        BinaryTreeNode<T>* Create(BinaryTreeNode<T> *root);                     //创建二叉树
        void preOrder(BinaryTreeNode<T> *root);                                 //先序遍历二叉树
        void exchange(BinaryTreeNode<T> *root);                                 //交换左右子树
        void deletelea(BinaryTreeNode<T> *root,BinaryTreeNode<T> *pre);         //删除叶子结点
    };
    
    template<class T>
    BinaryTreeNode<T>* BinaryTree<T> :: Create(BinaryTreeNode<T> *root){
        char x;
        cin >> x;
        if(x == '0')
            return NULL;
        else{
            root = new BinaryTreeNode<T>(x);
            root->leftchild = Create(root->leftchild);
            root->rightchild = Create(root->rightchild);
            return root;
        }
    }
    template<class T>
    void BinaryTree<T> :: preOrder(BinaryTreeNode<T> *root){
        if(root != NULL){
            visit(root);
            preOrder(root->leftchild);
            preOrder(root->rightchild);
        }
    }
    template<class T>
    void BinaryTree<T> :: exchange(BinaryTreeNode<T> *root){
        BinaryTreeNode<T> *temp;
        if(root != NULL){
            temp = root->leftchild;
            root->leftchild = root->rightchild;
            root->rightchild = temp;
            exchange(root->leftchild);
            exchange(root->rightchild);
        }
    }
    template<class T>
    void BinaryTree<T> :: deletelea(BinaryTreeNode<T> *root,BinaryTreeNode<T> *pre){
        if(root!= NULL){
            if(root->leftchild == NULL&&root->rightchild == NULL){
                if(pre != NULL){
                    if(root == pre->leftchild)
                        pre->leftchild = NULL;
                    if(root == pre->rightchild)
                        pre->rightchild = NULL;
                free(root);
                }
            }
            else{
                pre = root;
                deletelea(root->leftchild,pre);
                deletelea(root->rightchild,pre);
            }
    
        }
    }
    int main(){
        BinaryTreeNode<char> *root;
        BinaryTreeNode<char> *pre = NULL;
        BinaryTree<char> *t;
        root = t->Create(root);
        t->preOrder(root);
        /*cout << endl << "交换后的二叉树先序序列为:" << endl;
        t->exchange(root);
        t->preOrder(root);*/
        cout << endl << "删除叶子结点后的二叉树先序序列为:" << endl;
        t->deletelea(root,pre);
        t->preOrder(root);
    return 0;
    }
    

     

    展开全文
  • 给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个...

    题目描述:
    给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。
    注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个节点也应该被删除。
    也就是说,你需要重复此过程直到不能继续删除。

    示例 1:
    输入:root = [1,2,3,2,null,2,4], target = 2
    输出:[1,null,3,null,4]
    解释:
    上面左边的图中,绿色节点为叶子节点,且它们的值与 target 相同(同为 2 ),它们会被删除,得到中间的图。
    有一个新的节点变成了叶子节点且它的值与 target 相同,所以将再次进行删除,从而得到最右边的图。

    示例 2:
    输入:root = [1,3,3,3,2], target = 3
    输出:[1,3,null,null,2]

    示例 3:
    输入:root = [1,2,null,2,null,2], target = 2
    输出:[1]
    解释:每一步都删除一个绿色的叶子节点(值为 2)。

    示例 4:
    输入:root = [1,1,1], target = 1
    输出:[]

    示例 5:
    输入:root = [1,2,3], target = 1
    输出:[1,2,3]

    提示:
    1 <= target <= 1000
    每一棵树最多有 3000 个节点。
    每一个节点值的范围是 [1, 1000] 。

    方法1:
    主要思路:解题链接汇总
    (1)后序遍历;
    (2)为了确定当前结点的前置结点,使用辅助变量进行存储;

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* post_order(TreeNode*root,TreeNode* pre,const int& target){
            if(root==nullptr){//空结点
                return nullptr;
            }
            
            post_order(root->left,root,target);
            post_order(root->right,root,target);
    
            if(root->left==nullptr&&root->right==nullptr&&root->val==target){
                if(pre==nullptr){//删除根节点
                    return nullptr;
                }
                if(pre->left==root){
                    pre->left=nullptr;
                }
                else{
                    pre->right=nullptr;
                }
                return pre;//叶子结点已经被删除
            }
            return root;
        }
        TreeNode* removeLeafNodes(TreeNode* root, int target) {
            TreeNode* pre=nullptr;//辅助结点,存储前置结点
            return post_order(root,pre,target);
        }
    };
    

    方法2:
    主要思路:
    (1)去掉辅助前置结点;

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* removeLeafNodes(TreeNode* root, int target) {
            if(root==nullptr){
                return nullptr;
            }
            
            root->left=removeLeafNodes(root->left,target);
            root->right=removeLeafNodes(root->right,target);
    
            if(root->left==nullptr&&root->right==nullptr&&root->val==target){
                return nullptr;
            }
            return root;
        }
    };
    
    展开全文
  • 给你一棵以root为根的二叉树和一个整数target,请你删除所有值为target 的叶子节点 。 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也...

    给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。

    注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个节点也应该被删除。

    也就是说,你需要重复此过程直到不能继续删除。

     

    示例 1:

    输入:root = [1,2,3,2,null,2,4], target = 2
    输出:[1,null,3,null,4]
    解释:
    上面左边的图中,绿色节点为叶子节点,且它们的值与 target 相同(同为 2 ),它们会被删除,得到中间的图。
    有一个新的节点变成了叶子节点且它的值与 target 相同,所以将再次进行删除,从而得到最右边的图。
    示例 2:

    输入:root = [1,3,3,3,2], target = 3
    输出:[1,3,null,null,2]
    示例 3:

    输入:root = [1,2,null,2,null,2], target = 2
    输出:[1]
    解释:每一步都删除一个绿色的叶子节点(值为 2)。
    示例 4:

    输入:root = [1,1,1], target = 1
    输出:[]
    示例 5:

    输入:root = [1,2,3], target = 1
    输出:[1,2,3]
     

    提示:

    1 <= target <= 1000
    每一棵树最多有 3000 个节点。
    每一个节点值的范围是 [1, 1000] 。

    /**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} target
     * @return {TreeNode}
     */
    var removeLeafNodes = function(root, target) {
        if(!root) return null;
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
        if(root.left === null && root.right === null && root.val === target) {
            return null;
        }
        return root;
    };

     

    展开全文
  • 如果该节点为叶子节点,则打印路径,如果当前节点不是叶节点,则继续访问它的子节点。当前节点访问结束之后,递归函数将自动回到它的父节点。因此我们在函数退出之前要在路径上删除当前节点,以确保返回父节点时路径...
  • 给你一棵以root为根的二叉树和一个整数target,请你删除所有值为target 的叶子节点 。 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也...
  • 给你一棵以root为根的二叉树和一个整数target,请你删除所有值为target 的叶子节点 。 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也...
  • 我们需要删除所有值为 target 的叶子节点,那么我们的操作顺序应当从二叉树叶子节点开始,逐步向上直到二叉树的根为止 常见的二叉树遍历,后序遍历是先遍历完所有子结点之后再遍历根结点,符合题...
  • 二叉树递归算法: ...6. 删除二叉树中所有叶子节点 7. 交换每个节点的左右子女 8. 判断一棵树是否为二叉排序树 9. 找出给定结点在二叉树中的层次 10. 判断二叉树是否为平衡二叉树 首先,创建二叉树 BiTre...
  • 4)如果该二叉树所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。 注意: 1)遍历的方法和原理估计大家都懂,这里不再赘述。...
  • 二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据成员,且小于右子树所有节点的数据成员。排序二叉树的中序遍历...
  • 二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据成员,且小于右子树所有节点的数据成员。排序二叉树的中序遍历...
  • //遍历到叶子节点的时候,将数组所有数字加到ans上 //注意:不要忘了返回的时候,删除元素 class Solution { public: int ans = 0; void dfs(vector<int>& s, TreeNode* node) { if (node == NULL)...
  • 给定一个二叉树,返回从根节点到叶子节点所有路径。 思路 参考了:https://leetcode-cn.com/problems/binary-tree-paths/solution/257java-liang-chong-hui-su-de-fang-shi-dfs-by-ustc/ 回溯在于,走到一个叶子...
  • 实现了二叉树节点的增加、查询、删除还有将二叉树变成平衡二叉树。 定义速览 深度(层数)、层、叶子、孩子、兄弟、堂兄弟。 二叉树:两个子节点,且区分左右节点。 满二叉树。 完全二叉树:最后两层可以出现子节点...
  • 二叉查找树节点删除

    千次阅读 2017-03-13 15:09:20
    简介本文将介绍如何从二叉查找树中删除某个任意的节点。由于二叉树特有的结构,即: (1)所有左子树的节点小于等于根节点 ...叶子节点删除是最简单的情况,由于叶子节点没有左右子树,删除后不会破坏原
  • 右子树中所有结点的值),树的左右结点高度(到叶子结点需要经过的最大结点数)差小于2。对一颗平衡二叉树进行中序遍历可以顺序输出所有节点的值,对树进行查找时类似二分查找,时间复杂度为log(n)。 一、排序...
  • 数据结构——二叉树

    2020-07-02 16:20:36
    二叉树结合了有序数据,链表两者的优势,在树种查找数据的素的和有序数组一样快,插入数据和删除数据的速度和链表一样快 树的概念 节点、根节点、父节点、子节点、兄弟节点 节点高度:子树的个数 树的高度:所有...
  • 满二叉树:二叉树中所有叶子结点的度都是2,且叶子结点都在同一层次上 完全二叉树:如果一个二叉树与满二叉树前m个节点的结构相同,这样的二叉树被称为完全二叉树 也就是说,如果把满二叉树从右至左、从...
  • 1 被删除的是叶子节点,直接删除; 2 被删除只有一个子节点,指针下移; 3 有两个子节点,为了不破坏树的结构,需要找出一个节点来替换当前节点。  根据二叉树的特点,当前节点大于所有左子树,小于所有右子树,  ...
  • 算法_二叉树_python

    2020-03-29 21:07:40
    二叉树的相关操作 创建二叉树 先序、中序、后续遍历 删除节点、添加节点 计算二叉树叶子个数 #二叉树  # 1)若任意节点的左子树不空,则左子树上所有结点...#定义个二叉树节点类,python无struct class btnode...
  • 树的度是树中所有结点的度的最大值,此树的度为3。 树中结点的最大层次成为树的深度或高度。此树的深度为4。 父节点A的子结点B,C,D;B,C,D也是兄弟节点 树的集合称为森林.树和森林之间有着密切的关系.删除一个树...
  • 1. 普通二叉树比如表达式树 2. 二叉查找树 BST (满足左子树所有...(1) 被删节点是叶子节点。此时将父节点的相应指针置空就可以 (2) 被删的节点只有一个子女。此时将父节点的相应指针设置为自己的子节点 (3) 被删
  •  在一棵二叉树中寻找所有路径,每条路径节点值的和为目标值sum。假设根节点的值为val,由于二叉树的子树也是二叉树,问题可以转化为在左子树与右子树上寻找路径,该路径上的节点和为sum-val。所以可以使用二叉树的...
  • 1、二叉排序树二叉排序树又称为二叉查找树。是一个具有下列属性的二叉树: 若左子树不为空,则左子树上所有节点值均小于它的根节点的值 若右子树不为空,则右子树上所有节点的值均...当删除的节点为叶子节点时,直接
  • 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 思路 路径从根节点到叶子节点,要先保存根节点,所以要用先序遍历。 因为...
  • 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前) /** ...
  • 平衡二叉树—AVL树

    2020-12-11 20:00:12
    在计算机科学,AVL树是最先发明的自平衡二叉查找树。在AVL树任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多...所有叶子节点不存在左右子树,所以平衡因子是0。
  • 输入一颗二叉树的根节点和一个整数,按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 牛客网题目链接 解题思路 首先,只有遍历到...

空空如也

空空如也

1 2 3 4 5
收藏数 89
精华内容 35
关键字:

删除二叉树中所有叶子节点