java遞歸遍歷二叉樹
1. 用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();
//
}
}
2. 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());
}
然後就會退到上一個節點的遍歷函數了。
3. java 用遞歸創建二叉樹，非遞歸遍歷二叉樹輸出節點
我自己用遞歸寫了下，不知道能不能給你幫助：
測試類：
package tree;
import java.util.*;
public class Test {
public static void main(String[] args){
List<Tree> trees=new ArrayList<Tree>();
int id=1;
Tree tree1=new Tree(0,id++,"張三豐");
Tree tree2=new Tree(tree1.getId(),id++,"武當宋大俠宋遠橋");
Tree tree3=new Tree(tree1.getId(),id++,"武當俞二俠俞蓮舟");
Tree tree4=new Tree(tree1.getId(),id++,"武當俞三俠俞岱岩");
Tree tree5=new Tree(tree1.getId(),id++,"武當張四俠張松溪");
Tree tree6=new Tree(tree1.getId(),id++,"武當張五俠張翠山");
Tree tree7=new Tree(tree1.getId(),id++,"武當殷六俠殷梨亭");
Tree tree8=new Tree(tree1.getId(),id++,"武當莫七俠莫聲谷");
Tree tree9=new Tree(tree6.getId(),id++,"明教張無忌");
Tree tree13=new Tree(tree2.getId(),id++,"叛徒宋青書");
Tree tree10=new Tree(0,id++,"任我行");
Tree tree11=new Tree(tree10.getId(),id++,"令狐沖");
Tree tree12=new Tree(tree10.getId(),id++,"任盈盈");
trees.add(tree1);
trees.add(tree2);
trees.add(tree3);
trees.add(tree4);
trees.add(tree5);
trees.add(tree6);
trees.add(tree7);
trees.add(tree8);
trees.add(tree9);
trees.add(tree10);
trees.add(tree11);
trees.add(tree12);
trees.add(tree13);
for(int i=0;i<trees.size();i++){
Tree tree=trees.get(i);
if(tree.getParentId()==0){
tree.showChildTree(trees);
}
}
}
}
樹類：
package tree;
import java.util.List;
public class Tree {
private int parentId;
private int id;
private String showStr;
private String Spaces="";
public Tree() {
// TODO Auto-generated constructor stub
}
public Tree(int parentId,int id,String showStr){
this.parentId=parentId;
this.id=id;
this.showStr=showStr;
}
public void showChildTree(List<Tree> trees){
if(parentId!=0){
trees.get(id-1).setSpaces(trees.get(parentId-1).getSpaces()+" ");
}
System.out.println(trees.get(id-1).getSpaces()+showStr);
for(int i=0;i<trees.size();i++){
Tree tree=trees.get(i);
if(tree.getParentId()==id){
tree.showChildTree(trees);
}
}
}
public int getParentId() {
return parentId;
}
public void setParentId(int parentId) {
this.parentId = parentId;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getShowStr() {
return showStr;
}
public void setShowStr(String showStr) {
this.showStr = showStr;
}
public String getSpaces() {
return Spaces;
}
public void setSpaces(String spaces) {
Spaces = spaces;
}
}
效果圖：
張三豐
武當宋大俠宋遠橋
叛徒宋青書
武當俞二俠俞蓮舟
武當俞三俠俞岱岩
武當張四俠張松溪
武當張五俠張翠山
明教張無忌
武當殷六俠殷梨亭
武當莫七俠莫聲谷
任我行
令狐沖
任盈盈
4. java數據結構二叉樹查找結點操作，遞歸調用求詳細講解
這是先序遍歷樹的代碼，什麼是先序遍歷呢，一種按照根-左子樹-右子樹的順序遍歷樹就是先序遍歷。
CBTType TreeFindNode(CBTType treeNode,String data){
CBTType ptr;
if(treeNode==null){//輸入根節點為空時
return null;
}else{
if(treeNode.data.equals(data)){//根節點等於要查找的數據時
return treeNode;
}else{
if((ptr=TreeFindNode(treeNode.left,data))!=null){//從左子樹查找，為什麼可以用TreeFindNode表示呢？
return ptr;
}else if((ptr=TreeFindNode(treeNode.right,data))!=null){//從右子樹查找
return ptr;
}else{
return null;
}
}
}
}
從左子樹查找，為什麼可以用TreeFindNode表示呢？因為，左子樹也可以按照先序遍歷的順序查找的，所以當然可以用TreeFindNode表示，如果你想左子樹用中序遍歷查找，那麼就不可以用TreeFindNode表示。
上述例子的查找過程：
1 --根（2，4，5）--左（3，6，7）--右
2--根（4）--左（5）--右
4--根
5--根
返回
5. java 遞歸 算 二叉樹 層級
層次遍歷從方法上不具有遞歸的形式，所以一般不用遞歸實現。當然了，非要寫成遞歸肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("\n"); LevelOrder(level, rear); free(level); } 補充一下，在main裡面調用的時候就得用LevelOrder(T,1)了。
6. 遞歸創建二叉樹,java語言描述，有疑問
我手頭沒有工具，不方便試，不過看著這兩行有點問題：
Creat(root.getlchild(),str,j);
Creat(root.getrchild(),str,j);
你第一次創建的Node，左右都是null，所以你傳入這個方法的第一個參數都是null，那怎麼為它設置data呢？應該先為左右節點都創建對象，然後再這樣操作吧。
7. java二叉樹遍歷問題
二叉樹具有以下重要性質：
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
證明：用數學歸納法證明：
歸納基礎：i=1時，有2i-1=20=1。因為第1層上只有一個根結點，所以命題成立。
歸納假設：假設對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。
歸納步驟：根據歸納假設，第i-1層上至多有2i-2個結點。由於二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結點，故命題成立。
性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。因此利用性質1可得，深度為k的二叉樹的結點數至多為：
20+21+…+2k-1=2k-1
故命題正確。
性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
證明：因為二叉樹中所有結點的度數均不大於2，所以結點總數(記為n)應等於0度結點數、1度結點(記為n1)和2度結點數之和：
n=no+n1+n2 (式子1)
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：
nl+2n2
樹中只有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1
滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
1、滿二叉樹(FullBinaryTree)
一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
滿二叉樹的特點：
（1） 每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
（2） 滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。
圖(a)是一個深度為4的滿二叉樹。
2、完全二叉樹(Complete BinaryTree)
若一棵二叉樹至多隻有最下面的兩層上結點的度數可以小於2，並且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
特點：
（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
（2） 在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點後得到的二叉樹仍然是一棵完全二叉樹。
（3） 在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
如圖(c)中，結點F沒有左孩子而有右孩子L，故它不是一棵完全二叉樹。
圖(b)是一棵完全二叉樹。
性質4 具有n個結點的完全二叉樹的深度為
證明：設所求完全二叉樹的深度為k。由完全二叉樹定義可得：
深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
由於完全二叉樹深度為k，故第k層上還有若干個結點，因此該完全二叉樹的結點個數：
n>2k-1-1。
另一方面，由性質2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取對數後有：
k-1≤lgn<k
又因k-1和k是相鄰的兩個整數，故有
,
由此即得：
注意：
的證明
8. 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;
}
}
一個作業題，裡面有你要的東西。
主函數自己寫吧。當然其它地方也有要改的。
9. 用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();
//
}
}
10. java二叉樹遞歸演算法原理
「node.left!=null從根節點開始遞歸到9，跳出循環輸出9，接著判斷9的右節點為null；」
你這就話本身就有問題，輸出9時，那麼node是多少呢，是12，接著是判斷12的右節點，而不是9的右節點。
根節點是相對的，
你把9看成左節點，那麼12就是根節點，
按照中序遍歷規則，左中右，那麼輸出9就到12有什麼奇怪呢，
你把9看成根節點，它也是葉節點，沒有左右節點，那麼輸出9就到12有什麼奇怪呢。
你遞歸不懂就應該看譚浩強的遞歸分析，而不是來看二叉樹。