java遍歷二叉樹演算法

❶ java實現二叉樹的問題

/**
* 二叉樹測試二叉樹順序存儲在treeLine中，遞歸前序創建二叉樹。另外還有能
* 夠前序、中序、後序、按層遍歷二叉樹的方法以及一個返回遍歷結果asString的
* 方法。
*/

public class BitTree {
public static Node2 root;
public static String asString;

//事先存入的數組,符號#表示二叉樹結束。
public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};

//用於標志二叉樹節點在數組中的存儲位置，以便在創建二叉樹時能夠找到節點對應的數據。
static int index;

//構造函數
public BitTree() {
System.out.print("測試二叉樹的順序表示為：");
System.out.println(treeLine);
this.index = 0;
root = this.setup(root);
}

//創建二叉樹的遞歸程序
private Node2 setup(Node2 current) {
if (index >= treeLine.length) return current;
if (treeLine[index] == '#') return current;
if (treeLine[index] == ' ') return current;
current = new Node2(treeLine[index]);
index = index * 2 + 1;
current.left = setup(current.left);
index ++;
current.right = setup(current.right);
index = index / 2 - 1;
return current;
}

//二叉樹是否為空。
public boolean isEmpty() {
if (root == null) return true;
return false;
}

//返回遍歷二叉樹所得到的字元串。
public String toString(int type) {
if (type == 0) {
asString = "前序遍歷：\t";
this.front(root);
}
if (type == 1) {
asString = "中序遍歷：\t";
this.middle(root);
}
if (type == 2) {
asString = "後序遍歷：\t";
this.rear(root);
}
if (type == 3) {
asString = "按層遍歷：\t";
this.level(root);
}
return asString;
}

//前序遍歷二叉樹的循環演算法，每到一個結點先輸出，再壓棧，然後訪問它的左子樹，
//出棧，訪問其右子樹，然後該次循環結束。
private void front(Node2 current) {
StackL stack = new StackL((Object)current);
do {
if (current == null) {
current = (Node2)stack.pop();
current = current.right;
} else {
asString += current.ch;
current = current.left;
}
if (!(current == null)) stack.push((Object)current);
} while (!(stack.isEmpty()));
}

//中序遍歷二叉樹
private void middle(Node2 current) {
if (current == null) return;
middle(current.left);
asString += current.ch;
middle(current.right);
}

//後序遍歷二叉樹的遞歸演算法
private void rear(Node2 current) {
if (current == null) return;
rear(current.left);
rear(current.right);
asString += current.ch;
}

}

/**
* 二叉樹所使用的節點類。包括一個值域兩個鏈域
*/

public class Node2 {
char ch;
Node2 left;
Node2 right;

//構造函數
public Node2(char c) {
this.ch = c;
this.left = null;
this.right = null;
}

//設置節點的值
public void setChar(char c) {
this.ch = c;
}

//返回節點的值
public char getChar() {
return ch;
}

//設置節點的左孩子
public void setLeft(Node2 left) {
this.left = left;
}

//設置節點的右孩子
public void setRight (Node2 right) {
this.right = right;
}

//如果是葉節點返回true
public boolean isLeaf() {
if ((this.left == null) && (this.right == null)) return true;
return false;
}
}

一個作業題，裡面有你要的東西。
主函數自己寫吧。當然其它地方也有要改的。

❷ java層次遍歷演算法思路

找個例子看一下就有了。比如遞歸前序遍歷二叉樹，即先根遍歷。先遍歷根節點，之後向下又是一個跟節點，在遍歷做節點，在遍歷右節點，依次下去，知道沒有右節點結束。在遍歷右邊的部分，根節點，左節點，右節點，知道沒有右節點是為止。至此遍歷結束。書上有圖一看就知道了。其他的遍歷按照遍歷演算法一樣。建議看下數據結構的遍歷，講的很詳細。

❸ 二叉樹三種遍歷技巧

在二叉樹的前序遍歷，中序遍歷，後序遍歷這三種遍歷方式中，有兩個相同的特點就是左子樹總是在右子樹的之前遍歷。還有他們的遍歷都可以用遞歸的方式來描述。
前序遍歷的方式是：首先訪問根節點，然後訪問左子樹，最後訪問右子樹。
中序遍歷的方式是：首先訪問左子樹，接著訪問根結點，最後訪問右子樹。
後序遍歷的方式是：首先訪問左子樹，接著訪問右子樹，最後訪問根結點。

