# 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
*
*/
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!

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