精华内容
下载资源
问答
  • 删除叶子节点的话 分3步 1、找到要删除的节点 2、找到要删除的节点的父节点 3、删除节点(将其与父节点的联系断开) java实现 树类 package com.demo4; public class BinarySearchTree { Node root; public void ...

    在二叉搜索树种搜索直接采用递归就可以做到
    删除叶子节点的话
    分3步
    1、找到要删除的节点
    2、找到要删除的节点的父节点
    3、删除节点(将其与父节点的联系断开)

    java实现
    树类

    package com.demo4;
    
    public class BinarySearchTree {
        Node root;
        public void add(Node node){
            if(root == null){
                root = node;
            }
            else{
                root.add(node);
            }
        }
        public void middleshow(){
            if(root == null){
                System.out.println("This tree is Empty.");
                return;
            }
            else{
                root.middleshow(root);
            }
        }
        public Node search(int value){
            if(root == null) return null;
            else{
                return root.search(value);
            }
        }
        public Node searchParent(int value){
            if(root == null) return null;
            else{
                return root.searchParent(value);
            }
        }
        public void deleteLeaf(int value){
            if(root == null){
                return;
            }
            else{
                Node target = search(value);
                if(target == null){
                    return;
                }
                Node parent = searchParent(value);
                if(target.left == null && target.right == null){
                    if(parent.left.value == value){
                        parent.left = null;
                    }
                    else{
                        parent.right = null;
                    }
                }
            }
        }
    }
    
    

    节点类

    package com.demo4;
    
    public class Node {
        int value;
        Node left;
        Node right;
        public Node(int value){
            this.value = value;
        }
    
        public void add(Node node) {
            if(node == null){
                return;
            }
            if(node.value > this.value){
                if(this.right == null){
                    this.right = node;
                }
                else{
                    this.right.add(node);
                }
            }
            if(node.value < this.value){
                if(this.left == null){
                    this.left = node;
                }
                else{
                    this.left.add(node);
                }
            }
        }
    
        public void middleshow(Node node) {
            if(node == null){
                return;
            }
            middleshow(node.left);
            System.out.println(node.value);
            middleshow(node.right);
        }
    
        public Node search(int value) {
            if(this.value == value){
                return this;
            }
            else if(value < this.value){
    			if(this.left == null){
    				return null;	
    			}
    			return left.search(value);
    		}
    		else{
    			if(this.right == null){
    				return null;
    			}	
    			return right.search(value)
    		}
        }
    
        public Node searchParent(int value) {
            if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)){
                return this;
            }
            else{
                if(this.value > value && this.left != null){
                    return this.left.searchParent(value);
                }
                else if(this.right != null){
                    return this.right.searchParent(value);
                }
                else{
                    return null;
                }
            }
        }
    }
    
    

    测试类

    package com.demo4;
    
    public class testBST {
        public static void main(String[] args) {
            int [] arr = new int[] {7,3,10,12,5,1,9};
            BinarySearchTree bst = new BinarySearchTree();
            for(int i : arr){
                bst.add(new Node(i));
            }
    
            System.out.println(bst.searchParent(3).value);
            System.out.println(bst.searchParent(9).value);
            System.out.println(bst.searchParent(5).value);
            System.out.println("*******************************************************");
            System.out.println("原数组拍好序后:");
            bst.middleshow();
            System.out.println("*******************************************************");
            System.out.println("原树删除1,12两个叶子节点后");
            bst.deleteLeaf(1);
            bst.deleteLeaf(12);
            bst.middleshow();
        }
    }
    
    

    在这里插入图片描述

    展开全文
  • package com.njupt.acm; import java.util.Scanner; public class POJ_1577 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int levels = 0;...
    package com.njupt.acm;
    
    import java.util.Scanner;
    
    public class POJ_1577 {
    
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		
    		int levels = 0;
    		String line;
    		String[] leaves = new String[26];
    		
    		while(scanner.hasNext()){
    			line = scanner.nextLine().trim();
    			if(line.equals("*")){
    				System.out.println(preorder(leaves, levels));
    				leaves = new String[26];
    				levels = 0;
    			}else if(line.equals("$")){
    				System.out.println(preorder(leaves, levels));
    				break;
    			}else{
    				leaves[levels++] = line;
    			}
    		}
    		
    	}
    	
    	public static String preorder(String[] leaves,int levels){//将根据leaves中的行序列计算前序遍历序列
    		
    		while(levels > 0 && leaves[levels-1].length() == 0){//从leaves[]标的最后一项开始找,找到第一个非空项..
    			levels--;
    		}
    		if(levels == 0){
    			return "";
    		}
    		levels--;
    		
    		char root = leaves[levels].charAt(0);//leaves表尾存储子根
    		String[] left = new String[levels];
    		String[] right = new String[levels];
    		
    		int i;
    		for(i = 0 ; i < levels ; ++i){
    			int past = 0;
    			while(past < leaves[i].length() && leaves[i].charAt(past) < root){//找到左右子树的分界点
    				past++;
    			}
    			
    			left[i] = leaves[i].substring(0,past);
    			right[i] = leaves[i].substring(past);
    		}
    		
    		return root + preorder(left, levels) + preorder(right, levels);
    	}
    }
    

    展开全文
  • 第一种删除叶子节点() 思路: 1.找到要删除的叶子 2.找到叶子的父节点parent 3.判断叶子是parent的左子节点还是右子节点4根据前面的情况对应删除 左子节点 parent.left=null 右子节点 parent.lright=null 第二种...

    笔记示意图

    第一种删除叶子节点()

    思路:
    1.找到要删除的叶子
    2.找到叶子的父节点parent
    3.判断叶子是parent的左子节点还是右子节点4根据前面的情况对应删除
    左子节点 parent.left=null
    右子节点 parent.lright=null

    第二种情况:
    1.找到要删除的节点targetnode
    2.找到叶子的父节点parent
    3.确定targetnode的子节点是左子节点还是右子节点
    (4)确定target是parent的左子节点还是右子节点
    (5)如果targetnode有左子节点
    5.1如果targetnode是parents的左子节点
    Parent,left=targetnode.left
    5.2如果targetnode是parents的右子节点
    Parent.right=targetnode.left
    (6)如果targetnode有右子节点
    如果targetnode是parent的左子节点
    Parent,left=targetnode.right
    如果targetnode是parent的右子节点
    Parent,right=targetnode.right
    情况三 删除有两颗子树的节点

    思路
    (1)找到要删除的节点targetnode
    2.找到叶子的父节点parent
    (3)从targetnode的右子树找到最小的节点
    (4)用一个临时变量,将最小节点的值保存在tamp中
    (5)删除该最小节点
    (6)targetnode.value=temp
    本次新增了search和searchparent和delNode方法
    注意:只实现了第一种情况的删除

    public class BST {
        public static void main(String[] args) {
               int[]arr={7,3,10,12,5,1,9,2};
               BinarySortTree binarySortTree=new BinarySortTree();
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
            System.out.println("中序遍历");
            binarySortTree.infixOrder();
            //删除节点
            System.out.println("删除后");
            binarySortTree.delNode(5);
            binarySortTree.infixOrder();
        }
    }
    class  BinarySortTree{
        private Node root;
        public Node search(int value){
            if (root==null){
                return null;
            }else {
                return root.search(value);
            }
        }
        public Node searchParent(int value){
            if (root==null){
                return null;
            }else {
                return root.searchParent(value);
            }
        }
        public void delNode(int value) {
            if (root == null) {
                return;
            } else {
                //1.先找到要删除的节点
                Node targetNode = search(value);
                //如果没有找到要删除的节点
                if (targetNode == null) {
                    return;
                }
                //如果我们发现当前这颗二叉排序树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
    
                //找到targetnode的父节点
                Node parent = searchParent(value);
                //如果要删除的是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
                    //判断targetnode是左子节点还是右子节点
                    if (parent.left != null && parent.left.value == value) {
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {
                        parent.right = null;
                    }
                }
            }
        }
        public  void add(Node node){
            if (root==null){
                root=node;//如果树为空,让root指向node
    
            }else  {
                root.add(node);
            }
        }
        public  void infixOrder(){
            if (root!=null){
                root.infixOrder();
            }else {
                System.out.println("二叉排序树为空不能遍历");
            }
        }
    }
    class Node{
        int value;
        Node left;
        Node right;
        //查找要删除的节点
        //value希望删除结点的值
        public Node search(int value){
            if(value==this.value){
                return  this;
            }else if(value<this.value){
                //向左子树递归查找
                if (this.left==null){
                    return null;
                }
                return  this.left.search(value);
            }else {
                //查找结点大于当前节点
                if (this.right==null){
                    return null;
                }
                return  this.right.search(value);
            }
        }
        //查找要删除节点的父节点
    
        /**
         *
         * @param value 要找的节点的值
         * @return 要删除的节点的父节点,如果没有返回null
         */
        public  Node searchParent(int value){
              if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
                  return this;
              }else {
                  //如果查找节点的值小于当前节点的值,并且当前节点的左子节点不为空
    
                  if(value<this.value&&this.left!=null){
                      return this.left.searchParent(value);
                  }else if(value>=this.value&&this.right!=null) {
                      //注意相等情况
                      //右递归找
                      return this.right.searchParent(value);
    
                  }else {
                      //无父结点
                      return null;
                  }
              }
        }
    
        public Node(int value) {
            this.value = value;
        }
        //递归添加节点,满足二叉排序树的要求
        public void add(Node node){
            if (node==null){
                return;
            }
            //判断传入节点的值和子树根节点的值
            if(node.value<this.value){
                //如果当前节点左子节点为空
                if(this.left==null){
                   this.left=node;
                }else {
                    //递归向左子树添加
                     this.left.add(node);
                }
            }else {//节点大于当前节点
                 if(this.right==null){
                    this.right=node;
                }else {
                    //递归向右子树添加
                    this.right.add(node);
            }
        }
    }
    //中序遍历
        public void infixOrder(){
            if (this.left!=null){
                this.left.infixOrder();
            }
            System.out.println(this.value);
            if (this.right!=null){
                this.right.infixOrder();
            }
        }
    }
    
    展开全文
  • 递归删除所有叶子节点

    千次阅读 2016-11-27 21:40:04
    void BiTree::deleteLeaves(BiTreeNode *root) { if (root == NULL) return;... //表示是根节点(或者出错,跑到叶子节点了,这种情况应该不会),不删除 if (root->left) //当前节点有左子树 { if (root->left->left ||
    void BiTree::deleteLeaves(BiTreeNode *root)
    {
    if (root == NULL) return;
    if (!root->left && !root->right) return; //表示是根节点(或者出错,跑到叶子节点了,这种情况应该不会),不删除
    if (root->left) //当前节点有左子树
    {
    if (root->left->left || root->left->right) //左子树不是叶子
    deleteLeaves(root->left);
    else //当前节点的左子节点是叶子
    {
    delete root->left;
    root->left = NULL;
    }
    }
    if (root->right)
    {
    if (root->right->left || root->right->right)
    deleteLeaves(root->right);
    else //当前节点的右子节点是叶子
    {
    delete root->right;
    root->right = NULL;
    }
    }
    }
    展开全文
  • 首先想这个题的普通节点怎么做,首先删除它的子节点的叶子节点,如果返回来时它自己成了叶子节点,则要删除它自己,所以很显然是后序遍历。 然后就是怎么删除自己的问题,要删除自己,就返回null,然后让自己的父...
  • //删除二叉树中的所有叶子节点 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(...
  • 给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个...
  • 2-3树 叶子节点删除

    2020-04-18 21:10:35
    本文不再阐述关于2-3树的定义、节点的插入以及将删除的非叶子节点转换为叶子节点的方法 注意: 本文仅对2-3树 叶子节点删除操作 进行分类与讨论 定义: 2-节点: 如果某个节点包含1个权值, 那么我们称之为2-节点, ...
  • 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个节点也应该被删除。 也就是说,你需要重复此过程直到不能继续删除。 审题: 由于删除的是叶子...
  • 给你一棵以root为根的二叉树和一个整数target,请你删除所有值为target 的叶子节点 。 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也...
  • 题目描述: 给你一棵二叉树,请按以下要求的...删除叶子节点 [4,5,3] ,得到如下树结构: 1 / 2 现在删去叶子节点 [2] ,得到如下树结构: 1 现在删去叶子节点 [1] ,得到空树: [] 方法1: 主要思
  • 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也应该被删除。 也就是说,你需要重复此过程直到不能继续删除。 示例 1: 输入:root = ...
  • 给你一棵以root为根的二叉树和一个整数target,请你删除所有值为target 的叶子节点 。 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也...
  • 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target ,那么这个节点也应该被删除。 也就是说,你需要重复此过程直到不能继续删除。 示例 1: 输入:root = ...
  • 给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个...
  • 给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点; 如果新叶子节点的值恰好也是 target ,那么这个...
  • 给你一棵以root为根的二叉树和一个整数target,请你删除所有值为target的叶子节点。 注意,一旦删除值为target的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是target,那么这个节点也应该被...
  • 删除给定值的叶子节点 题解: 给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的...
  • 给你一棵以 root 为根的二叉树和一个整数 target ,请你删除所有值为 target 的 叶子节点 。 注意,一旦删除值为 target 的叶子节点,它的父节点就可能变成叶子节点;如果新叶子节点的值恰好也是 target ,那么这个...
  • void deletLeaf(BTree root) {     if (!root)  {   return;  }   if ((root->left == NULL)&&(root->right == NULL))  {  root->data = 0;   return;
  • 这里面有个特殊情况,就是查找...它也是个叶子节点。那么直接 null,而且这种情况必须先判断。否则后序会报错 public void del(int value) { if (root == null) { return; } Nod search = root.search(value); ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,618
精华内容 647
关键字:

删除叶子节点