java樹中序遍歷

㈠ 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是相鄰的兩個整數，故有
,
由此即得：

注意：
的證明

㈡ 求一個java遍歷比較完整樹的方法

//用中序遍歷一個二叉樹
class BinaryTree
{
class Node
{
private int data; //保存數據內容
private Node left; //左子樹
private Node right;//右子樹
public Node(int data){
this.data = data;
}
public void addNode(Node newNode){ //addNode方法用來添加數據
if(newNode.data <= this.data){
if(this.left == null){ //左子樹為空
this.left = newNode;
}else{
this.left.addNode(newNode);//繼續向下判斷
}
}
if(newNode.data > this.data){
if(this.right == null){ //右子樹為空
this.right = newNode;
}else{
this.right.addNode(newNode);//繼續向下判斷
}
}
} //addNode方法結束
public void printNode(){ //採用中序遍歷（左-根-右)
if(this.left != null){
this.left.printNode();
}
System.out.println(this.data); //找到根內容
if(this.right != null){
this.right.printNode();
}
}
} //Node類結束
private Node root; //根節點
public void add(int data){
Node newNode = new Node(data);
if(this.root == null){
this.root = newNode;
}else{
this.root.addNode(newNode);
}
}
public void print(){
this.root.printNode();
}
}
public class Demo
{
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
bt.add(3);
bt.add(4);
bt.add(0);
bt.add(1);
bt.print();
}
}

㈢ 二叉樹的java實現與幾種遍歷

二叉樹的定義

二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.

從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷

• 前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹

• 中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹

• 後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點

其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序

具體實現看下圖：

㈣ 急急急！！！要求用java實現二叉樹中序遍歷序列 具體要求如下

第一棵樹只有一個 1 節點，為什麼輸出序列有兩個 1？
第二棵樹只有一個 3 節點，為什麼輸出序列有兩個 3？
題目中的輸出序列是否不正確？

㈤ 二叉樹中序遍歷問題

你建二叉樹的時候沒有把左右孩子地址返回給父節點，遍歷時找不到左右孩子，當然就崩潰了。而且你的程序在不停地對一個野指針進行操作，這樣是很危險的。

create函數改成：

BiTreeCreate()
{
intx;
BiTreebt;
scanf("%d",&x);
if(x==0)bt=NULL;
else
{
bt=(BiTree)malloc(sizeof(BiTNode));
bt->data=x;
bt->LChild=Create();
bt->RChild=Create();
}
returnbt;
}

main函數改成：

intmain()
{
BiTreebt;
bt=Create();
InOrder(bt);
getch();
return0;
}

就可以了。

㈥ 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二叉樹中序遍歷 的遞歸演算法沒有看懂。。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中，遍歷是幹嘛用的有什麼意義

你說的比較籠統，遍歷的話，可以遍歷數組，遍歷list，遍歷鏈表，遍歷圖，樹等等，遍歷的意義就在於檢查集合中的元素並做處理。至於什麼順序，那要根據需求嘍。
例子，比較簡單的是，遍歷一個整型數組，找出裡面最大的數。

㈨ java二叉樹的順序表實現

做了很多年的程序員，覺得什麼樹的設計並不是非常實用。二叉樹有順序存儲，當一個insert大量同時順序自增插入的時候，樹就會失去平衡。樹的一方為了不讓塌陷，會增大樹的高度。性能會非常不好。以上是題外話。分析需求在寫代碼。
import java.util.List;

import java.util.LinkedList;

public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;

private static class Node {
Node leftChild;
Node rightChild;
int data;

Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}

// 創建二叉樹
public void createBintree() {
nodeList = new LinkedList<Node>();

// 將數組的值轉換為node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}

// 對除最後一個父節點按照父節點和孩子節點的數字關系建立二叉樹
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}

// 最後一個父節點
int lastParentIndex = array.length / 2 - 1;

// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果為奇數，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}

// 前序遍歷
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

// 中序遍歷
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}

inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}

// 後序遍歷
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}

postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}

public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);

System.out.println("前序遍歷：");
preOrderTraverse(root);
System.out.println();

System.out.println("中序遍歷：");
inOrderTraverse(root);
System.out.println();

System.out.println("後序遍歷：");
postOrderTraverse(root);
}
}

㈩ 什麼是樹的遍歷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;
}

}