❹ 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代碼和調試結果如下：

(4)java遍歷二叉樹演算法擴展閱讀：

1、HashMap的重要參數

HashMap 的實例有兩個參數影響其性能：初始容量 和載入因子。容量是哈希表中桶的數量，初始容量只是哈希表在創建時的容量。

載入因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。

在Java編程語言中，載入因子默認值為0.75，默認哈希表元為101。

2、HashMap的同步機制

注意，此實現不是同步的。 如果多個線程同時訪問一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。

（結構上的修改是指添加或刪除一個或多個映射關系的任何操作；以防止對映射進行意外的非同步訪問，如下：

Map m = Collections.synchronizedMap(new HashMap(...));

❺ 用java怎麼構造一個二叉樹呢

二叉樹的相關操作，包括創建，中序、先序、後序（遞歸和非遞歸），其中重點的是java在先序創建二叉樹和後序非遞歸遍歷的的實現。
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree<T> {

private Node<T> root;

public Tree() {
}

public Tree(Node<T> root) {
this.root = root;
}

//創建二叉樹
public void buildTree() {

Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍歷創建二叉樹
private Node<T> createTree(Node<T> node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}

}

//中序遍歷(遞歸)
public void inOrderTraverse() {
inOrderTraverse(root);
}

public 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 preOrderTraverse() {
preOrderTraverse(root);
}

public 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 postOrderTraverse() {
postOrderTraverse(root);
}

public 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.peek();

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);
}

public void levelTraverse(Node<T> node) {

Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {

Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}

}

}

}

//樹的節點

class Node<T> {

private Node<T> left;
private Node<T> right;
private T value;

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 left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}

}
測試代碼：
package com.algorithm.tree;

public class TreeTest {

/**
* @param args
*/
public static void main(String[] args) {
Tree<Integer> tree = new Tree<Integer>();
tree.buildTree();
System.out.println("中序遍歷");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("後續遍歷");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍歷");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();

//
}

}

❻ 遍歷二叉樹

