Creation of binary tree and traversal in three ways (recursive and non-recursive)

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

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
          }
      }
      
  • 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 + " ");
          }
      }
      
  • 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!

Tags: Java data structure stack Binary tree

Posted by artweb on Wed, 01 Jun 2022 12:17:31 +0530