美文网首页
02. 树的遍历算法（递归和非递归实现）

02. 树的遍历算法（递归和非递归实现）

作者: 一直流浪 | 来源:发表于2022-09-07 17:36 被阅读0次

02. 树的遍历算法（递归和非递归实现）

树从存储方式上可分为顺序树和链式树

这节我们主要说的是链式树。

1. 定义结点

public class Node {
    public String name;          //结点的数据域，拿String name代替
    public Node lchild;          //存放左孩子
    public Node rchild;          //存放右孩子
    public boolean status;       //非递归后序遍历会用到
    public Node() {
        // TODO Auto-generated constructor stub
        this.name = "";
        this.lchild = null;
        this.rchild = null;
        this.status = false;
    }
    
    public Node(String string) {
        // TODO Auto-generated constructor stub
        this.name = string;
        this.lchild = null;
        this.rchild = null;
        this.status = false;
    }   
}

2. 树的创建

定义一个Tree类，里面主要实现树的创建，和一些遍历操作，先部分展示代码并讲解，在最后会给出全部源码。

我们为了养成良好的习惯，建议把每个东西归结成一个类，比如树，栈，队列，都分开定义，到用的时候，直接new就行了。

先定义数据结构

1.树的结构：

public class Tree {

    // 声明输入流
    Scanner scanner;

    // 声明一个队列(层序遍历会用到)
    Seqqueue queue;

    // 声明一个栈(非递归的先序，中序，后序会用到)
    Seqstack stack;

    public Tree() {
        // TODO Auto-generated constructor stub
        // 初始化输入流
        this.scanner = new Scanner(System.in);

        // 初始化队列
        this.queue = new Seqqueue();
        this.queue.initQueue(10);

        // 初始化栈
        this.stack = new Seqstack();
        this.stack.InitStack(20);

    }

2.栈的结构：（树的非递归遍历会用到）

public class Seqstack {
    // 节点数组(模拟顺序栈)
    public Node[] nodes;

    // 栈顶下标
    public int top;

    public Seqstack() {
        // TODO Auto-generated constructor stub
        this.top = -1;

    }

    // 初始化栈
    public void InitStack(int size) {
        this.nodes = new Node[size];
        this.top = -1;

    }

    // 判断栈空
    public boolean IsEmpty() {
        if (this.top == -1) {
            return true;
        }

        return false;
    }

    // 判断栈满
    public boolean IsFull() {
        if (this.top == this.nodes.length - 1) {
            return true;
        }

        return false;
    }

    // 入栈
    public void push(Node node) {
        if (IsFull()) {
            System.out.println("栈已经满了，入栈失败");
            return;
        }
        this.top++;
        this.nodes[this.top] = node;
    }

    // 出栈
    public Node pop() {
        if (IsEmpty()) {
            System.out.println("栈已经空了，出栈失败");
            return null;
        }
        Node node = this.nodes[this.top];
        this.top--;
        return node;

    }

    // 清空栈
    public void ClearStack() {
        // 如果不为空，就一直出栈
        while (!IsEmpty()) {
            Node node = pop();
        }

    }

    // 拿到栈顶元素
    public Node getTop() {
        if (IsEmpty()) {
            System.out.println("栈中没有元素");
            return null;
        }
        return this.nodes[this.top];
    }
}

3.循环队列的结构：（树的层序遍历会用到）

public class Seqqueue {
    public Node[] queue;
    public int QUEUE_SIZE;
    public int front;
    public int rear;
    
    //初始化队列
        public void initQueue(int size) {
            this.QUEUE_SIZE = size;
            this.queue = new Node[size];
            this.front = 0;
            this.rear = 0;
        
        }
        
        //判断队列是否为空
        public boolean isEmpty() {
            if(this.front  == this.rear ) {
                return true;
            }
            else {
                return false;
            }
        }
        
        //判断队列是否为满
        public boolean isFull() {
            if((this.front % this.QUEUE_SIZE) == ((this.rear+1) % this.QUEUE_SIZE)) {
                return true;
            }
            else {
                return false;
            }
        }
        