遍歷方案：
1．遍歷方案
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
（1）訪問結點本身(N)，
（2）遍歷該結點的左子樹(L)，
（3）遍歷該結點的右子樹(R)。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。
2．三種遍歷的命名
根據訪問結點操作發生位置命名：
① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))
——訪問結點的操作發生在遍歷其左右子樹之前。
② LNR：中序遍歷(InorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之中(間)。
③ LRN：後序遍歷(PostorderTraversal)
——訪問結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和後根遍歷。
遍歷演算法
1．中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
2．先序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1) 訪問根結點；
(2) 遍歷左子樹；
(3) 遍歷右子樹。
3．後序遍歷得遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)遍歷右子樹；
(3)訪問根結點。
4．中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void InOrder(BinTree T)
{ //演算法里①~⑥是為了說明執行過程加入的標號
① if(T) { // 如果二叉樹非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 訪問結點
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
遍歷序列
1．遍歷二叉樹的執行蹤跡
三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。
具體線路為：
從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。
2．遍歷序列
A
/ \
B C
/ / \
D E F
圖
（1） 中序序列（inorder traversal）
中序遍歷二叉樹時，對結點的訪問次序為中序序列
【例】中序遍歷上圖所示的二叉樹時，得到的中序序列為：
D B A E C F
（2） 先序序列（preorder traversal）
先序遍歷二叉樹時，對結點的訪問次序為先序序列
【例】先序遍歷上圖所示的二叉樹時，得到的先序序列為：
A B D C E F
（3） 後序序列（postorder traversal）
後序遍歷二叉樹時，對結點的訪問次序為後序序列
【例】後序遍歷上圖所示的二叉樹時，得到的後序序列為：
D B E F C A
（4）層次遍歷（level traversal）二叉樹的操作定義為：若二叉樹為空，則退出，否則，按照樹的結構，從根開始自上而下，自左而右訪問每一個結點，從而實現對每一個結點的遍歷
注意：
（1）在搜索路線中，若訪問結點均是第一次經過結點時進行的，則是前序遍歷；若訪問結點均是在第二次(或第三次)經過結點時進行的，則是中序遍歷(或後序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經過的結點分別列表，即可分別得到該二叉樹的前序序列、中序序列和後序序列。
（2）上述三種序列都是線性序列，有且僅有一個開始結點和一個終端結點，其餘結點都有且僅有一個前趨結點和一個後繼結點。為了區別於樹形結構中前趨(即雙親)結點和後繼(即孩子)結點的概念，對上述三種線性序列，要在某結點的前趨和後繼之前冠以其遍歷次序名稱。
【例】上圖所示的二叉樹中結點C，其前序前趨結點是D，前序後繼結點是E；中序前趨結點是E，中序後繼結點是F；後序前趨結點是F，後序後繼結點是A。但是就該樹的邏輯結構而言，C的前趨結點是A，後繼結點是E和F。
二叉鏈表的構造
1． 基本思想
基於先序遍歷的構造，即以二叉樹的先序序列為輸入構造。
注意：
先序序列中必須加入虛結點以示空指針的位置。
【例】
建立上圖所示二叉樹，其輸入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
2． 構造演算法
假設虛結點輸入時以空格字元表示，相應的構造演算法為：
void CreateBinTree (BinTree *T)
{ //構造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身
char ch；
if((ch=getchar())=='') *T=NULL； //讀人空格，將相應指針置空
else{ //讀人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成結點
(*T)->data=ch；
CreateBinTree(&(*T)->lchild)； //構造左子樹
CreateBinTree(&(*T)->rchild)； //構造右子樹
}
}
注意：
調用該演算法時，應將待建立的二叉鏈表的根指針的地址作為實參。
【例】
設root是一根指針(即它的類型是BinTree)，則調用CreateBinTree(&root)後root就指向了已構造好的二叉鏈表的根結點。
二叉樹建立過程見http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm
下面是關於二叉樹的遍歷、查找、刪除、更新數據的代碼(遞歸演算法):
[code]
#include <iostream>
using namespace std;
typedef int T;
class bst{
struct Node{
T data;
Node* L;
Node* R;
Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}
};
Node* root;
int num;
public:
bst():root(NULL),num(0){}
void clear(Node* t){
if(t==NULL) return;
clear(t->L);
clear(t->R);
delete t;
}
~bst(){clear(root);}
void clear(){
clear(root);
num = 0;
root = NULL;
}
bool empty(){return root==NULL;}
int size(){return num;}
T getRoot(){
if(empty()) throw "empty tree";
return root->data;
}
void travel(Node* tree){
if(tree==NULL) return;
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
void travel(){
travel(root);
cout << endl;
}
int height(Node* tree){
if(tree==NULL) return 0;
int lh = height(tree->L);
int rh = height(tree->R);
return 1+(lh>rh?lh:rh);
}
int height(){
return height(root);
}
void insert(Node*& tree, const T& d){
if(tree==NULL)
tree = new Node(d);
else if(ddata)
insert(tree->L, d);
else
insert(tree->R, d);
}
void insert(const T& d){
insert(root, d);
num++;
}
Node*& find(Node*& tree, const T& d){
if(tree==NULL) return tree;
if(tree->data==d) return tree;
if(ddata)
return find(tree->L, d);
else
return find(tree->R, d);
}
bool find(const T& d){
return find(root, d)!=NULL;
}
bool erase(const T& d){
Node*& pt = find(root, d);
if(pt==NULL) return false;
combine(pt->L, pt->R);
Node* p = pt;
pt = pt->R;
delete p;
num--;
return true;
}
void combine(Node* lc, Node*& rc){
if(lc==NULL) return;
if(rc==NULL) rc = lc;
else combine(lc, rc->L);
}
bool update(const T& od, const T& nd){
Node* p = find(root, od);
if(p==NULL) return false;
erase(od);
insert(nd);
return true;
}
};
int main()
{
bst b;
cout << "input some integers:";
for(;;){
int n;
cin >> n;
b.insert(n);
if(cin.peek()=='\n') break;
}
b.travel();
for(;;){
cout << "input data pair:";
int od, nd;
cin >> od >> nd;
if(od==-1&&nd==-1) break;
b.update(od, nd);
b.travel();
}
}
[/code]

❼ 什麼是樹的遍歷java

樹遍歷方法:有先序遍歷、中序遍歷、後序遍歷以及廣度優先遍歷四種遍歷樹的方法

Demo:

publicclassThreeLinkBinTree<E>{

publicstaticclassTreeNode{

Objectdata;
TreeNodeleft;
TreeNoderight;
TreeNodeparent;

publicTreeNode(){

}

publicTreeNode(Objectdata){
this.data=data;
}

publicTreeNode(Objectdata,TreeNodeleft,TreeNoderight,TreeNodeparent){
this.data=data;
this.left=left;
this.right=right;
this.parent=parent;
}

}

privateTreeNoderoot;

//以默認的構造器創建二叉樹
publicThreeLinkBinTree(){
this.root=newTreeNode();
}

//以指定根元素創建二叉樹
publicThreeLinkBinTree(Edata){
this.root=newTreeNode(data);
}

/**
*為指定節點添加子節點
*
*@paramparent需要添加子節點的父節點的索引
*@paramdata新子節點的數據
*@paramisLeft是否為左節點
*@return新增的節點
*/
publicTreeNodeaddNode(TreeNodeparent,Edata,booleanisLeft){

if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
if(isLeft&&parent.left!=null){
thrownewRuntimeException(parent+"節點已有左子節點，無法添加左子節點");
}
if(!isLeft&&parent.right!=null){
thrownewRuntimeException(parent+"節點已有右子節點，無法添加右子節點");
}

TreeNodenewNode=newTreeNode(data);
if(isLeft){
//讓父節點的left引用指向新節點
parent.left=newNode;
}else{
//讓父節點的left引用指向新節點
parent.right=newNode;
}
//讓新節點的parent引用到parent節點
newNode.parent=parent;
returnnewNode;
}

//判斷二叉樹是否為空
publicbooleanempty(){
//根據元素判斷二叉樹是否為空
returnroot.data==null;
}

//返回根節點
publicTreeNoderoot(){
if(empty()){
thrownewRuntimeException("樹為空，無法訪問根節點");
}
returnroot;
}

//返回指定節點（非根節點）的父節點
publicEparent(TreeNodenode){
if(node==null){
thrownewRuntimeException("節點為null，無法訪問其父節點");
}
return(E)node.parent.data;
}

//返回指定節點（非葉子）的左子節點，當左子節點不存在時返回null
publicEleftChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
returnparent.left==null?null:(E)parent.left.data;
}

//返回指定節點（非葉子）的右子節點，當右子節點不存在時返回null
publicErightChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
returnparent.right==null?null:(E)parent.right.data;
}

//返回該二叉樹的深度
publicintdeep(){
//獲取該樹的深度
returndeep(root);
}

//這是一個遞歸方法：每一棵子樹的深度為其所有子樹的最大深度+1
privateintdeep(TreeNodenode){
if(node==null){
return0;
}
//沒有子樹
if(node.left==null&&node.right==null){
return1;
}else{
intleftDeep=deep(node.left);
intrightDeep=deep(node.right);
//記錄其所有左、右子樹中較大的深度
intmax=leftDeep>rightDeep?leftDeep:rightDeep;
//返回其左右子樹中較大的深度+1
returnmax+1;
}
}

//實現先序遍歷
//1、訪問根節點
//2、遞歸遍歷左子樹
//3、遞歸遍歷右子樹
publicList<TreeNode>preIterator(){
returnpreIterator(root);
}

privateList<TreeNode>preIterator(TreeNodenode){

List<TreeNode>list=newArrayList<TreeNode>();
//處理根節點
list.add(node);

//遞歸處理左子樹
if(node.left!=null){
list.addAll(preIterator(node.left));
}

//遞歸處理右子樹
if(node.right!=null){
list.addAll(preIterator(node.right));
}

returnlist;

}

//實現中序遍歷
//1、遞歸遍歷左子樹
//2、訪問根節點
//3、遞歸遍歷右子樹
publicList<TreeNode>inIterator(){
returninIterator(root);
}

privateList<TreeNode>inIterator(TreeNodenode){

List<TreeNode>list=newArrayList<TreeNode>();

//遞歸處理左子樹
if(node.left!=null){
list.addAll(inIterator(node.left));
}

//處理根節點
list.add(node);

//遞歸處理右子樹
if(node.right!=null){
list.addAll(inIterator(node.right));
}

returnlist;

}

//實現後序遍歷
//1、遞歸遍歷左子樹
//2、遞歸遍歷右子樹
//3、訪問根節點
publicList<TreeNode>postIterator(){
returnpostIterator(root);
}

privateList<TreeNode>postIterator(TreeNodenode){

List<TreeNode>list=newArrayList<TreeNode>();

//遞歸處理左子樹
if(node.left!=null){
list.addAll(postIterator(node.left));
}

//遞歸處理右子樹
if(node.right!=null){
list.addAll(postIterator(node.right));
}

//處理根節點
list.add(node);

returnlist;

}

//實現廣度優先遍歷
//廣度優先遍歷又稱為按層遍歷，整個遍歷演算法先遍歷二叉樹的第一層（根節點），再遍歷根節點的兩個子節點（第二層），以此類推
publicList<TreeNode>breadthFirst(){

Queue<TreeNode>queue=newArrayDeque<TreeNode>();
List<TreeNode>list=newArrayList<TreeNode>();
if(root!=null){
//將根元素加入「隊列」
queue.offer(root);
}
while(!queue.isEmpty()){
//將該隊列的「隊尾」的元素添加到List中
list.add(queue.peek());
TreeNodep=queue.poll();
//如果左子節點不為null，將它加入「隊列」
if(p.left!=null){
queue.offer(p.left);
}
//如果右子節點不為null，將它加入「隊列」
if(p.right!=null){
queue.offer(p.right);
}
}
returnlist;
}

}

❽ java二叉樹中序遍歷 的遞歸演算法沒有看懂。。search(data.getLeft());之後不就回到最左邊的一個

最左邊的節點是沒有左子樹和右子樹的。
if(data.getLeft()!=null){ // 這里getLetf()為null

search(data.getLeft());
}
System.out.print(data.getObj()+","); //只有這句是執行的！

if(data.getRight()!=null){ // 這里getRight()為null

search(data.getRight());
}

然後就會退到上一個節點的遍歷函數了。

❾ java構建二叉樹演算法

下面是你第一個問題的解法，是構建了樹以後又把後序輸出的程序。以前寫的，可以把輸出後序的部分刪除，還有檢驗先序中序的輸入是否合法的代碼也可以不要。/*****TreeNode.java*********/public class TreeNode {
char elem;
TreeNode left;
TreeNode right;
}/*******PlantTree.java*********/import java.io.*;
public class PlantTree {
TreeNode root;
public static void main(String[] args) {
PlantTree seed=new PlantTree();
String preorder=null;
String inorder=null;
try {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Please input the preorder");
preorder=br.readLine();
System.out.println("Please input the inorder");
inorder=br.readLine();
} catch (Exception e) {
// TODO: handle exception
}

if(preorder!=null&&seed.checkTree(preorder,inorder)) {

seed.root=new TreeNode();
seed.root.elem=preorder.charAt(0);
seed.makeTree(preorder,inorder,seed.root);
System.out.println("The tree has been planted,the postorder is:");
seed.printPostorder(seed.root);
}
}

void makeTree(String preorder,String inorder,TreeNode root) {
int i=inorder.lastIndexOf(root.elem);

if(i!=0) {//有左子樹
String leftPre=preorder.substring(1, i+1);
String leftIn=inorder.substring(0,i);
TreeNode leftNode=new TreeNode();
leftNode.elem=leftPre.charAt(0);
root.left=leftNode;
makeTree(leftPre,leftIn,leftNode);
}
if(i!=inorder.length()-1) {//有右子樹
String rightPre=preorder.substring(i+1,preorder.length());
String rightIn=inorder.substring(i+1,inorder.length());
TreeNode rightNode=new TreeNode();
rightNode.elem=rightPre.charAt(0);
root.right=rightNode;
makeTree(rightPre,rightIn,rightNode);
}

}
void printPostorder(TreeNode root) {
if(root.left!=null)
printPostorder(root.left);
if(root.right!=null)
printPostorder(root.right);
System.out.print(root.elem);

}
boolean checkTree(String a,String b) {
for(int i=0;i<a.length();i++) {
if(i!=a.lastIndexOf(a.charAt(i))) {
System.out.println("There are same element in the tree");
return false;
}
if(!b.contains(""+a.charAt(i))) {
System.out.println("Invalid input");
return false;
}

}
if(a.length()==b.length())
return true;
return false;
}
}