二叉树链式存储和遍历

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（" 中序遍历（递归）："）;biTree.inOrderRecur（biTree.getRoot（））;System.out.print（" 后序遍历（递归）："）;biTree.postOrderRecur（biTree.getRoot（））;System.out.print（" 层次遍历："）;biTree.levelOrder（biTree.getRoot（））;System.out.print（" 先序遍历（非递归）："）;//biTree.preOrder（biTree.getRoot（））;biTree.preOrderOne（biTree.getRoot（））;System.out.print（" 中序遍历（非递归）："）;biTree.inOrder（biTree.getRoot（））;System.out.print（" 后序遍历（非递归）："）;biTree.postOrder（biTree.getRoot（））;}

2.1 输出结果

本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-05/131810.htm