用java实现二叉树的遍历算法

ゞ浴缸里的玫瑰 2022-05-21 20:50 130阅读 0赞

用java实现二叉树的遍历算法，编写二叉树类BinaryTree，代码如下：  
package package2;  
public class BinaryTree \{

int data; //根节点数据  
BinaryTree left; //左子树  
BinaryTree right; //右子树

public BinaryTree(int data) //实例化二叉树类  
\{  
this.data = data;  
left = null;  
right = null;  
\}

public void insert(BinaryTree root,int data)\{ //向二叉树中插入子节点  
if(data>root.data) //二叉树的左节点都比根节点小  
\{  
if(root.right==null)\{  
root.right = new BinaryTree(data);  
\}else\{  
this.insert(root.right, data);  
\}  
\}else\{ //二叉树的右节点都比根节点大  
if(root.left==null)\{  
root.left = new BinaryTree(data);  
\}else\{  
this.insert(root.left, data);  
\}  
\}  
\}  
\}  
当建立好二叉树类后可以创建二叉树实例，并实现二叉树的先根遍历，中根遍历，后根遍历，代码如下：  
package package2;  
public class BinaryTreePreorder \{

public static void preOrder(BinaryTree root)\{ //先根遍历  
if(root!=null)\{  
System.out.print(root.data+”-“);  
preOrder(root.left);  
preOrder(root.right);  
\}  
\}

public static void inOrder(BinaryTree root)\{ //中根遍历

if(root!=null)\{  
inOrder(root.left);  
System.out.print(root.data+”–”);  
inOrder(root.right);  
\}  
\}

public static void postOrder(BinaryTree root)\{ //后根遍历

if(root!=null)\{  
postOrder(root.left);  
postOrder(root.right);  
System.out.print(root.data+”—”);  
\}  
\}  
public static void main(String\[\] str)\{  
int\[\] array = \{12,76,35,22,16,48,90,46,9,40\};  
BinaryTree root = new BinaryTree(array\[0\]); //创建二叉树  
for(int i=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);

当运行上面的程序后结果如下：  
先根遍历：  
12-9-76-35-22-16-48-46-40-90-  
中根遍历：  
9–12–16–22–35–40–46–48–76–90–  
后根遍历：  
9—16—22—40—46—48—35—90—76—12—