博客

二叉树的创建以及三种方式的遍历（递归与非递归）

  • Post author:
  • Post category:其他




先序遍历的顺序创建二叉树

输入一段字符串其中以’#’代表NULL，其余字符表示结点的值，按照先序遍历的顺序创建二叉树

例如字符串


“ABC##DE#G##F###”


表示该二叉树为

二叉树

其中

#

代表空

  • 代码实现 
private Node createBiTree(Node node) {  //先序遍历顺序建立二叉树
    if(chars[index] == '#') { //如果当前输入的字符为‘#’标识没有结点值为null
        node = null;
    }
    else {
        node = new Node(chars[index++]);//创建值为chars[index]的结点
        node.leftChild = createBiTree(node.leftChild);//递归创建左结点
        index++; //当上一个左子树结点为null返回时，要进行index++来确定下一位要读进来的元素，一边对右子树结点赋值
        node.rightChild = createBiTree(node.rightChild);//递归创建右节点
    }
    return node;//返回根结点
}
  • 代码解析

    • 字符数组中index下标移动问题

      字符数组中的每一位元素代表二叉树结点的值，每当创建一个结点时需要去数组中取一位元素作结点的值，所以在创建一个结点后index需要往后移动一位，因为当结点的左子树为空后，继续创建右子树结点，此时也需要将index往后移一位来取值给右子树结点。



遍历二叉树



1. 先序遍历

  • 先序递归遍历

    基于递归调用的方式先序遍历二叉树

    • 代码实现 

      private void preorderTraverse(Node node) { //先序遍历
    if(node != null) {
        System.out.print(node.value + " ");
        preorderTraverse(node.leftChild); //递归遍历左子树
        preorderTraverse(node.rightChild);//递归遍历右子树
    }
}

    • 代码解析

      在先序递归遍历中，先输出结点的值再进行遍历。

  • 先序非递归遍历

    基于栈操作的非递归方式先序遍历二叉树

    • 代码实现

      private void preorderTraverse2(Node root) { //先序非递归遍历

    SqStack<Node> Stack = new SqStack<Node>();//初始化一个栈

    while(root != null || !Stack.isEmpty()) { //当栈为空并且结点为空时结束循环
        if(root != null) {
            Stack.Push(root);//如果结点不为空，进栈
            System.out.print(root.value + " ");//按进栈顺序输出
            root = root.leftChild; //遍历左子树
        }
        else {
            Node tempNode = Stack.Pop();  //出栈的结点
            root = tempNode.rightChild; //遍历出栈节点的右子树结点
        }
    }
    System.out.println();
}
    • 代码解析

      • 初始化Stack

        非递归遍历是采用栈操作来代替递归操作，将非空结点按照左子树优先的原则进栈，当左子树结点为空时，取出当前结点再将当前结点的右子树进栈，此时进栈顺序为先序遍历的顺序



2. 中序遍历

  • 中序递归遍历

    基于递归调用的方式中序遍历二叉树

    • 代码实现

      private void inorderTraverse(Node node) { //中序递归遍历
    if(node != null) {
        inorderTraverse(node.leftChild);//递归遍历左子树
        System.out.print(node.value + " ");
        inorderTraverse(node.rightChild);//递归遍历右子树
    }
}
  • 先序非递归遍历

    基于栈操作的非递归方式中序遍历二叉树

    • 代码实现 

      private void inorderTraverse2(Node root) { //中序非递归遍历
    SqStack<Node> Stack = new SqStack<Node>();//初始化一个栈
    while(root != null || !Stack.isEmpty()) { //当栈为空并且结点为空时结束循环
        if(root != null) {
            Stack.Push(root);
            root = root.leftChild;  //遍历左子树
        }
        else {
            Node tempNode = Stack.Pop();  //出栈的结点
            System.out.print(tempNode.value + " ");//按出栈顺序输出
            root = tempNode.rightChild; //遍历出栈节点的右子树
        }
    }
    System.out.println();
}

    • 代码解析

      中序非递归遍历和先序非递归遍历类似，只需要改变输出的位置，先序遍历是结点进栈的顺序，所以在结点进栈时输出，而中序遍历是按结点的出栈顺序，因此在结点出栈时输出



