java二叉樹非遞歸

⑴ 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別

在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：

[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}

BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);

while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}

return 0;
}

⑵ 如何不用遞歸遍歷二叉樹

非遞歸的方法是用存儲代替計算，就是在建立樹時，實現了存儲展開，相當於存儲了未來需要遍歷的路徑，所以就快了。遞歸是送快遞，一層層往下遞，非遞歸是先建好區域倉庫，由各地倉庫儲存發貨，所以速度更快，但需要倉庫儲存（內存佔用更多）。
二叉樹遍歷在數據結構中用得多，這種演算法是從kb時代的內存來的，主要用於理解概念，提升編程時的思想用。
實際用途中
如果用於商業一般用資料庫代替，根本用不到二叉樹，是用存儲代替計算。速度快，可以用內存資料庫，如我用h2 database的Memory Mode 在java下可以實現1秒1百萬次插入。用sqlite內存模式代替以前在c++需要手工管理的數據結構。數據量大一個電腦存不下時，用hadoop/spark/redis，對分布式大數據支持比較好。
如果用於計算量大的任務或內核結構，可以用矩陣數組，鏈表，k/v這種比較直觀模式存儲。
對於樹和圖這種在內存中復雜的數據結構，盡量不要在生產環境下使用，容易內存泄露，用簡單方式代替。對於圖結構，可以使用圖資料庫，如neo4j。對於樹結構，可以在資料庫中存儲一棵樹。實際上資料庫的存儲多用樹，如B樹、B-樹、B+樹、B*樹。
當然如果你寫加密演算法，這種要求極高的程序時，還是需要考慮性能最大化的，否則一般用存儲代替遍歷計算，因為內存和硬碟，現在很便宜了，而cpu還是一種寶貴的資源。

