Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "introduction to the concept of binary tree in Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Catalogue

The concept of binary tree

Why use binary tree?

What is a tree?

Terms related to trees!

Root node

Path

Parent node

Child node

Leaf node

Subtree

Visit

Layer (depth)

Keyword

Full binary tree

Complete binary tree

Five properties of binary tree

Second, search binary tree

insert

Delete

Hello, everyone. Long time no see. In this article, we will mainly explain the related concepts of binary tree, and also talk about searching binary tree (also known as binary sort tree). Let's get straight to the point. GitHub source code link

Why does the concept of binary tree use binary tree?

Why use trees? Because it usually combines the advantages of the other two data structures: one is an ordered array and the other is a linked list. Finding data items in a tree is as fast as finding data items in an ordered array, and inserting and deleting data items is as fast as a linked list. Next, let's think about these topics a little bit, and then delve into the details of the tree.

Inserting data in an ordered array is too slow, and finding data in a linked list is too slow. So later, there was a binary tree as a data structure.

What is a tree?

Before going into the binary tree, let's have a brief understanding of the concept of tree. A tree is composed of several nodes and edges, for example, cities can be regarded as nodes and traffic routes between cities as edges. Of course, to be more accurate, this example should belong to the category of the graph, the relevant knowledge points about the graph. We'll discuss it later. In the picture below, it is a tree.

Terms related to trees!

As shown in the following figure

Root node

The top node of the tree is called the root node. A tree has only one root node, which is generally the beginning of the traversal of the whole tree.

Path

Imagine going from one node in the tree to another along the edge, and the order of the nodes is called the path.

Parent node

Just like the name, it plays the role of "father" in the binary tree, and every node in the binary tree (except the root node) has an edge up to find the "parent node" of the node.

Child node

Each node may have one or more edges down to connect to other nodes, and the following nodes are called its "child nodes".

Leaf node

Nodes without children are called "leaf nodes" or "leaf nodes" for short. There is only one root in a tree, but it can have many leaf nodes.

Subtree

Each node can be used as the root of the "subtree". It and all its child nodes, children of the child nodes, etc., are contained in the subtree. As in a family, the subtree of a node contains all its descendants.

Visit

When the program control flow reaches a node, it is called "accessing" the node, usually to perform some action at that node, such as looking at the value of a data field of the node or displaying the node. If you just pass a node on the path from one node to another, you are not considered to have visited that node.

Layer (depth)

Just like us, our generation can be seen as a layer. And Mom and Dad's generation, is another layer.

Keyword

As shown in the figure, there is a value in each node, which we call a keyword.

Full binary tree

In a binary tree, if all branch nodes have left and right subtrees, and all leaf nodes are on the same level, such a binary tree is called a full binary tree. As shown in the image above.

Complete binary tree

