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!