服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - Java中二叉树的建立和各种遍历实例代码

Java中二叉树的建立和各种遍历实例代码

2021-03-15 12:32GavinZhou_xd Java教程

这篇文章主要介绍了Java中二叉树的建立和各种遍历实例代码,涉及树节点的定义,后序遍历,层序遍历,深度优先和广度优先等相关内容,具有一定借鉴价值,需要的朋友可以参考下

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题

先序+中序->建树

假设现在有个二叉树,如下:

Java中二叉树的建立和各种遍历实例代码

此时遍历顺序是:

?
1
2
3
PreOrder: GDAFEMHZ
InOrder: ADEFGHMZ
PostOrder: AEFDHZMG

现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树
或者给出中序(InOrder)和后序(PostOrder), 建立二叉树,其实是一样的

树节点的定义:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Tree{
    char val;
    Tree left;
    Tree right;
    Tree(char val, Tree left, Tree right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
    Tree(){
    }
    Tree(char val){
        this.val = val;
        this.left = null;
        this.right =null;
    }
}

建树:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static Tree buildTree(char[] preOrder, char[] inOrder){
    //preOrder是先序序列
    //inOrder是中序序列
    if(preOrder == null || preOrder.length == 0){
        return null;
    }
    Tree root = new Tree(preOrder[0]);
    //找到inOrder中的root的位置
    int inOrderIndex = 0;
    for (char i = 0; i < inOrder.length; i++){
        if(inOrder[i] == root.val){
            inOrderIndex = i;
        }
    }
    //preOrder的左子树和右子树部分
    char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);
    char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+inOrderIndex, preOrder.length);
    //inOrder的左子树和右子树部分
    char[] inOrderLeft = Arrays.copyOfRange(inOrder, 0, inOrderIndex);
    char[] inOrderRight = Arrays.copyOfRange(inOrder, inOrderIndex+1, inOrder.length);
    //递归建立左子树和右子树
    Tree leftChild = buildTree(preOrderLeft, inOrderLeft);
    Tree rightChild = buildTree(preOrderRight, inOrderRight);
    root.left = leftChild;
    root.right = rightChild;
    return root;
}

中序+后序去建树其实是一样的,此处不写了

各种遍历

后序遍历

?
1
2
3
4
5
6
7
8
9
10
11
public static void postOrderPrint(Tree root){
    //后续遍历
    //左右根
    if(root.left != null){
      postOrderPrint(root.left);
    }
    if(root.right != null){
      postOrderPrint(root.right);
    }
    System.out.print(root.val + " ");
  }

举一反三,先序和中序是一样的,此处不写了

层序遍历

可以用一个队列Queue,初始先把root节点加入到队列,当队列不为空的时候取队列头的节点node,打印node的节点值,如果node的左右孩子不为空将左右孩子加入到队列中即可

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void layerOrderPrint(Tree root){
    if(root == null){
      return;
    }
    //层序遍历
    Queue<Tree> qe = new LinkedList<Tree>();
    qe.add(root);
    while(!qe.isEmpty()){
      Tree node = qe.poll();
      System.out.print(node.val + " ");
      if(node.left != null){
        qe.add(node.left);
      }
      if(node.right != null){
        qe.add(node.right);
      }
    }
  }

深度优先和广度优先

其实就是换个说法而已,深度优先不就是先序遍历嘛,广度优先就是层序遍历

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void deepFirstPrint(Tree root){
    //深度优先遍历等价于先序遍历
    //所以可以直接使用先序遍历
    if(root == null){
      return;
    }
    System.out.print(root.val + " ");
    if(root.left != null){
      deepFirstPrint(root.left);
    }
    if(root.right != null){
      deepFirstPrint(root.right);
    }
  }
 
public static void deepFirstPrintNoneRec(Tree root){
    //深度优先遍历的非递归形式
    if(root == null){
      return;
    }
    Stack<Tree> st = new Stack<Tree>();
    st.add(root);
    while(!st.isEmpty()){
      Tree node = st.pop();
      System.out.print(node.val + " ");
      //栈是后进先出的
      //先加右孩子后加左孩子
      if(node.right != null){
        st.add(node.right);
      }
      if(node.left != null){
        st.add(node.left);
      }
    }
  }

main函数:

?
1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    char[] preOrder = "GDAFEMHZ".toCharArray();
    char[] inOrder = "ADEFGHMZ".toCharArray();
    Tree root = Main.buildTree(preOrder, inOrder);
//   Main.postOrderPrint(root); //后序遍历
//   Main.layerOrderPrint(root); //层序遍历
//   Main.deepFirstPrint(root); //深度优先遍历
//   Main.deepFirstPrintNoneRec(root); //深度优先遍历的非递归版本
  }

总结

以上就是本文关于Java中二叉树的建立和各种遍历实例代码的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/gavin__zhou/article/details/70199074

延伸 · 阅读

精彩推荐