算法设计（如何实现二叉树删除操作（代码实现））

本文概述

C ++
Java
Python3

给定一棵二叉树, 通过确保树从底部开始收缩来删除它的一个节点(即被删除的节点被最底部和最右边的节点替换)。这与
BST删除
。在这里, 元素之间没有任何顺序, 因此我们将其替换为last元素。
例子：

Delete 10 in below tree10/\2030Output :30/20Delete 20 in below tree10/\2030\40Output :10/\4030

推荐：请解决
实践
首先, 在继续解决方案之前。
算法
1.
从根开始, 找到二叉树中最深和最右边的节点以及我们要删除的节点。
2.
将最深的最右边节点的数据替换为要删除的节点。
3.
然后删除最深的最右边的节点。

文章图片
C ++

// C++ program to delete element in binary tree #include < bits/stdc++.h> using namespace std; /* A binary tree node has key, pointer to left child and a pointer to right child */ struct Node { int key; struct Node *left, *right; }; /* function to create a new node of tree and return pointer */ struct Node* newNode( int key) { struct Node* temp = new Node; temp-> key = key; temp-> left = temp-> right = NULL; return temp; }; /* Inorder traversal of a binary tree*/ void inorder( struct Node* temp) { if (!temp) return ; inorder(temp-> left); cout < < temp-> key < < " " ; inorder(temp-> right); }/* function to delete the given deepest node (d_node) in binary tree */ void deletDeepest( struct Node* root, struct Node* d_node) { queue< struct Node*> q; q.push(root); // Do level order traversal until last node struct Node* temp; while (!q.empty()) { temp = q.front(); q.pop(); if (temp == d_node) { temp = NULL; delete (d_node); return ; } if (temp-> right) { if (temp-> right == d_node) { temp-> right = NULL; delete (d_node); return ; } else q.push(temp-> right); }if (temp-> left) { if (temp-> left == d_node) { temp-> left = NULL; delete (d_node); return ; } else q.push(temp-> left); } } }/* function to delete element in binary tree */ Node* deletion( struct Node* root, int key) { if (root == NULL) return NULL; if (root-> left == NULL & & root-> right == NULL) { if (root-> key == key) return NULL; else return root; }queue< struct Node*> q; q.push(root); struct Node* temp; struct Node* key_node = NULL; // Do level order traversal to find deepest // node(temp) and node to be deleted (key_node) while (!q.empty()) { temp = q.front(); q.pop(); if (temp-> key == key) key_node = temp; if (temp-> left) q.push(temp-> left); if (temp-> right) q.push(temp-> right); }if (key_node != NULL) { int x = temp-> key; deletDeepest(root, temp); key_node-> key = x; } return root; }// Driver code int main() { struct Node* root = newNode(10); root-> left = newNode(11); root-> left-> left = newNode(7); root-> left-> right = newNode(12); root-> right = newNode(9); root-> right-> left = newNode(15); root-> right-> right = newNode(8); cout < < "Inorder traversal before deletion : " ; inorder(root); int key = 11; root = deletion(root, key); cout < < endl; cout < < "Inorder traversal after deletion : " ; inorder(root); return 0; }

Java

// Java program to delete element // in binary tree import java.util.LinkedList; import java.util.Queue; class GFG{ // A binary tree node has key, pointer to // left child and a pointer to right child static class Node { int key; Node left, right; // Constructor Node( int key) { this .key = key; left = null ; right = null ; } } static Node root; static Node temp = root; // Inorder traversal of a binary tree static void inorder(Node temp) { if (temp == null ) return ; inorder(temp.left); System.out.print(temp.key + " " ); inorder(temp.right); } // Function to delete deepest // element in binary tree static void deleteDeepest(Node root, Node delNode) { Queue< Node> q = new LinkedList< Node> (); q.add(root); Node temp = null ; // Do level order traversal until last node while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp == delNode) { temp = null ; return ; } if (temp.right!= null ) { if (temp.right == delNode) { temp.right = null ; return ; } else q.add(temp.right); } if (temp.left != null ) { if (temp.left == delNode) { temp.left = null ; return ; } else q.add(temp.left); } } }// Function to delete given element // in binary tree static void delete(Node root, int key) { if (root == null ) return ; if (root.left == null & & root.right == null ) { if (root.key == key) return ; else return ; }Queue< Node> q = new LinkedList< Node> (); q.add(root); Node temp = null , keyNode = null ; // Do level order traversal until // we find key and last node. while (!q.isEmpty()) { temp = q.peek(); q.remove(); if (temp.key == key) keyNode = temp; if (temp.left != null ) q.add(temp.left); if (temp.right != null ) q.add(temp.right); } if (keyNode != null ) { int x = temp.key; deleteDeepest(root, temp); keyNode.key = x; } }// Driver code public static void main(String args[]) { 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.print( "Inorder traversal " + "before deletion:" ); inorder(root); int key = 11 ; delete(root, key); System.out.print( "\nInorder traversal " + "after deletion:" ); inorder(root); } } // This code is contributed by Ravi Kant Verma

Python3

# Python3 program to illustrate deletion in a Binary Tree# class to create a node with data, left child and right child. class Node: def __init__( self , data): self .data = https://www.lsbin.com/data self .left = None self .right = None# Inorder traversal of a binary tree def inorder(temp): if ( not temp): return inorder(temp.left) print (temp.data, end =" " ) inorder(temp.right)# function to delete the given deepest node (d_node) in binary tree def deleteDeepest(root, d_node): q = [] q.append(root) while ( len (q)): temp = q.pop( 0 ) if temp is d_node: temp = None return if temp.right: if temp.right is d_node: temp.right = None return else : q.append(temp.right) if temp.left: if temp.left is d_node: temp.left = None return else : q.append(temp.left)# function to delete element in binary tree def deletion(root, key): if root = = None : return None if root.left = = None and root.right = = None : if root.key = = key : return None else : return root key_node = None q = [] q.append(root) while ( len (q)): temp = q.pop( 0 ) if temp.data = https://www.lsbin.com/= key: key_node = temp if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) if key_node : x = temp.data deleteDeepest(root, temp) key_node.data = x return root# Driver code if __name__ = ='__main__' : root = Node( 10 ) root.left = Node( 11 ) root.left.left = Node( 7 ) root.left.right = Node( 12 ) root.right = Node( 9 ) root.right.left = Node( 15 ) root.right.right = Node( 8 ) print ( "The tree before the deletion:" ) inorder(root) key = 11 root = deletion(root, key) print () print ( "The tree after the deletion; " ) inorder(root)# This code is contributed by Monika Anandan

输出如下