3. 后序遍历

  • 后序递归遍历

    基于递归调用的方式的后序遍历二叉树

    • 代码实现

      private void postorderTraverse(Node node) { //后序遍历
    if(node != null) {
        postorderTraverse(node.leftChild);
        postorderTraverse(node.rightChild);
        System.out.print(node.value + " ");
    }
}
  • 后序非递归遍历

    基于栈操作的非递归方式的后序遍历二叉树

    • 代码实现 

      private void postorderTraverse2(Node root) { //后序非递归遍历
    SqStack<Node> Stack = new SqStack<Node>(); //初始化一个栈
    Node preNode = null; //前一个栈顶元素，用来避免结点重复进栈
    while(root != null || !Stack.isEmpty()) { //当栈为空并且结点为空时结束循环
        if(root != null) {
            Stack.Push(root);
            root = root.leftChild; //遍历左子树
        }
        else {
            Node currentNode = Stack.getTop();  //得到当前栈顶结点
            root = currentNode.rightChild; //将root设置为出栈顶结点的右子树
            //如果左右子树都为null或者左子树为null右子树为上一个出栈的结点时，当前结点退栈
            if(root == null || (preNode == currentNode.rightChild) ) { 
                System.out.print(Stack.Pop().value + " "); //当前结点退栈并打印值
                root = null; //将root重置为null，以获取栈顶元素，避免重复入栈
                preNode = currentNode; //将pre结点更新为前一次的栈顶的结点（即当前出栈的结点）
            }
        }
    }
    System.out.println();
}

    • 代码解析

      后续遍历的非递归是最复杂的

      • preNode的设置与作用

        preNode设置的目的是为了防止特殊结点重复入栈，例如此二叉树中的E结点，因为当E结点进栈后左结点为空就将E结点的右节点G入栈,G左右结点都为空，所以G退栈，此时栈顶元素又到了E，如果不加处理G结点会无限次入栈再出栈，所以设置preNode结点并将其指向上一次的出栈结点，当G结点出栈后将preNode指向G表示G已近入过栈了再当栈顶元素回到E结点时，将E结点出栈



二叉树的深度

基于遍历的方法求二叉树的深度

  • 代码实现 

    private int depth(Node root) { //递归求二叉树的深度
	if(root == null)
		return 0;
	else {
		int m = depth(root.leftChild); //统计左边子树结点
		int n = depth(root.rightChild);//统计右边子树结点
		if(m > n)
			return (m + 1);
		else
			return (n + 1);
	}
}

  • 代码解析

    递归统计二叉树的深度，统计每一个结点的左右子树深度并比较最大值，再一层一层往上返回结果。



完整代码

import com.code.Stack.SqStack;
/**
 * 1.先序遍历的顺序建立二叉树
 * 2.分别用先序 中序 后序 遍历二叉树
 * 3.求二叉树的深度
 * @author admin
 *
 */
class BinaryTree {

	
	protected class Node{
		
		
		private Node leftChild;
		private Node rightChild;
		private char value;
		
		public Node(char element) { //结点初始化
			// TODO Auto-generated constructor stub
			leftChild = null;
			rightChild = null;
			value = element;
		}
	}
	
	private char[] chars; //存储输入的字符串
	private int index = 0;//取单个字符的索引
	private Node root;//根结点
	
	public BinaryTree(String string) {
		// TODO Auto-generated constructor stub
		this.chars = string.toCharArray();//将输入字符串转换为字符数组以便分析单个字符
		root = createBiTree(root);//创建二叉树
	}
	
	private Node createBiTree(Node node) {  //先序遍历顺序建立二叉树
		if(chars[index] == '#') { //如果当前输入的字符为‘#’标识没有结点值为null
			node = null;
		}
		else {
			node = new Node(chars[index++]);//创建值为chars[index]的结点
			node.leftChild = createBiTree(node.leftChild);//递归创建左结点
			index++; //当上一个左子树结点为null返回时，要进行index++来确定下一位要读进来的元素
			node.rightChild = createBiTree(node.rightChild);//递归创建右节点
		}
		return node;//返回根结点
	}
	
