樹的遍歷演算法java
『壹』 二叉樹的java實現與幾種遍歷
二叉樹的定義
二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.
從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式
二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷
前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹
中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹
後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點
其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序
具體實現看下圖：
『貳』 怎樣使用java對二叉樹進行層次遍歷
publicclassBinaryTree{
intdata;//根節點數據
BinaryTreeleft;//左子樹
BinaryTreeright;//右子樹
publicBinaryTree(intdata)//實例化二叉樹類
{
this.data=data;
left=null;
right=null;
}
publicvoidinsert(BinaryTreeroot,intdata){//向二叉樹中插入子節點
if(data>root.data)//二叉樹的左節點都比根節點小
{
if(root.right==null){
root.right=newBinaryTree(data);
}else{
this.insert(root.right,data);
}
}else{//二叉樹的右節點都比根節點大
if(root.left==null){
root.left=newBinaryTree(data);
}else{
this.insert(root.left,data);
}
}
}
}
當建立好二叉樹類後可以創建二叉樹實例，並實現二叉樹的先根遍歷，中根遍歷，後根遍歷，代碼如下：
packagepackage2;
publicclassBinaryTreePreorder{
publicstaticvoidpreOrder(BinaryTreeroot){//先根遍歷
if(root!=null){
System.out.print(root.data+"-");
preOrder(root.left);
preOrder(root.right);
}
}
publicstaticvoidinOrder(BinaryTreeroot){//中根遍歷
if(root!=null){
inOrder(root.left);
System.out.print(root.data+"--");
inOrder(root.right);
}
}
publicstaticvoidpostOrder(BinaryTreeroot){//後根遍歷
if(root!=null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"---");
}
}
publicstaticvoidmain(String[]str){
int[]array={12,76,35,22,16,48,90,46,9,40};
BinaryTreeroot=newBinaryTree(array[0]);//創建二叉樹
for(inti=1;i<array.length;i++){
root.insert(root,array[i]);//向二叉樹中插入數據
}
System.out.println("先根遍歷：");
preOrder(root);
System.out.println();
System.out.println("中根遍歷：");
inOrder(root);
System.out.println();
System.out.println("後根遍歷：");
postOrder(root);
『叄』 java層次遍歷演算法思路
找個例子看一下就有了。比如遞歸前序遍歷二叉樹，即先根遍歷。先遍歷根節點，之後向下又是一個跟節點，在遍歷做節點，在遍歷右節點，依次下去，知道沒有右節點結束。在遍歷右邊的部分，根節點，左節點，右節點，知道沒有右節點是為止。至此遍歷結束。書上有圖一看就知道了。其他的遍歷按照遍歷演算法一樣。建議看下數據結構的遍歷，講的很詳細。
『肆』 用Java實現一個樹形結構，並對其進行遍歷
importjava.util.Iterator;
importjava.util.Random;
importjava.util.TreeSet;
publicclassDemo{
publicstaticvoidmain(String[]args)throwsException{
TreeSet<Integer>ts=newTreeSet<Integer>();
for(inti=0;i<10;i++){
ts.add(newRandom().nextInt(999));
}
for(Iterator<Integer>it=ts.iterator();it.hasNext();){
System.out.println(it.next());
}
}
}
//上面是利用TreeSet進行簡單的二叉樹實現，另有遍歷，當然遍歷是自然順序。
//如有需要請自行修改吧。
『伍』 java Map 怎麼遍歷
關於java中遍歷map具體有四種方式，請看下文詳解。
1、這是最常見的並且在大多數情況下也是最可取的遍歷方式，在鍵值都需要時使用。
Map<Integer, Integer> map = newHashMap<Integer, Integer>();
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("Key = "+ entry.getKey() + ", Value = "+ entry.getValue());
}
2、在for-each循環中遍歷keys或values。
如果只需要map中的鍵或者值，你可以通過keySet或values來實現遍歷，而不是用entrySet。
Map<Integer, Integer> map = newHashMap<Integer, Integer>();
for(Integer key : map.keySet()) {
System.out.println("Key = "+ key);
}
for(Integer value : map.values()) {
System.out.println("Value = "+ value);
}
該方法比entrySet遍歷在性能上稍好（快了10%），而且代碼更加干凈。
3、使用Iterator遍歷
使用泛型：
Map<Integer, Integer> map = newHashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while(entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.println("Key = "+ entry.getKey() + ", Value = "+ entry.getValue());
}
不使用泛型：
Map map = newHashMap();
Iterator entries = map.entrySet().iterator();
while(entries.hasNext()) {
Map.Entry entry = (Map.Entry) entries.next();
Integer key = (Integer)entry.getKey();
Integer value = (Integer)entry.getValue();
System.out.println("Key = "+ key + ", Value = "+ value);
}
4、通過鍵找值遍歷（效率低）
Map<Integer, Integer> map = newHashMap<Integer, Integer>();
for(Integer key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key = "+ key + ", Value = "+ value);
}
假設Map中的鍵值對為1=>11,2=>22,3=>33,現用方法1來遍歷Map代碼和調試結果如下：
(5)樹的遍歷演算法java擴展閱讀：
1、HashMap的重要參數
HashMap 的實例有兩個參數影響其性能：初始容量 和載入因子。容量是哈希表中桶的數量，初始容量只是哈希表在創建時的容量。
載入因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。
在Java編程語言中，載入因子默認值為0.75，默認哈希表元為101。
2、HashMap的同步機制
注意，此實現不是同步的。 如果多個線程同時訪問一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。
（結構上的修改是指添加或刪除一個或多個映射關系的任何操作；以防止對映射進行意外的非同步訪問，如下：
Map m = Collections.synchronizedMap(new HashMap(...));
『陸』 java中的遍歷是什麼意思
遍歷就是把每個元素都訪問一次.比如一個二叉樹,遍歷二叉樹意思就是把二叉樹中的每個元素都訪問一次
『柒』 java 二叉樹前序遍歷
//類Node定義二叉樹結點的數據結構;
//一個結點應包含結點值，左子結點的引用和右子結點的引用
class Node{
public Node left; //左子結點
public Node right; //右子結點
public int value; //結點值
public Node(int val){
value = val;
}
}
public class Traversal
{
//read()方法將按照前序遍歷的方式遍歷輸出二叉樹的結點值
//此處採用遞歸演算法會比較簡單，也容易理解，當然也可以用
//循環的方法遍歷，但會比較復雜，也比較難懂。二叉樹遍歷
//用遞歸演算法最為簡單，因為每個結點的遍歷方式都是，根，
//左，右，遞歸的調用可以讓每個結點以這種方式遍歷
public static void read(Node node){
if(node != null){
System.out.println(node.value);//輸出當前結點的值
if(node.left != null)
read(node.left); //遞歸調用 先讀左結點
if(node.right != null)
read(node.right); //遞歸調用 後讀右結點
}
}
public static void main(String[] args){
//初始化5個結點，分別初始值為1，2，3，4，5
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
//構建二叉樹，以n1為根結點
n1.left = n2;
n1.right = n5;
n2.left = n3;
n2.right = n4;
read(n1);
}
}
注釋和代碼都是我自己寫的，如果樓主覺得有的注釋多餘可以自己刪除一些！代碼我都編譯通過，並且運行結果如你提的要求一樣！你只要把代碼復制編譯就可以了，注意要以文件名Traversal.java來保存，否則編譯不通過，因為main函數所在的類是public類型的！
『捌』 java 實現二叉樹的層次遍歷
class TreeNode {
public TreeNode left;
public TreeNode right;
public int value;
public TreeNode(TreeNode left, TreeNode right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
}
public class BinaryTree {
public static int getTreeHeight(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math
.max(getTreeHeight(root.left), getTreeHeight(root.right));
}
public static void recursePreOrder(TreeNode root) {
if (root == null)
return;
System.out.println(root.value);
if (root.left != null)
recursePreOrder(root.left);
if (root.right != null)
recursePreOrder(root.right);
}
public static void stackPreOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
stack.push(root);
System.out.println(root.value);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
temp = temp.right;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}
public static void recurseInOrder(TreeNode root) {
if (root == null)
return;
if (root.left != null)
recurseInOrder(root.left);
System.out.println(root.value);
if (root.right != null)
recurseInOrder(root.right);
}
public static void stackInOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
else
stack.push(root);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
System.out.println(temp.value);
temp = temp.right;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(null, null, 1);
TreeNode node2 = new TreeNode(null, node1, 2);
TreeNode node3 = new TreeNode(null, null, 3);
TreeNode node4 = new TreeNode(node2, node3, 4);
TreeNode node5 = new TreeNode(null, null, 5);
TreeNode root = new TreeNode(node4, node5, 0);
System.out.println("Tree Height is " + getTreeHeight(root));
System.out.println("Recurse In Order Traverse");
recurseInOrder(root);
System.out.println("Stack In Order Traverse");
stackInOrder(root);
System.out.println("Recurse Pre Order Traverse");
recursePreOrder(root);
System.out.println("Stack Pre Order Traverse");
stackPreOrder(root);
}
}
可以做個參考