        //入队
        public void enterQueue(Node node) {
            if(isFull()) {
                System.out.println("队列已经满了，入队失败");
                return;     
            }
            this.queue[this.rear] = node;
            this.rear ++;
            this.rear = this.rear % this.QUEUE_SIZE;
            
        }
        //出队
        public Node deleteQueue() {
            if(isEmpty()){
                System.out.println("队列为空，出队失败");
                return null;
            }
            this.front = this.front % this.QUEUE_SIZE;
            Node node = this.queue[this.front];
            
            this.front++;
            return node;
        }
}
  1. 树的递归创建方式：（使用先序创建）
    // 递归创建树（树的头节点）
    Node createBiTree(Node tree) {
        String string = scanner.nextLine();
        if (string.equals(".")) {
            return null;
        }
        tree = new Node();

        tree.name = string;
        tree.lchild = createBiTree(tree.lchild);
        tree.rchild = createBiTree(tree.rchild);
        return tree;
    }

3. 树的递归遍历

我们利用三种遍历的特点，根据他们的打印顺序总结出来:

先序：根左右

中序：左跟右

后序：左右跟

3.1 树的递归先序遍历

    // 先序遍历(递归)
    void PreOrder(Node tree) {
        if (tree != null) {
            System.out.println(tree.name);
            PreOrder(tree.lchild);
            PreOrder(tree.rchild);
        }

    }

3.2 树的递归中序遍历

    // 中序遍历(递归)
    void Inthread(Node tree) {
        if (tree != null) {
            Inthread(tree.lchild);
            System.out.println(tree.name);
            Inthread(tree.rchild);
        }
    }

3.3 树的递归后序遍历

    // 后序遍历(递归)
    void PostOrder(Node tree) {
        if (tree != null) {
            PostOrder(tree.lchild);
            PostOrder(tree.rchild);
            System.out.println(tree.name);
        }
    }

递归的遍历特别简单，只需要知道递归的原理就OK了，不做详解。

4. 树的非递归遍历

树的非递归遍历，还会用到栈，利用栈的先进后出的特点，实现树的遍历。

4.1 树的非递归先序遍历

这块我会给出两种方法，原理基本相同。

（1）根据先序打印特点：根左右。

我们用到压栈和出栈来模拟这个过程：

  1. 由于栈是先进后出的，所以我们先访问根节点，压栈。
  2. 然后判断栈不为空，然后出栈，打印。
  3. 对出栈的结点进行判断，他有没有右孩子，如果有，把右孩子压栈。
  4. 再判断有没有左孩子，如果有，把左孩子压栈。
  5. 完成后，再跳回第2步，一直循环
    // 先序遍历(非递归)
    void nonPreOrder(Node tree) {
        Node temp = null;
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        stack.push(tree);
        while (!stack.IsEmpty()) {
            temp = stack.pop();
            System.out.println(temp.name);
            if (temp.rchild != null) {
                stack.push(temp.rchild);
            }
            if (temp.lchild != null) {
                stack.push(temp.lchild);
            }
        }
    }

（2）第二种只是把压栈的顺序，进行了一点修正，其他的都差不多，但是，为了方便记忆非递归的先序，中序，后序，建议学习第二种的算法。

    // 先序遍历(非递归)
    void nonPreOrder2(Node tree) {

        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp = null;
        temp = tree;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                System.out.println(temp.name);
                stack.push(temp);
                temp = temp.lchild;
            }
            temp = stack.pop();
            temp = temp.rchild;
        }
    }

4.2 树的非递归中序遍历

根据中序打印特点：左跟右。

我们用到压栈和出栈来模拟这个过程：

  1. 由于栈是先进后出的，所以我们先访问根节点，用temp结点记录。
  2. 然后判断栈不为空或者temp不为空，进入循环。
  3. 先将temp的所有左子树全部压栈。
  4. 然后出栈栈顶结点，打印
  5. 然后再判断出栈的这个结点有没有右孩子，如果有，将右孩子入栈
  6. 再将右孩子结点 的所有左孩子全部入栈，即从第3步开始循环。
    // 中序遍历(非递归)
    void nonInthread(Node tree) {

        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp = null;
        temp = tree;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.lchild;
            }

            temp = stack.pop();
            System.out.println(temp.name);
            temp = temp.rchild;

        }
    }

