二叉树中的节点删除-----按照最底层最右边的节点收缩-白红宇

二叉树中的节点删除-----按照最底层最右边的节点收缩

阅读量：5068 次

发布时间：2019-06-12

本文共 2578 字，大约阅读时间需要 8 分钟。

package bst;import java.util.LinkedList;import java.util.Queue;public class BTDel {    static Node root;        static class Node{        int key;        Node left;        Node right;                Node(int key){            this(key,null,null);        }                Node(int key,Node left,Node right){            this.key = key;            this.left = left;            this.right = right;        }    }        public static void inorder(Node root) {        if(root==null) {            return;        }        inorder(root.left);        System.out.print(root.key+" ");        inorder(root.right);    }        public static void deletDeepest(Node root,Node d_node) {        Queue
     
       q = new LinkedList
      
       ();        Node temp;        while(!q.isEmpty()) {            temp = q.poll();            if(temp.right != null) {                if(temp.right == d_node) {                    temp.right = null;                    d_node = null;                    return;                }else {                    q.add(temp.right);                }            }            if(temp.left != null) {                if(temp.left == d_node) {                    temp.left = null;                    d_node = null;                    return;                }else {                    q.add(temp.left);                }            }        }    }         public static void deletion(Node root,int key) {        Queue
       
         q = new LinkedList
        
         ();        q.add(root);        Node temp = null;        Node key_node = null;        while(!q.isEmpty()) {            temp = q.poll();            if(temp.key == key) {                key_node = temp;            }            if(temp.left != null) {                q.add(temp.left);            }                        if(temp.right != null) {                q.add(temp.right);            }        }                int x = temp.key;        deletDeepest(root,temp);        key_node.key = x;    }        public static void main(String[] args) {        Node root = new Node(10);        root.left = new Node(11);        root.left.left = new Node(7);        root.left.right = new Node(12);        root.right = new Node(9);        root.right.left = new Node(15);        root.right.right = new Node(8);        System.out.println("Inorder traversal before deletion : ");        inorder(root);                int key = 11;                deletion(root,key);                System.out.println();                inorder(root);    }        }