A binary tree with n nodes is numbered from top to bottom and from left to right. If the number is I (1 n, (n is the total number of nodes of the whole tree), then I node has no right child node, on the contrary, 2i + 1 is the right child node.

Second, search binary tree

After explaining some of the basic concepts of binary tree above, let's move on to the next knowledge point: searching binary tree.

Definition: the key value of the left child node of a node is less than this node, and the key value of the right child node is greater than or equal to the parent node. As shown in the picture below, it is a search binary tree.

Some students may have found a rule, that is, the result of searching the middle order of the binary tree is an ascending order. So when judging whether a tree is searching for a binary tree, you can start from here.

Knowing the definition, we can implement the corresponding code according to the definition.

Node structure

Class TreeNode {int val; / / keyword TreeNode left; / left child node TreeNode right; / / right child node public TreeNode (int val) {this.val = val;}}

Search the whole frame structure of binary tree

Public class BST {private TreeNode root; / / Root node public void insert (int val) {/ / insert a new node} public void remove (int val) {/ / delete the corresponding node} public boolean contains (int val) {/ / query whether there is this value}}

Let's explain the specific implementation of each method one by one:

insert

Insert a new node, which is relatively simple. We get to compare the values of the current node and the passed-in parameters in turn. If the values of the parameters are smaller, we will do recursion on the left subtree and continue this operation.

/ / Recursive solution public void insert (int val) {root = process (val, root);} private TreeNode process (int val, TreeNode node) {if (node = = null) {/ / if the current node is null, create the node and return return new TreeNode (val);} if (val)

< node.val) { //小于当前节点 node.left = process(val, node.left); } else { node.right = process(val, node.right); //大于等于当前节点 } return node;}//非递归解法public void insert(int val) { TreeNode node = new TreeNode(val); //先创建好节点 TreeNode parent = null; //父节点，用于连接新的节点 TreeNode cur = root; //当前移动的节点 if (root == null) { root = node; //还没有根结点的情况 } else { while (true) { parent = cur; if (val < cur.val) { //小于当前节点的情况 cur = cur.left; if (cur == null) { //如果为null了，说明走到了最后的节点 parent.left = node; return; } } else { //大于当前节点的情况 cur = cur.right; if (cur == null) { parent.right = node; //如果为null，就走到最后节点了 return; } } } }} 递归与非递归的解法，差异只是在于空间复杂度。当整棵树很大时，递归去调用，就会耗费大量的栈空间。而非递归的解法，只是耗费了几个引用的空间。 删除 删除是一个比较难的点，删除之后，还需要保持搜索二叉树的结构。所以我们需要分为三种情况： 被删除节点是叶节点。 被删除节点只有一个孩子节点。 被删除节点有两个孩子节点。 我们需要循环遍历这颗树，找到需要被删除的节点，并且在遍历的过程中，还需要记录被删除节点的父节点是谁，以及被删除节点是父节点的左孩子还是右孩子。所以循环时，有三个变量，分别是parent、cur和isLeftChild。 在找到需要被删除的节点后。再对这个节点进行判断，看这个节点是叶节点？还是只有一个孩子节点？又或者是有两个孩子节点的情况。 如果是叶节点，parent的left（或者是right）置为null 如果只有一个节点，我们就需要绕过cur节点，直接连接cur的left或者right 如果是有两个节点，我们就需要找到cur的后继节点。也就是cur的右子树中，最小的节点。 其次我们还需要判断被删除的节点，是不是root根结点？如果是，就需要更换根结点。 非递归版本大致框架： //非递归版本public boolean remove(int val) { //删除对应的节点 if (root == null) { throw new RuntimeException("root is null."); } TreeNode parent = root; TreeNode cur = root; boolean isLeftChild = true; while (cur != null && cur.val != val) { //循环查找需要被删除的节点 parent = cur; if (val < cur.val) { cur = cur.left; isLeftChild = true; } else { cur = cur.right; isLeftChild = false; } } if (cur == null) { //没找到需要删除的节点 return false; } //找到了需要被删除的节点 if ( cur.left== null && cur.right == null) { //叶节点的情况 if (cur == root) { root = null; } else if (isLeftChild) { parent.left = null; } else { parent.right = null; } } else if (cur.right == null) { if (cur == root) { root = root.left; } else if (isLeftChild) { parent.left = cur.left; } else { parent.right = cur.left; } } else if (cur.left == null) { //只有一个孩子节点的情况 if (cur == root) { root = root.right; } else if (isLeftChild) { parent.left = cur.right; } else { parent.right = cur.right; } } else { //有两个孩子节点的情况 TreeNode minNode = findMinNode(cur.right); if (cur == root) { root = minNode; } else if (isLeftChild) { parent.left = minNode; } else { parent.right = minNode; } minNode.left = cur.left; //新节点minNode的左孩子指向被删除节点cur的左孩子 // C/C++语言，需要回收cur内存空间 } return true;}private TreeNode findMinNode(TreeNode head) { TreeNode pre = null; TreeNode cur = head; TreeNode next = head.left; while (next != null) { pre = cur; cur = next; next = next.left; //一直寻找该树的最左的节点 } if (pre != null) { pre.left = cur.right; //cur就是最左边的节点，pre的cur的父节点。父节点的left指向cur的right cur.right = head; //cur的right指向head这个根结点 } return cur; //返回最左边的节点}//递归版本public void remove2(int val) { if (root == null) { throw new RuntimeException("root is null."); } process2(val, root);}private TreeNode process2(int val, TreeNode node) { if (node == null) { return null; } if (val < node.val) { //小于 node.left = process2(val, node.left); } else if (val >

Node.val) {/ / greater than node.right = process2 (val, node.right);} else if (node.left! = null & & node.right! = null) {/ / the above if is not true, indicating that val is equal. Here is the case of two child nodes node.val = getMinNodeVal (node.right); / / overwrite the smallest node value in the right subtree node.right = process2 (node.val, node.right); / / re-delete the overridden values} else {/ / if there is only one child node or no node node = node.left! = null? Node.left: node.right;} return node;} private int getMinNodeVal (TreeNode node) {TreeNode pre = null; TreeNode cur = node; while (cur! = null) {pre = cur; cur = cur.left;} return pre.val;}

The recursive version of deletion simply assigns the value of the smallest node in the right subtree to cur, and then recursively calls to delete the node with the lowest value on the right subtree.

The last contains method is simple. It traverses the entire binary tree and returns true if it finds val, otherwise it returns false.

Public boolean contains (int val) {TreeNode cur = root; while (cur! = null) {if (cur.val = = val) {return true;} else if (val < cur.val) {cur = cur.left;} else {cur = cur.right;}} return false } this is the end of the introduction to the concept of binary tree in Java. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.