中序的非递归遍历，和上述的先序的第二种非递归遍历比较，会发现，只改变了打印的位置，其他的都没有变化，所以建议记住，先序的第二种算法。

4.2 树的非递归后序遍历

后序我会给出，自己总结的三种方法，各有特点，其中第一种可以和前两对应起来，改动较小，对应编程能力差的同学，可以着重学习，后两种方法也很nice，想要多学点的同学，也可以学习。

（1）第一种：根据后序打印特点：左右跟。

我们根据先序的过程，先访问根节点，再访问左孩子，最后访问右孩子，根据具体的顺序，我们可以发现其实后序只需要，把先序打印的过程，换成一个如另一个栈的过程，所以我们需要两个栈，再把先将左孩子压栈，后将右孩子压栈，变成先将右孩子压栈，再将左孩子压栈，最后我们的第二个栈中就得到了后序的倒序，我们再将第二个栈出栈，打印就行。

    // 后序遍历(非递归3)
    void nonPostOrder3(Node tree) {
        Seqstack stack2 = new Seqstack();
        stack2.InitStack(20);
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp = null;
        temp = tree;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                stack2.push(temp);       //这行改变
                stack.push(temp);
                temp = temp.rchild;      //这行改变
            }
            temp = stack.pop();
            temp = temp.lchild;
        }
        while (!stack2.IsEmpty()) {              //把第二个栈全部出栈打印
            temp = stack2.pop();              
            System.out.println(temp.name);

        }
    }

后两种方法，都需要明白一个特点：

我们可以观察前序、中序、后序的过程，根据他们是第几次访问根节点然后再打印的特点，我们可以发现：

  1. 先序都是先访问根节点，然后打印，然后再访问他的左孩子，把他的左孩子又看出根节点，然后打印，又去访问他的左孩子，如果左孩子不存在，去访问他的右孩子，把他的右孩子又看成根节点，一直重复上面的步骤。（这块的根节点指的是每一个结点都看成根节点，不是特指树的根节点）。
  2. 中序都是先访问根节点，然后访问所有的左孩子，左孩子全部访问结束，再回来访问根节点，打印根节点，再去访问右孩子，又去访问右孩子的所有左孩子，一直重复上面步骤。
  3. 后序都是先访问根节点，再访问他的全部左孩子，左孩子全部访问结束，再回来访问他的根节点，又访问他的全部右孩子，右孩子全部访问结束，再反过来打印根节点。（这块的根节点指的是每一个结点都看成根节点，不是特指树的根节点）。

总结一个特点：

  1. 先序：第一次访问一个结点时打印
  2. 中序：第二次访问一个结点时打印
  3. 后序：第三次访问一个结点时打印

后序什么时候打印，可以根据他是不是访问完右孩子过来的，如果是访问完右孩子过来的，就让他打印，否则去遍历他的右孩子。

下面的两种方法都是根据，这个特点完成的，这是有点稍微的区别。

（2）第二种：多创建一个结点，用来记录出栈的元素，进行判断

    // 后序遍历(非递归1)
    void nonPostOrder(Node tree) {
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp, r = null;   //r用来记录
        temp = tree;
        while (temp != null || !stack.IsEmpty()) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.lchild;
            } else {
                temp = stack.getTop();
                if (temp.rchild != null && temp.rchild != r) {
                    temp = temp.rchild;
                } else {
                    temp = stack.pop();
                    System.out.println(temp.name);
                    r = temp;
                    temp = null;
                }
            }

        }

    }

（3）第三种：利用在结点中，多一个属性，用来记录是第几次访问

    // 后序遍历(非递归2)
    void nonPostOrder2(Node tree) {
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp;
        temp = tree;
        stack.push(temp);
        temp = temp.lchild;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.lchild;
            }

            temp = stack.pop();
            if (temp.rchild != null && temp.status == false) {
                stack.push(temp);
                temp.status = true;
                temp = temp.rchild;
            } else {
                System.out.println(temp.name);
                temp = null;
            }

        }
    }

5. 树的层序遍历

