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

How to find the next node of the binary tree, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Preface

Given that a binary tree contains a reference to the parent node and one of the nodes, how do you find the next node in the ordered traversal sequence in this node?

Analysis of problems

As mentioned earlier, our known conditions are as follows:

A binary tree containing references to the parent node

The node to find

The problem we need to solve:

Find the next node to find the ordered traversal sequence in the node

Next, we deduce the law of the next node by giving an example. let's draw a binary search tree, as follows:

8 / 6 13 / 3 7 9 15

For example, we look for the next node of 6, and according to the rules of traversal in the middle order, we know that its next node is 7.

The next node of 8 is 9.

The next node of 3 is 6

The next node of 7 is 8

Through the above examples, we can analyze the following information:

If the node to be found has a right subtree, then its next node is the leftmost child node in its right subtree.

The node you are looking for does not store the right subtree:

If the current node belongs to the left child of the parent node, its next node is the parent node itself.

If the current node belongs to the right child node of the parent node, you need to traverse up along the pointer of the parent node until you find a node that is the left child node of its parent node

The above law may be a little roundabout, we can put the law into the problem to verify a few more times, we can understand.

Realization idea

Save a reference to its parent node when a node is inserted into a binary tree

Call the search node method of the binary tree to find the node information you are looking for

Determine whether the found node has a right subtree.

If it exists, traverse its left subtree to the leaf node and return it.

If it does not exist, it traverses its parent node to the root node until it finds a node that is equal to the left child of its parent node and returns it.

Implementation code

Next, let's convert the above ideas into code. The binary tree related implementation used in this code, please move to my other article: TypeScript implementation of binary search tree.

Search for the node you want to find

We need to find the node information to find the node in the binary tree before we can continue with the next steps. The code for searching the node is as follows:

Import {Node} from ". / Node.ts"; export default class BinarySearchTree {protected root: Node | undefined; constructor (protected compareFn: ICompareFunction = defaultCompare) {this.root = undefined;} / / search for a specific value search (key: t): boolean | Node {return this.searchNode (this.root, key) } / / search node private searchNode (node: Node, key: t): boolean | Node {if (node = = null) {return false;} if (this.compareFn (key, node.key) = Compare.LESS_THAN) {/ / the key to be found is return this.searchNode (node.left, key) on the left side of the node } else if (this.compareFn (key, node.key) = Compare.BIGGER_THAN) {/ / the key to be found is return this.searchNode (node.right, key) on the right side of the node;} else {/ / the node has found return node;}

Save parent node reference

The binary tree here is slightly different from the binary tree we implemented. When inserting the node, you need to save the reference of the parent node. The implementation code is as follows:

Export default class BinarySearchTree {/ / insertion method insert (key: t): void {if (this.root = = null) {/ / if the root node does not exist, create a new node directly this.root = new Node (key) } else {/ / find a suitable location in the root node to insert the child node this.insertNode (this.root, key) }} / / Node inserts protected insertNode (node: Node, key: t): void {/ / if the key of the new node is less than the key of the current node, the key of the new node is greater than the key of the current node. Insert the new node into the right side of the current node if (this.compareFn (key, node.key) = Compare.LESS_THAN) {if (node.left = = null) {/ / the left subtree of the current node is directly inserted into the null node.left = new Node (key, node) } else {/ / recurses down from the current node (left subtree), finds the null location and inserts it into this.insertNode (node.left, key) }} else {if (node.right = = null) {/ / the right subtree of the current node is null directly inserted into node.right = new Node (key, node) } else {/ / recurses down from the current node (right subtree) to find the location of null and insert it into this.insertNode (node.right, key); auxiliary class of binary tree: each node of binary tree is used to store * / export class Node {public left: Node | undefined Public right: Node | undefined; public parent: Node | undefined; constructor (public key: K, parent?: Node) {this.left = undefined; this.right = undefined; console.log (key, "parent", parent?.key); this.parent = parent;} toString (): string {return `${this.key}`;}}

Let's test the above code to verify whether the parent node reference is successful:

Const tree = new BinarySearchTree (); tree.insert (8); tree.insert (6); tree.insert (3); tree.insert (7); tree.insert (13); tree.insert (9); tree.insert (15)

It took a long time to save the parent node reference but didn't implement it, and finally turned to my friend _ Dreams?.

Find the next node

Next, we can implement the algorithm according to the law of the node. The implementation code is as follows:

Export class TreeOperate {/ * find the next node of the binary tree * rule: * 1. Enter a binary tree that contains a reference to the parent node and one of the nodes * 2. Find out the next node of the ordered ergodic sequence in this node * * for example: * 8 * /\ * 6 13 * /\ * 3 7 9 15 * 6 the next node is 7Part 8 and the next node is 9 * * through analysis We can get the following information: * 1. If a node has a right subtree, then its next node is the leftmost child node * 2 in its right subtree. If a node does not have a right subtree: * (1). If the current node belongs to the left child of the parent, then its next node is the parent itself * (2). The current node belongs to the right child node of the parent node and traverses up along the pointer of the parent node until it finds a node * * / findBinaryTreeNextNode (tree: BinarySearchTree, node: number): null | Node {/ / search node const result: Node | boolean = tree.search (node); if (result = = null) throw "Node does not exist" Let currentNode = result as Node; / / there exists if (currentNode.right) {currentNode = currentNode.right; / / the leftmost child node while (currentNode.left) {currentNode = currentNode.left;} return currentNode of the right subtree. } / / there is no while (currentNode.parent) {/ / the left child node of which the current node is equal to its parent node exists in the right subtree, then if (currentNode = = currentNode.parent.left) {return currentNode.parent } / / condition is not valid, continue to get its parent node currentNode = currentNode.parent;} return null;}}

Let's test the above code with an example:

/ / build a binary search tree const tree = new BinarySearchTree (); tree.insert (8); tree.insert (6); tree.insert (3); tree.insert (7); tree.insert (13); tree.insert (9); tree.insert (15); / / find the next node const nextNode = treeOperate.findBinaryTreeNextNode (tree, 7); console.log ("next node of 7", nextNode.toString ())

Code address

The complete code in this paper is as follows:

TreeOperate.ts

BinarySearchTree.ts

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.