	private void preorderTraverse(Node node) { //先序遍历
		if(node != null) {
			System.out.print(node.value + " ");
			preorderTraverse(node.leftChild); //递归遍历左子树
			preorderTraverse(node.rightChild);//递归遍历右子树
		}
	}
	private void preorderTraverse2(Node root) { //先序非递归遍历
		SqStack<Node> Stack = new SqStack<Node>();//初始化一个栈
		while(root != null || !Stack.isEmpty()) { //当栈为空并且结点为空时结束循环
			if(root != null) {
				Stack.Push(root);//如果结点不为空，进栈
				System.out.print(root.value + " ");//按进栈顺序输出
				root = root.leftChild; //遍历左子树
			}
			else {
				Node tempNode = Stack.Pop();  //出栈的结点
				root = tempNode.rightChild; //遍历出栈节点的右子树
			}
		}
		System.out.println();
	}
	
	public void preorderTraverse() { //先序遍历
		System.out.print("递归：");
		preorderTraverse(root);
		System.out.print("非递归：");
		preorderTraverse2(root);
	}
	
	private void inorderTraverse(Node node) { //中序递归遍历
		if(node != null) {
			inorderTraverse(node.leftChild);//递归遍历左子树
			System.out.print(node.value + " ");
			inorderTraverse(node.rightChild);//递归遍历右子树
		}
	}
	
	private void inorderTraverse2(Node root) { //中序非递归遍历
		SqStack<Node> Stack = new SqStack<Node>();//初始化一个栈
		while(root != null || !Stack.isEmpty()) { //当栈为空并且结点为空时结束循环
			if(root != null) {
				Stack.Push(root);
				root = root.leftChild;  //遍历左子树
			}
			else {
				Node tempNode = Stack.Pop();  //出栈的结点
				System.out.print(tempNode.value + " ");//按出栈顺序输出
				root = tempNode.rightChild; //遍历出栈节点的右子树
			}
		}
		System.out.println();
	}
	
	public void inorderTraverse() { //两种先序方法遍历
		System.out.print("递归：");
		inorderTraverse(root);
		System.out.print("非递归：");
		inorderTraverse2(root);
	}
	
	private void postorderTraverse(Node node) { //后序遍历
		if(node != null) {
			postorderTraverse(node.leftChild);
			postorderTraverse(node.rightChild);
			System.out.print(node.value + " ");
		}
	}
	
	private void postorderTraverse2(Node root) { //后序非递归遍历
		SqStack<Node> Stack = new SqStack<Node>(); //初始化一个栈
		Node preNode = null; //前一个栈顶元素，用来避免结点重复进栈
		while(root != null || !Stack.isEmpty()) { //当栈为空并且结点为空时结束循环
			if(root != null) {
				Stack.Push(root);
				root = root.leftChild; //遍历左子树
			}
			else {
				Node currentNode = Stack.getTop();  //得到当前栈顶结点
				root = currentNode.rightChild; //将root设置为出栈顶结点的右子树
				//如果左右子树都为null或者左子树为null右子树为上一个出栈的结点时，当前结点退栈
				if(root == null || (preNode == currentNode.rightChild) ) { 
					System.out.print(Stack.Pop().value + " "); //当前结点退栈并打印值
					root = null; //将root重置为null，以获取栈顶元素，避免重复入栈
					preNode = currentNode; //将pre结点更新为前一次的栈顶的结点（即当前出栈的结点）
				}
			}
		}
		System.out.println();
	}
	public void postorderTraverse() { //后序遍历
		System.out.print("非递归：");
		postorderTraverse(root);
		System.out.print("非递归：");
		postorderTraverse2(root);
	}
	
	private int depth(Node root) { //递归求二叉树的深度
		if(root == null)
			return 0;
		else {
		
			int m = depth(root.leftChild); //统计左边子树结点
			int n = depth(root.rightChild);//统计右边子树结点
			if(m > n)
				return (m + 1);
			else
				return (n + 1);
		}
	}
	public int depth() {
		return depth(root);
	}
}

其中

import com.code.Stack.SqStack;

导入的栈类的代码在

https://blog.csdn.net/qq_40701941/article/details/107023992

中



总结

  • 递归是非常神奇的东西，在刚开始接触递归时还是需要一步一步的跟进递归逻辑里，这样更有利于对代码的理解。
  • 代码是需要反复推敲的，纸和笔是必不可少的。

欢迎大家帮忙指出瑕疵，瑞思拜！


版权声明：本文为qq_40701941原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。