用到了队列

    // 层序遍历
    void cengxu(Node tree) {
        Node temp = null;
        queue.front = queue.rear = 0;
        if (tree == null) {
            System.out.println("该树为空");
            return;
        }
        queue.enterQueue(tree);
        while (queue.front != queue.rear) {
            temp = queue.deleteQueue();
            System.out.println(temp.name);
            if (temp.lchild != null) {
                queue.enterQueue(temp.lchild);
            }
            if (temp.rchild != null) {
                queue.enterQueue(temp.rchild);
            }

        }
    }

6. 计算树的深度

    // 递归计算树的深度
    int high(Node t) {
        int h = 0, left = 0, right = 0;
        if (t == null) {
            return 0;
        }
        left = high(t.lchild);
        right = high(t.rchild);
        h = (left > right ? left : right) + 1;
        return h;
    }

7. 反转二叉树

7.1 递归方法

    // 反转二叉树(递归)
    void recReversal(Node tree) {
        if (tree == null) {
            return;
        }
        if (tree.lchild == null && tree.rchild == null) {
            return;
        }
        Node temp = tree.lchild;
        tree.lchild = tree.rchild;
        tree.rchild = temp;
        recReversal(tree.lchild);
        recReversal(tree.rchild);
    }

7.2 非递归算法

用到栈

    // 反转二叉树(非递归)
    void nonRecReversal(Node tree) {
        Node t = null;
        if (tree == null) {
            System.out.println("树为空");
            return;
        }
        stack.push(tree);
        while (!stack.IsEmpty()) {
            Node temp = stack.pop();
            t = temp.lchild;
            temp.lchild = temp.rchild;
            temp.rchild = t;

            if (temp.rchild != null) {
                stack.push(temp.rchild);
            }
            if (temp.lchild != null) {
                stack.push(temp.lchild);
            }
        }
    }

8. 统计结点数（递归）

    // 统计结点数(递归)
    int getNodeNum(Node tree) {
        int nodes = 0;
        if (tree == null) {         
            return 0;
        }
        else {
            nodes = 1 + getNodeNum(tree.lchild) + getNodeNum(tree.rchild);
        }
        
        return nodes;
    }

9. 统计叶子结点数（递归）

    //统计叶子结点数（递归）
    int getLeafNum(Node tree) {
        if(tree == null) {
            return 0;
        }
        if(tree.lchild == null &&tree.rchild == null) {
            return 1;
        }
        return getLeafNum(tree.lchild) + getLeafNum(tree.rchild);           
    }

10. 判断一个结点是否是一个子树上的结点（递归）

    //找一个结点是否是一个子树的结点
    boolean Ishave(Node tree,Node node) {
        if(node == null || tree == null) {
            return false;
        }
        if(tree.name.equals(node.name)) {
            return true;
        }
        else {
            return Ishave(tree.lchild, node) | Ishave(tree.rchild, node);
        }
        
    }

11. 代码的综合

对上面讲述所有代码算法的综合

树的创建和操作：

//class Tree

import java.util.Scanner;

public class Tree {

    // 声明输入流
    Scanner scanner;

    // 声明一个队列(层序遍历会用到)
    Seqqueue queue;

    // 声明一个栈(非递归的先序，中序，后序会用到)
    Seqstack stack;

    public Tree() {
        // TODO Auto-generated constructor stub
        // 初始化输入流
        this.scanner = new Scanner(System.in);

        // 初始化队列
        this.queue = new Seqqueue();
        this.queue.initQueue(10);

        // 初始化栈
        this.stack = new Seqstack();
        this.stack.InitStack(20);

    }

    // 递归创建树（树的头节点）
    Node createBiTree(Node tree) {
        String string = scanner.nextLine();
        if (string.equals(".")) {
            return null;
        }
        tree = new Node();

        tree.name = string;
        tree.lchild = createBiTree(tree.lchild);
        tree.rchild = createBiTree(tree.rchild);
        return tree;
    }

    // 先序遍历(递归)
    void PreOrder(Node tree) {
        if (tree != null) {
            System.out.println(tree.name);
            PreOrder(tree.lchild);
            PreOrder(tree.rchild);
        }

    }

    // 先序遍历(非递归)
    void nonPreOrder(Node tree) {
        Node temp = null;
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        stack.push(tree);
        while (!stack.IsEmpty()) {
            temp = stack.pop();
            System.out.println(temp.name);
            if (temp.rchild != null) {
                stack.push(temp.rchild);
            }
            if (temp.lchild != null) {
                stack.push(temp.lchild);
            }
        }
    }

