你的位置:首页 > Java教程

[Java教程]二叉树链式存储和遍历


1 二叉树的链式存储

1.1 链式存储

      顺序存储对空间利用率较低,所以,二叉树一般采用链式存储结构,用一个链表来存储一颗二叉树。二叉链表至少包含3个域:数据域data左指针域lchild右指针域rchild,如果再加上一个指向双亲结点的指针就变成了三叉链表

 

二叉树的链式存储结构如下:

/** * 二叉链表结点 * @author cyhe */private class Node{  Integer data;  Node lchild, rchild;}

      根据完全二叉树的序列递归创建二叉树,输入序列时不存在的结点用0代替,以下是创建的代码和一些有用的方法。

/** * 存储先序输入的二叉树,默认大小为10,当超过10自动调用resize方法扩容 */private Integer[] nodes = new Integer[10];public LinkBiTree(){  init();}/** * 获取根节点 * @return */public Node getRoot(){  return root;}/** * 满了自动扩容 * @param max */private void resize(int max){  Integer[] temp = new Integer[max];  for(int i=0; i<nodes.length; i++){    temp[i] = nodes[i];  }  nodes = temp;}/** * 先序输入二叉树,不存在的结点使用0 */public void init(){  System.out.println("先序列输入一个二叉树,不存在的结点用0代替,使用逗号隔开:");//    String[] ins = StdIn.readString().split(",");  String[] ins = "1,2,3,4,0,5,7,8".split(",");  n = ins.length;  for (int i = 0; i < ins.length; i++) {    if(i>=nodes.length){      resize(2 * nodes.length); // 扩大两倍    }    nodes[i] = Integer.valueOf(ins[i]);  }  System.out.println("LinkBiTree [nodes=" + Arrays.toString(nodes) + "]");  root = build(1); // 递归创建树  System.out.println("输入的树高度为:"+depth(root));  print();}/** * 递归创建一颗树, 使用完全二叉树序列 * @param node * @param data */public Node build(int index){  if (index > n) {    return null;  }  Integer tmp = nodes[index - 1]; // 获取结点的值  if (tmp == 0) { // 若为 0 表示结点不存在    return null;  } else {    Node node = new Node();    node.data = tmp;    node.lchild = build(2 * index); // 创建左子树    node.rchild = build(2 * index + 1); // 创建右子树    return node;  }}/** * 递归获取二叉树的高度 * @return */public int depth(Node node){  if(node != null){    int l = depth(node.lchild); // 左子树高度    int r = depth(node.rchild); // 右子树高度    return l > r ? l + 1 : r + 1; // 树的高度为子树最大高度加上根节点  }  return 0; // 空树高度为0}

1.2 层次遍历

/** * 层次遍历,利用队列是实现 */public void levelOrder(Node root){  RingBuffer<Node> queue = new RingBuffer<Node>(n+1);  queue.put(root); // 根节点先进队列    while(queue.size()>0){    Node tmp = queue.get();    System.out.print(tmp.data + " "); // 根    if (tmp.lchild != null) { // 如果根节点的左子树存在,把左子树编号入栈      queue.put(tmp.lchild);    }        if (tmp.rchild != null) { // 如果根节点的右子树存在,把右子树编号入栈      queue.put(tmp.rchild);    }  }}

1.3 先序遍历

1.3.1 递归实现

/** * 递归先序遍历 */public void preOrderRecur(Node node){  if(node != null){    System.out.print(node.data+" "); // 根    preOrderRecur(node.lchild); // 左    preOrderRecur(node.rchild); // 右  }}

1.3.2 非递归实现

实现方法1:

/** * 非递归先序遍历 */public void preOrder(Node node){  ArrayStack<Node> stack = new ArrayStack<Node>(n + 1);  stack.push(node);  while (!stack.isEmpty()) {    Node tmp = stack.pop();    System.out.print(tmp.data + " "); // 根    if (tmp.rchild != null) { // 如果根节点的右子树存在,把右子树编号入栈      stack.push(tmp.rchild);    }    if (tmp.lchild != null) { // 如果根节点的左子树存在,把左子树编号入栈      stack.push(tmp.lchild);    }  }}

实现方法2:

/** * 非递归先序遍历 */public void preOrderOne(Node node){  ArrayStack<Node> stack = new ArrayStack<Node>(n + 1);  while (node != null || !stack.isEmpty()) {    while(node != null){ // 把最左侧的全部入栈      System.out.print(node.data + " "); // 根      stack.push(node);      node = node.lchild;    }    Node tmp = stack.pop(); // 弹出最后入栈的左子树    node = tmp.rchild; // 看它有没有右孩子  }}

1.4 中序遍历

1.4.1 递归实现

/** * 递归中序遍历 */public void inOrderRecur(Node node){  if(node != null){    inOrderRecur(node.lchild); // 左    System.out.print(node.data+" "); // 根    inOrderRecur(node.rchild); // 右  }}

1.4.2 非递归实现

/** * 非递归中序遍历 */public void inOrder(Node node){  ArrayStack<Node> stack = new ArrayStack<Node>(n + 1);  while (node != null || !stack.isEmpty()) {    while(node != null){ // 把最左侧的全部入栈      stack.push(node);      node = node.lchild;    }    Node tmp = stack.pop(); // 弹出最后入栈的左子树    System.out.print(tmp.data + " "); // 先访问左子树    node = tmp.rchild; // 看它有没有右孩子  }}

1.5 后序遍历

1.5.1 递归实现

/** * 递归后序遍历 */public void postOrderRecur(Node node){  if(node != null){    postOrderRecur(node.lchild); // 左    postOrderRecur(node.rchild); // 右    System.out.print(node.data+" "); // 根  }}

1.5.2 非递归实现

/** * 非递归后序遍历 */public void postOrder(Node node){  ArrayStack<Node> stack = new ArrayStack<Node>(n + 1);  Node pre = null; // 前一个访问的结点  while (node != null || !stack.isEmpty()) {    while(node != null){ // 把最左侧的全部入栈      stack.push(node);      node = node.lchild;    }    Node tmp = stack.peek(); // 现在要判断栈内结点有没有右孩子,或者右孩子是否访问过        // 如果当前结点不存在右孩子或者右孩子已经访问过,则访问当前结点    if(tmp.rchild == null || pre == tmp.rchild){      Node n = stack.pop();      System.out.print(n.data + " "); // 访问结点      pre = n;    } else {      node = tmp.rchild; // 否则访问右孩子    }  }}

2 测试

public static void main(String[] args) {  LinkBiTree<Integer> biTree = new LinkBiTree<Integer>();    System.out.print("先序遍历(递归):");  biTree.preOrderRecur(biTree.getRoot());  System.out.print("\n中序遍历(递归):");  biTree.inOrderRecur(biTree.getRoot());  System.out.print("\n后序遍历(递归):");  biTree.postOrderRecur(biTree.getRoot());  System.out.print("\n层次遍历:");  biTree.levelOrder(biTree.getRoot());  System.out.print("\n先序遍历(非递归):");//  biTree.preOrder(biTree.getRoot());  biTree.preOrderOne(biTree.getRoot());  System.out.print("\n中序遍历(非递归):");  biTree.inOrder(biTree.getRoot());  System.out.print("\n后序遍历(非递归):");  biTree.postOrder(biTree.getRoot());}

2.1 输出结果