Create binary tree in preorder traversal order
Enter a string in which '#' represents NULL, and the other characters represent the value of the node, and create a binary tree in the order of preorder traversal
For example, the string "ABC##DE#G##F###" means that the binary tree is
where # stands for empty
- Code
private Node createBiTree(Node node) { //Build a binary tree in preorder traversal order if(chars[index] == '#') { //If the current input character is '#', there is no node and the value is null node = null; } else { node = new Node(chars[index++]);//Create a node whose value is chars[index] node.leftChild = createBiTree(node.leftChild);//Create the left node recursively index++; //When the previous left subtree node is returned as null, index++ is performed to determine the next element to be read in, while assigning a value to the right subtree node node.rightChild = createBiTree(node.rightChild);//Create right node recursively } return node;//return root node }
- Code parsing
-
index subscript movement problem in character array
Each element in the character array represents the value of a binary tree node. Whenever a node is created, one element needs to be taken from the array as the value of the node, so after creating a node, the index needs to move one bit backward. , because when the left subtree of the node is empty, continue to create the right subtree node. At this time, it is also necessary to move the index one bit backward to get the value to the right subtree node.
-
traverse binary tree
1. Preorder traversal
- Preorder recursive traversal
Preorder traversal of binary tree based on recursive call
-
Code
private void preorderTraverse(Node node) { //preorder traversal if(node != null) { System.out.print(node.value + " "); preorderTraverse(node.leftChild); //Recursively traverse the left subtree preorderTraverse(node.rightChild);//Recursively traverse the right subtree } }
-
Code parsing
In preorder recursive traversal, the value of the node is output first and then traversed.
-
- Preorder non-recursive traversal
Non-recursive preorder traversal of binary tree based on stack operation
- Code
private void preorderTraverse2(Node root) { //Preorder non-recursive traversal SqStack<Node> Stack = new SqStack<Node>();//initialize a stack while(root != null || !Stack.isEmpty()) { //End the loop when the stack is empty and the node is empty if(root != null) { Stack.Push(root);//If the node is not empty, push the stack System.out.print(root.value + " ");//output in stack order root = root.leftChild; //Traverse the left subtree } else { Node tempNode = Stack.Pop(); //Node popped from the stack root = tempNode.rightChild; //Traverse the right subtree of the popped node } } System.out.println(); }
- Code parsing
- Initialize Stack
Non-recursive traversal is to use stack operation instead of recursive operation, and push non-empty nodes into the stack according to the principle of left subtree first. When the left subtree node is empty, take out the current node and then put the right subtree of the current node. Push the stack, at this time the stack order is the order of preorder traversal
- Initialize Stack
- Code
2. Inorder traversal
- Inorder recursive traversal
Inorder traversal of binary tree based on recursive call
- Code
private void inorderTraverse(Node node) { //Inorder recursive traversal if(node != null) { inorderTraverse(node.leftChild);//Recursively traverse the left subtree System.out.print(node.value + " "); inorderTraverse(node.rightChild);//Recursively traverse the right subtree } }
- Code
- Preorder non-recursive traversal
Non-recursive inorder traversal of binary tree based on stack operation
-
Code
private void inorderTraverse2(Node root) { //Inorder non-recursive traversal SqStack<Node> Stack = new SqStack<Node>();//initialize a stack while(root != null || !Stack.isEmpty()) { //End the loop when the stack is empty and the node is empty if(root != null) { Stack.Push(root); root = root.leftChild; //Traverse the left subtree } else { Node tempNode = Stack.Pop(); //Node popped from the stack System.out.print(tempNode.value + " ");//output in pop order root = tempNode.rightChild; //Traverse the right subtree of the popped node } } System.out.println(); }
-
Code parsing
In-order non-recursive traversal is similar to pre-order non-recursive traversal. You only need to change the position of the output. Pre-order traversal is the order in which nodes are pushed into the stack, so the output is output when the nodes are pushed into the stack, while in-order traversal is the output of nodes stack order, so output when the node is popped
-
3. Post-order traversal
- post-order recursive traversal
Post-order traversal of binary tree based on recursive call
- Code
private void postorderTraverse(Node node) { //post-order traversal if(node != null) { postorderTraverse(node.leftChild); postorderTraverse(node.rightChild); System.out.print(node.value + " "); } }
- Code
- postorder non-recursive traversal
Non-recursive post-order traversal of binary tree based on stack operation
-
Code
private void postorderTraverse2(Node root) { //postorder non-recursive traversal SqStack<Node> Stack = new SqStack<Node>(); //initialize a stack Node preNode = null; //The previous top element of the stack, used to avoid repeated nodes on the stack while(root != null || !Stack.isEmpty()) { //End the loop when the stack is empty and the node is empty if(root != null) { Stack.Push(root); root = root.leftChild; //Traverse the left subtree } else { Node currentNode = Stack.getTop(); //get the current stack top node root = currentNode.rightChild; //Set root to the right subtree of the popped top node //If both the left and right subtrees are null or the left subtree is null and the right subtree is the last node popped from the stack, the current node is popped off the stack if(root == null || (preNode == currentNode.rightChild) ) { System.out.print(Stack.Pop().value + " "); //Unstack the current node and print the value root = null; //Reset root to null to get the top element of the stack to avoid repeated pushes to the stack preNode = currentNode; //Update the pre node to the previous node on the top of the stack (that is, the node currently popped from the stack) } } } System.out.println(); }
-
Code parsing
The non-recursion of subsequent traversals is the most complicated
-
The setting and function of preNode
The purpose of the preNode setting is to prevent special nodes from being repeatedly pushed into the stack, such as the E node in this binary tree, because when the E node is pushed into the stack, the left node is empty, and the right node G of the E node is pushed into the stack. The nodes are all empty, so G pops off the stack. At this time, the top element of the stack reaches E again. If the G node is not processed, it will be pushed and popped infinitely, so set the preNode node and point it to the last pop. Node, when the G node is popped out of the stack, point preNode to G to indicate that G has almost entered the stack, and when the top element of the stack returns to the E node, pop the E node from the stack
-
-
depth of binary tree
A traversal-based method to find the depth of a binary tree
-
Code
private int depth(Node root) { //Recursively find the depth of a binary tree if(root == null) return 0; else { int m = depth(root.leftChild); //Count the nodes of the left subtree int n = depth(root.rightChild);//Count the nodes of the right subtree if(m > n) return (m + 1); else return (n + 1); } }
-
Code parsing
Recursively count the depth of the binary tree, count the depth of the left and right subtrees of each node and compare the maximum value, and then return the result layer by layer.
full code
import com.code.Stack.SqStack; /** * 1.Build binary tree in preorder traversal order * 2.Traverse a binary tree in preorder, inorder, and postorder * 3.Find the depth of a binary tree * @author admin * */ class BinaryTree { protected class Node{ private Node leftChild; private Node rightChild; private char value; public Node(char element) { //Node initialization // TODO Auto-generated constructor stub leftChild = null; rightChild = null; value = element; } } private char[] chars; //store the input string private int index = 0;//take the index of a single character private Node root;//root node public BinaryTree(String string) { // TODO Auto-generated constructor stub this.chars = string.toCharArray();//Convert the input string to a character array for analysis of individual characters root = createBiTree(root);//Create a binary tree } private Node createBiTree(Node node) { //Build a binary tree in preorder traversal order if(chars[index] == '#') { //If the current input character is '#', there is no node and the value is null node = null; } else { node = new Node(chars[index++]);//Create a node whose value is chars[index] node.leftChild = createBiTree(node.leftChild);//Create the left node recursively index++; //When the previous left subtree node is returned as null, index++ is required to determine the next element to be read in node.rightChild = createBiTree(node.rightChild);//Create right node recursively } return node;//return root node } private void preorderTraverse(Node node) { //preorder traversal if(node != null) { System.out.print(node.value + " "); preorderTraverse(node.leftChild); //Recursively traverse the left subtree preorderTraverse(node.rightChild);//Recursively traverse the right subtree } } private void preorderTraverse2(Node root) { //Preorder non-recursive traversal SqStack<Node> Stack = new SqStack<Node>();//initialize a stack while(root != null || !Stack.isEmpty()) { //End the loop when the stack is empty and the node is empty if(root != null) { Stack.Push(root);//If the node is not empty, push the stack System.out.print(root.value + " ");//output in stack order root = root.leftChild; //Traverse the left subtree } else { Node tempNode = Stack.Pop(); //Node popped from the stack root = tempNode.rightChild; //Traverse the right subtree of the popped node } } System.out.println(); } public void preorderTraverse() { //preorder traversal System.out.print("Recursive:"); preorderTraverse(root); System.out.print("Non-recursive:"); preorderTraverse2(root); } private void inorderTraverse(Node node) { //Inorder recursive traversal if(node != null) { inorderTraverse(node.leftChild);//Recursively traverse the left subtree System.out.print(node.value + " "); inorderTraverse(node.rightChild);//Recursively traverse the right subtree } } private void inorderTraverse2(Node root) { //Inorder non-recursive traversal SqStack<Node> Stack = new SqStack<Node>();//initialize a stack while(root != null || !Stack.isEmpty()) { //End the loop when the stack is empty and the node is empty if(root != null) { Stack.Push(root); root = root.leftChild; //Traverse the left subtree } else { Node tempNode = Stack.Pop(); //Node popped from the stack System.out.print(tempNode.value + " ");//output in pop order root = tempNode.rightChild; //Traverse the right subtree of the popped node } } System.out.println(); } public void inorderTraverse() { //Two preorder method traversal System.out.print("Recursive:"); inorderTraverse(root); System.out.print("Non-recursive:"); inorderTraverse2(root); } private void postorderTraverse(Node node) { //post-order traversal if(node != null) { postorderTraverse(node.leftChild); postorderTraverse(node.rightChild); System.out.print(node.value + " "); } } private void postorderTraverse2(Node root) { //postorder non-recursive traversal SqStack<Node> Stack = new SqStack<Node>(); //initialize a stack Node preNode = null; //The previous top element of the stack, used to avoid repeated nodes on the stack while(root != null || !Stack.isEmpty()) { //End the loop when the stack is empty and the node is empty if(root != null) { Stack.Push(root); root = root.leftChild; //Traverse the left subtree } else { Node currentNode = Stack.getTop(); //get the current stack top node root = currentNode.rightChild; //Set root to the right subtree of the popped top node //If both the left and right subtrees are null or the left subtree is null and the right subtree is the last node popped from the stack, the current node is popped off the stack if(root == null || (preNode == currentNode.rightChild) ) { System.out.print(Stack.Pop().value + " "); //Unstack the current node and print the value root = null; //Reset root to null to get the top element of the stack to avoid repeated pushes to the stack preNode = currentNode; //Update the pre node to the previous node on the top of the stack (that is, the node currently popped from the stack) } } } System.out.println(); } public void postorderTraverse() { //post-order traversal System.out.print("Non-recursive:"); postorderTraverse(root); System.out.print("Non-recursive:"); postorderTraverse2(root); } private int depth(Node root) { //Recursively find the depth of a binary tree if(root == null) return 0; else { int m = depth(root.leftChild); //Count the nodes of the left subtree int n = depth(root.rightChild);//Count the nodes of the right subtree if(m > n) return (m + 1); else return (n + 1); } } public int depth() { return depth(root); } }
Among them import com.code.Stack.SqStack; The code of the imported stack class is in https://blog.csdn.net/qq_40701941/article/details/107023992 middle
Summarize
- Recursion is a very magical thing. When you first come into contact with recursion, you still need to follow the recursive logic step by step, which is more conducive to understanding the code.
- Code needs to be scrutinized, and paper and pen are essential.
Everyone is welcome to help point out the flaws, Ruisbai!