    // 先序遍历(非递归)
    void nonPreOrder2(Node tree) {

        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp = null;
        temp = tree;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                System.out.println(temp.name);
                stack.push(temp);
                temp = temp.lchild;
            }
            temp = stack.pop();
            temp = temp.rchild;
        }
    }

    // 中序遍历(递归)
    void Inthread(Node tree) {
        if (tree != null) {
            Inthread(tree.lchild);
            System.out.println(tree.name);
            Inthread(tree.rchild);
        }
    }

    // 中序遍历(非递归)
    void nonInthread(Node tree) {

        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp = null;
        temp = tree;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.lchild;
            }

            temp = stack.pop();
            System.out.println(temp.name);
            temp = temp.rchild;

        }
    }

    // 后序遍历(递归)
    void PostOrder(Node tree) {
        if (tree != null) {
            PostOrder(tree.lchild);
            PostOrder(tree.rchild);
            System.out.println(tree.name);
        }
    }

    // 后序遍历(非递归1)
    void nonPostOrder(Node tree) {
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp, r = null;
        temp = tree;
        while (temp != null || !stack.IsEmpty()) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.lchild;
            } else {
                temp = stack.getTop();
                if (temp.rchild != null && temp.rchild != r) {
                    temp = temp.rchild;
                } else {
                    temp = stack.pop();
                    System.out.println(temp.name);
                    r = temp;
                    temp = null;
                }
            }

        }

    }

    // 后序遍历(非递归2)
    void nonPostOrder2(Node tree) {
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp;
        temp = tree;
        stack.push(temp);
        temp = temp.lchild;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.lchild;
            }

            temp = stack.pop();
            if (temp.rchild != null && temp.status == false) {
                stack.push(temp);
                temp.status = true;
                temp = temp.rchild;
            } else {
                System.out.println(temp.name);
                temp = null;
            }

        }
    }

    // 后序遍历(非递归3)
    void nonPostOrder3(Node tree) {
        Seqstack stack2 = new Seqstack();
        stack2.InitStack(20);
        if (tree == null) {
            System.out.println("树不存在");
            return;
        }
        Node temp = null;
        temp = tree;
        while (!stack.IsEmpty() || temp != null) {
            while (temp != null) {
                stack2.push(temp);
                stack.push(temp);
                temp = temp.rchild;
            }
            temp = stack.pop();
            temp = temp.lchild;
        }
        while (!stack2.IsEmpty()) {
            temp = stack2.pop();
            System.out.println(temp.name);

        }
    }

    // 层序遍历
    void cengxu(Node tree) {
        Node temp = null;
        queue.front = queue.rear = 0;
        if (tree == null) {
            System.out.println("该树为空");
            return;
        }
        queue.enterQueue(tree);
        while (queue.front != queue.rear) {
            temp = queue.deleteQueue();
            System.out.println(temp.name);
            if (temp.lchild != null) {
                queue.enterQueue(temp.lchild);
            }
            if (temp.rchild != null) {
                queue.enterQueue(temp.rchild);
            }

        }
    }

    // 递归计算树的深度
    int high(Node t) {
        int h = 0, left = 0, right = 0;
        if (t == null) {
            return 0;
        }
        left = high(t.lchild);
        right = high(t.rchild);
        h = (left > right ? left : right) + 1;
        return h;
    }

    // 反转二叉树(递归)
    void recReversal(Node tree) {
        if (tree == null) {
            return;
        }
        if (tree.lchild == null && tree.rchild == null) {
            return;
        }
        Node temp = tree.lchild;
        tree.lchild = tree.rchild;
        tree.rchild = temp;
        recReversal(tree.lchild);
        recReversal(tree.rchild);
    }

    // 反转二叉树(非递归)
    void nonRecReversal(Node tree) {
        Node t = null;
        if (tree == null) {
            System.out.println("树为空");
            return;
        }
        stack.push(tree);
        while (!stack.IsEmpty()) {
            Node temp = stack.pop();
            t = temp.lchild;
            temp.lchild = temp.rchild;
            temp.rchild = t;

            if (temp.rchild != null) {
                stack.push(temp.rchild);
            }
            if (temp.lchild != null) {
                stack.push(temp.lchild);
            }
        }
    }
    
    //统计叶子结点数（递归）
    int getLeafNum(Node tree) {
        if(tree == null) {
            return 0;
        }
        if(tree.lchild == null &&tree.rchild == null) {
            return 1;
        }
        return getLeafNum(tree.lchild) + getLeafNum(tree.rchild);           
    }
    
    // 统计结点数(递归)
    int getNodeNum(Node tree) {
        int nodes = 0;
        if (tree == null) {         
            return 0;
        }
        else {
            nodes = 1 + getNodeNum(tree.lchild) + getNodeNum(tree.rchild);
        }
        
        return nodes;
    }
    
    //判断一个结点是否是一个子树的结点
    boolean Ishave(Node tree,Node node) {
        if(node == null || tree == null) {
            return false;
        }
        if(tree.name.equals(node.name)) {
            return true;
        }
        else {
            return Ishave(tree.lchild, node) | Ishave(tree.rchild, node);
        }
        
    }

}

