java二叉樹層次遍歷

㈠ 二叉樹的層次遍歷

設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存當前節點的左右孩子的隊列

InitQueue(Q); // 初始化隊列

if (Root == NULL) return ; //樹為空則返回
BiNode *p = Root; // 臨時保存樹根Root到指針p中
Visit(p->data); // 訪問根節點
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子進隊列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子進隊列

while (!QueueEmpty(Q)) // 若隊列不空，則層序遍歷 { DeQueue(Q, p); // 出隊列
Visit(p->data);// 訪問當前節點

if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子進隊列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子進隊列
}

DestroyQueue(Q); // 釋放隊列空間
return ;
這個已經很詳細了！你一定可以看懂的！加油啊！

㈡ 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)了。

㈢ 用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我現在 剛學習，就不獻丑了

㈣ 什麼是樹的層次遍歷 要求通俗易懂

就是按層(深度)遍歷整棵樹。

如果層次遍歷這棵樹，得到的序列就是12345678,遍歷時因為要一層一層的下來，所以一般用廣度優先遍歷。

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。

(4)java二叉樹層次遍歷擴展閱讀：

二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量。

給定N個節點，能構成h(N)種不同的二叉樹。h(N)為卡特蘭數的第N項。h(n)=C(2*n，n)/(n+1)。

設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i。

㈤ 怎樣使用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實現二叉樹層次遍歷

import java.util.ArrayList;

public class TreeNode {
private TreeNode leftNode;
private TreeNode rightNode;
private String nodeName;
public TreeNode getLeftNode() {
return leftNode;
}

public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}

public TreeNode getRightNode() {
return rightNode;
}

public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}

public String getNodeName() {
return nodeName;
}

public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public static int level=0;

public static void findNodeByLevel(ArrayList<TreeNode> nodes){
if(nodes==null||nodes.size()==0){
return ;
}
level++;
ArrayList<TreeNode> temp = new ArrayList();
for(TreeNode node:nodes){
System.out.println("第"+level+"層:"+node.getNodeName());
if(node.getLeftNode()!=null){
temp.add(node.getLeftNode());
}
if(node.getRightNode()!=null){
temp.add(node.getRightNode());
}
}
nodes.removeAll(nodes);
findNodeByLevel(temp);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode();
root.setNodeName("root");
TreeNode node1 = new TreeNode();
node1.setNodeName("node1");

TreeNode node3 = new TreeNode();
node3.setNodeName("node3");

TreeNode node7 = new TreeNode();
node7.setNodeName("node7");
TreeNode node8 = new TreeNode();
node8.setNodeName("node8");

TreeNode node4 = new TreeNode();
node4.setNodeName("node4");

TreeNode node2 = new TreeNode();
node2.setNodeName("node2");

TreeNode node5 = new TreeNode();
node5.setNodeName("node5");
TreeNode node6 = new TreeNode();
node6.setNodeName("node6");

root.setLeftNode(node1);

node1.setLeftNode(node3);

node3.setLeftNode(node7);
node3.setRightNode(node8);

node1.setRightNode(node4);

root.setRightNode(node2);

node2.setLeftNode(node5);
node2.setRightNode(node6);

ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
nodes.add(root);
findNodeByLevel(nodes);

}

}