⑶ 用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 {

private Node root;

public Tree() {
}

public Tree(Node 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 createTree(Node node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {
return null;
} else {
node = new Node((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 node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}

//中序遍歷(非遞歸)
public void nrInOrderTraverse() {

Stack<Node> stack = new Stack<Node>();
Node 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 node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}

//先序遍歷（非遞歸）
public void nrPreOrderTraverse() {

Stack<Node> stack = new Stack<Node>();
Node 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 node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}

//後續遍歷(非遞歸)
public void nrPostOrderTraverse() {

Stack<Node> stack = new Stack<Node>();
Node node = root;
Node 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 node) {

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

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

}

}

}

//樹的節點

class Node {

private Node left;
private Node right;
private T value;

public Node() {
}
public Node(Node left,Node right,T value) {
this.left = left;
this.right = right;
this.value = value;
}

public Node(T value) {
this(null,null,value);
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node 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 tree = new Tree();
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();

//
}

}

⑷ 用JAVA語言實現二叉樹的層次遍歷的非遞歸演算法及查找演算法。

分塊查找
typedef struct
{ int key;
int link;
}SD;
typedef struct
{ int key;
float info;
}JD;

int blocksrch(JD r[],SD nd[],int b,int k,int n)
{ int i=1,j;
while((k>nd[i].key)&&(i<=b) i++;
if(i>b) { printf("\nNot found");
return(0);
}
j=nd[i].link;
while((j<n)&&(k!=r[j].key)&&(r[j].key<=nd[i].key))
j++;
if(k!=r[j].key) { j=0; printf("\nNot found"); }
return(j);
}

哈希查找演算法實現
#define M 100

int h(int k)
{ return(k%97);
}

int slbxxcz(int t[],int k)
{ int i,j=0;
i=h(k);
while((j<M)&&(t[(i+j)%M]!=k)&&(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k) return(i);
else return(-1);
}

int slbxxcr(int t[],int k)
{ int i,j=0;
i=h(k);
while((j<M)&&(t[(i+j)%M]!=k)&&(t[(i+j}%M]>0))
j++;
if(j==M) return(0);
i=(i+j)%M;
if(t[i]<=0)
{ t[i]=k; return(1); }
if(t[i]==k) return(1);
}

int slbxxsc(int t[],int k)
{ int i,j=0;
i=h(k);
while((j<M)&&(t[(i+j)%M]!=k)&&(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k)
{ t[i]=-1; return(1); }
return(0);
}

順序查找
#define M 500
typedef struct
{ int key;
float info;
}JD;

int seqsrch(JD r[],int n,int k)
{ int i=n;
r[0].key=k;
while(r[i].key!=k)
i--;
return(i);
}

折半查找
int binsrch(JD r[],int n,int k)
{ int low,high,mid,found;
low=1; high=n; found=0;
while((low<=high)&&(found==0))
{ mid=(low+high)/2;
if(k>r[mid].key) low=mid+1;
else if(k==r[mid].key) found=1;
else high=mid-1;
}
if(found==1)
return(mid);
else
return(0);
}

雖然都是C++寫的，萬變不離其中，JAVA我現在 剛學習，就不獻丑了

⑸ 如何用非遞歸演算法求二叉樹的高度

if（T＝＝null）

return0；

intfront＝－1，

rear＝－1；

／／front出隊指針

rear入隊指針intlast＝0，

level＝0；

／／last每一層的最右指針

（front＝＝last時候一層遍歷結束level＋＋）BiTreeQ［Maxsize］；

／／模擬隊列Q［＋＋rear］＝T；

BiTreep；

while(front<rear){

p＝Q［＋＋front］；／／開始出隊

因為front要趕到lash

實現level＋＋

if(p->lchild)

Q[++rear] = p->lchild;

if(p->rchild)

Q[++rear] = p->rchild;

if（front＝＝last）｛

level＋＋；

last＝rear；／／last指向下層節點｝

｝

(5)java二叉樹非遞歸擴展閱讀

非遞歸演算法思想：

（1）設置一個棧S存放所經過的根結點（指針）信息；初始化S；

（2）第一次訪問到根結點並不訪問，而是入棧；

（3）中序遍歷它的左子樹，左子樹遍歷結束後，第二次遇到根結點，就將根結點（指針）退棧，並且訪問根結點；然後中序遍歷它的右子樹。

（4）當需要退棧時，如果棧為空則結束。

⑹ 二叉樹中序遍歷的非遞歸演算法

推薦這篇文章，把二叉樹的前序、中序和後續的遞歸和非遞歸演算法都講了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html

⑺ 二叉樹的非遞歸遍歷有什麼優點

• 遞歸和非遞歸只是解決問題的方法的不同，本質還是一樣的。

2. 遞歸演算法相對於非遞歸演算法來說效率通常都會更低

2.1 遞歸演算法會有更多的資源需要壓棧和出棧操作（不僅僅是參數，還有函數地址等）

2.2 由於編譯器對附加的一些棧保護機制會導致遞歸執行的更加低效

3. 使用循環代替遞歸演算法，通常可以獲得更好的執行效率和空間效率，在二叉樹層次較深的情況下，採用非遞歸方式遍歷能夠有效的提升遍歷的性能。

⑻ 在二叉樹T中，編寫一個非遞歸程序輸出該樹的所有葉子結點。

importjava.util.LinkedList;
importjava.util.List;
importjava.util.Queue;


publicclassSolutions{
	publicstaticclassTreeNode{
		TreeNodeleft=null;
		TreeNoderight=null;
		intvalue;
		TreeNode(intvalue){
			this.value=value;
		}
		
		@Override
		publicStringtoString(){
			//TODOAuto-generatedmethodstub
			return"<TreeNodevalue:"+this.value+">";
		}
	}

	
	publicList<TreeNode>getLeaf(TreeNoderoot){
		List<TreeNode>result=newLinkedList<TreeNode>();
		Queue<TreeNode>nodeQueue=newLinkedList<TreeNode>();
		TreeNodenode=null;
		nodeQueue.add(root);
		while(!nodeQueue.isEmpty()){
			node=nodeQueue.poll();
			if(node.left==null){
				if(node.right==null){
					result.add(node);
				}else{
					nodeQueue.add(node.right);
				}
			}else{
				nodeQueue.add(node.left);
				if(node.right!=null){
					nodeQueue.add(node.right);
				}
			}
		}
				
		returnresult;
	}
	
	publicstaticvoidmain(String[]args){
		TreeNoderoot=newTreeNode(0);
		root.left=newTreeNode(1);
		root.right=newTreeNode(2);
		root.left.left=newTreeNode(3);
		root.left.right=newTreeNode(4);
		root.right.left=newTreeNode(5);
		root.right.right=newTreeNode(6);
		Solutionss=newSolutions();
		System.out.println(s.getLeaf(root));
		//[<TreeNodevalue:3>,<TreeNodevalue:4>,<TreeNodevalue:5>,<TreeNodevalue:6>]
	}
}

⑼ 用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();

//
}

}