栈的结构：

//class Seqstack

public class Seqstack {
    // 节点数组(模拟顺序栈)
    public Node[] nodes;

    // 栈顶下标
    public int top;

    public Seqstack() {
        // TODO Auto-generated constructor stub
        this.top = -1;

    }

    // 初始化栈
    public void InitStack(int size) {
        this.nodes = new Node[size];
        this.top = -1;

    }

    // 判断栈空
    public boolean IsEmpty() {
        if (this.top == -1) {
            return true;
        }

        return false;
    }

    // 判断栈满
    public boolean IsFull() {
        if (this.top == this.nodes.length - 1) {
            return true;
        }

        return false;
    }

    // 入栈
    public void push(Node node) {
        if (IsFull()) {
            System.out.println("栈已经满了，入栈失败");
            return;
        }
        this.top++;
        this.nodes[this.top] = node;
    }

    // 出栈
    public Node pop() {
        if (IsEmpty()) {
            System.out.println("栈已经空了，出栈失败");
            return null;
        }
        Node node = this.nodes[this.top];
        this.top--;
        return node;

    }

    // 清空栈
    public void ClearStack() {
        // 如果不为空，就一直出栈
        while (!IsEmpty()) {
            Node node = pop();
        }

    }

    // 拿到栈顶元素
    public Node getTop() {
        if (IsEmpty()) {
            System.out.println("栈中没有元素");
            return null;
        }
        return this.nodes[this.top];
    }
}

循环队列的结构：

//class Seqqueue

public class Seqqueue {
    public Node[] queue;
    public int QUEUE_SIZE;
    public int front;
    public int rear;
    
    //初始化队列
        public void initQueue(int size) {
            this.QUEUE_SIZE = size;
            this.queue = new Node[size];
            this.front = 0;
            this.rear = 0;
        
        }
        
        //判断队列是否为空
        public boolean isEmpty() {
            if(this.front  == this.rear ) {
                return true;
            }
            else {
                return false;
            }
        }
        
        //判断队列是否为满
        public boolean isFull() {
            if((this.front % this.QUEUE_SIZE) == ((this.rear+1) % this.QUEUE_SIZE)) {
                return true;
            }
            else {
                return false;
            }
        }
        
        //入队
        public void enterQueue(Node node) {
            if(isFull()) {
                System.out.println("队列已经满了，入队失败");
                return;     
            }
            this.queue[this.rear] = node;
            this.rear ++;
            this.rear = this.rear % this.QUEUE_SIZE;
            
        }
        //出队
        public Node deleteQueue() {
            if(isEmpty()){
                System.out.println("队列为空，出队失败");
                return null;
            }
            this.front = this.front % this.QUEUE_SIZE;
            Node node = this.queue[this.front];
            
            this.front++;
            return node;
        }
}

给个测试用例：

//class Client

