《java实现二叉树的创建递归非递归遍历》由会员分享，可在线阅读，更多相关《java实现二叉树的创建递归非递归遍历（11页珍藏版）》请在金锄头文库上搜索。
1、Java 实现二叉树的创建、递归非递归遍历/* 二叉树的结点定义*/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);pub
2、lic 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;java
3、view plaincopyimport 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
4、 + 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 #
5、# 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(
6、).equals(#)return null;elsenode = 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 != nul
7、l)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)S
8、ystem.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.
9、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();Sys
10、tem.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();/* 后序非递
11、归遍历二叉树*/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();/* 如果右结点
12、为空，或者右结点之前遍历过，打印根结点 */if(node.getRight() = null | node.getRight() =preNode)System.out.println(node.getValue();node = stack.pop();preNode = node;node = null;elsenode = node.getRight();/* 层次遍历二叉树*/public void levelTraverse()levelTraverse(root);private void levelTraverse(Node<T> node) Queue<Nod
