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

输入一段字符串其中以’#'代表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中

总结

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

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