public class Client {
    public static void main(String[] args) {
        Tree tree = new Tree();
        Node node = null ;

        Node node4 = new Node("a");
        

        
        node = tree.createBiTree(node);     
        System.out.println("创建完成"); 
        
        
        
        System.out.println("递归先序遍历");
        tree.PreOrder(node);
        System.out.println("---------------------");
        System.out.println("非递归先序遍历");
        tree.nonPreOrder(node);
        System.out.println("---------------------");
        System.out.println("非递归先序遍历2");
        tree.nonPreOrder2(node);
        System.out.println("---------------------");
        
        
        
        System.out.println("递归中序遍历");
        tree.Inthread(node);
        System.out.println("---------------------");
        System.out.println("非递归中序遍历");
        tree.nonInthread(node);
        System.out.println("---------------------");
        
        
        
        System.out.println("后序遍历(递归)");
        tree.PostOrder(node);
        System.out.println("---------------------");
        System.out.println("后序遍历(非递归)");
        tree.nonPostOrder(node);
        System.out.println("---------------------");
        System.out.println("后序遍历(非递归2)");
        tree.nonPostOrder2(node);
        System.out.println("---------------------");
        System.out.println("后序遍历(非递归3)");
        tree.nonPostOrder3(node);
        System.out.println("---------------------");
        
        System.out.println("层序遍历");
        tree.cengxu(node);
        System.out.println("---------------------");
        
        
        
        System.out.println("树的深度"+tree.high(node));
        System.out.println("---------------------");
        
        
        
        System.out.println("递归反转二叉树");
        tree.recReversal(node);
        tree.cengxu(node);
        System.out.println("-------------------");
        
        
        System.out.println("非递归反转二叉树");
        tree.nonRecReversal(node);
        tree.cengxu(node);
        System.out.println("-------------------");
        
        System.out.println("树的叶子数:" + tree.getLeafNum(node));
        System.out.println("--------------------");
        
        System.out.println("树的结点数:" + tree.getNodeNum(node));
        System.out.println("--------------------");
        
        System.out.println("判断一个结点是否是一个子树上面的结点");
        System.out.println(tree.Ishave(node.lchild, node4));
    }
}

相关文章

  • 02. 树的遍历算法（递归和非递归实现）

    02. 树的遍历算法（递归和非递归实现） 树从存储方式上可分为顺序树和链式树 这节我们主要说的是链式树。 1. ...

  • 二叉树的遍历实现递归与非递归

    本文实现了二叉树的深度遍历算法，分为递归与非递归 递归的实现非常简单，基本上没啥难度 非递归的实现需要根据遍历的顺...

  • 【数据结构】【C#】026-二叉树（BT）：🌱遍历介绍

    一、递归遍历： 1、先序遍历：2、中序遍历：3、后续遍历：总结规律： 二、非递归遍历：利用栈来实现 非递归算法实现...

  • 二叉树遍历-JAVA实现

    基础二叉树 二叉树遍历分为前序、中序、后序递归和非递归遍历、还有层序遍历。 前序递归遍历算法：访问根结点-->递归...

  • 总结

    1、二叉树广度遍历（非递归） 广度遍历非递归实现需要依靠一个队列。 2、二叉树深度遍历（递归与非递归，前序，中序和...

  • 数据结构-树的遍历

    1. 先序遍历 递归实现 非递归实现 2. 中序遍历 递归实现 非递归实现 3. 后序遍历 递归实现 非递归实现 ...

  • 算法之二叉树

    二叉树之C++实现 创建二叉树 复制二叉树 先序遍历 递归实现 非递归实现 中序遍历 递归实现 非递归实现 后序遍...

  • 二叉树的三种深度优先遍历算法与思路

    看了一些关于二叉树遍历算法的文章，例如：二叉树三种遍历方式的递归和循环实现二叉树的递归与非递归遍历（前序、中序、后...

  • 树的遍历算法

    树的递归遍历 树的层次遍历 树的非递归前序遍历 树的非递归中序遍历

  • 二叉树的遍历 递归 非递归 Java

    二叉树的常用遍历算法实现 前序遍历 递归实现 非递归实现（1）这个是常规思路，先遍历到根节点，并打印、压栈，然后遍...

网友评论

      本文标题：02. 树的遍历算法（递归和非递归实现）

      本文链接：https://www.haomeiwen.com/subject/hjbqwrtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|02. 树的遍历算法（递归和非递归实现）|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！