近期復習數據結構中的二叉樹的相關問題，在這里整理一下

這里包含：
1、二叉樹的先序創建

2、二叉樹的遞歸先序遍歷

3、二叉樹的非遞歸先序遍歷

4、二叉樹的遞歸中序遍歷

5、二叉樹的非遞歸中序遍歷

6、二叉樹的遞歸后序遍歷

7、二叉樹的非遞歸后序遍歷

8、二叉樹的層次遍歷

這里感謝博客http://blog.csdn.net/skylinesky/article/details/6611442的指導

/**二叉樹的結點定義*/ class Node<T>{private T value;private Node<T> left;private Node<T> right;public Node(){}public Node(Node<T> left, Node<T> right, T value){this.left = left;this.right = right;this.value = value;}public Node(T value){this(null, null, value);}public Node<T> getLeft(){return this.left;}public void setLeft(Node<T> left){this.left = left;}public Node<T> getRight(){return this.right;}public void setRight(Node<T> right){this.right = right;}public T getValue(){return this.value;}public void setValue(T value){this.value = value;} }

import java.io.File; import java.io.FileNotFoundException; import java.util.LinkedList; import java.util.Scanner;/*** 二叉樹的定義：或為空，或僅僅有根節點，或有左子樹和右子樹（5種基本形態）* 二叉樹性質：* 1、在二叉樹的第i層上至多有2^(i-1)個結點（i>=1）* 2、深度為k的二叉樹至多有2^(k) - 1個結點（k>=1）* 3、對于不論什么一顆二叉樹，假設其終端結點數為n，度數為2的結點數為m。則n = m + 1* 4、具有n個結點的全然二叉樹的深度為k = floor(log2(n)) + 1* 5、在含有n個結點的二叉鏈表中有n+1個空鏈域* * @author 小菜鳥*創建時間：2014-08-10*/public class BinaryTree<T> {/**二叉樹的根節點*/private Node<T> root;public BinaryTree(){}public BinaryTree(Node<T> root){this.root = root;}/**先序遍歷創建二叉樹*//**input.txt: - + a # # * # # / e # # f # #* # 代表空結點*/public void createBiTree(){Scanner scn = null;try {scn = new Scanner(new File("input.txt"));} catch (FileNotFoundException e) {e.printStackTrace();}this.root = createBiTree(root, scn);}private Node<T> createBiTree(Node<T> node, Scanner scn) {String temp = scn.next();if(temp.trim().equals("#")){return null;}else{node = new Node<T>((T)temp);node.setLeft(createBiTree(node.getLeft(), scn));node.setRight(createBiTree(node.getRight(), scn));return node;}}/**先序遞歸遍歷二叉樹*/public void preOrderTraverse(){preOrderTraverse(root);}private void preOrderTraverse(Node<T> node) {if(node != null){System.out.println(node.getValue());preOrderTraverse(node.getLeft());preOrderTraverse(node.getRight());}}/**先序非遞歸遍歷二叉樹*/public void nrPreOrderTraverse(){Stack<Node<T>> stack = new Stack<Node<T>>();Node<T> node = root;while(node != null || !stack.isEmpty()){while(node != null){System.out.println(node.getValue());stack.push(node);node = node.getLeft();}node = stack.pop();node = node.getRight();}}/**中序遞歸遍歷二叉樹*/public void inOrderTraverse(){inOrderTraverse(root);}private void inOrderTraverse(Node<T> node) {if(node != null){inOrderTraverse(node.getLeft());System.out.println(node.getValue());inOrderTraverse(node.getRight());}}/**中序非遞歸遍歷二叉樹*/public void nrInOrderTraverse(){Stack<Node<T>> stack = new Stack<Node<T>>();Node<T> node = root;while(node != null || !stack.isEmpty()){while(node != null){stack.push(node);node = node.getLeft();}node = stack.pop();System.out.println(node.getValue());node = node.getRight();}}/**后序遞歸遍歷二叉樹*/public void postOrderTraverse(){postOrderTraverse(root);}private void postOrderTraverse(Node<T> node) {if(node != null){postOrderTraverse(node.getLeft());postOrderTraverse(node.getRight());System.out.println(node.getValue());}}/**后序非遞歸遍歷二叉樹*/public void nrPostOrderTraverse(){Stack<Node<T>> stack = new Stack<Node<T>>();Node<T> node = root;Node<T> preNode = null; //記錄之前遍歷的右結點while(node != null || !stack.isEmpty()){while(node != null){stack.push(node);node = node.getLeft();}node = stack.getTop();/**假設右結點為空，或者右結點之前遍歷過。打印根結點*/if(node.getRight() == null || node.getRight() == preNode){System.out.println(node.getValue());node = stack.pop();preNode = node;node = null;}else{node = node.getRight();}}}/**層次遍歷二叉樹*/public void levelTraverse(){levelTraverse(root);}private void levelTraverse(Node<T> node) {Queue<Node<T>> queue = new Queue<Node<T>>();queue.push(node);while(!queue.isEmpty()){node = queue.pop();if(node != null){System.out.println(node.getValue());queue.push(node.getLeft());queue.push(node.getRight());}}}public static void main(String[] args){BinaryTree<String> bt = new BinaryTree<String>();bt.createBiTree();//bt.preOrderTraverse();//bt.inOrderTraverse();//bt.postOrderTraverse();//bt.nrPreOrderTraverse();//bt.nrInOrderTraverse();//bt.nrPostOrderTraverse();bt.levelTraverse();} }

【注：當中關于棧和隊列的定義請參考還有一篇博文】

Java實現棧和隊列的定義：http://blog.csdn.net/junwei_yu/article/details/38470825

總結

以上是生活随笔為你收集整理的Java实现二叉树的创建、递归/非递归遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。