数据结构：二叉树构建与遍历（Java实现）

悠悠 2022-10-02 15:58 130阅读 0赞

如下所示，是一个二叉树，从根节点开始，每个节点最多有两个子节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

树是一种常见的数据结构，而二叉树又是一种特殊的树结构，这里介绍二叉树特点：

*  每个节点最多有两个子节点
 *  节点的左子节点中的数据小于节点中的数据
 *  节点的右子节点中的数据大于节点中的数据

这里给出一个由Java实现的二叉树：

package com.xxx.algorithm.tree;
    public class BST {
    	Node root = null;
    	public void insert(int data){
    		Node node = new Node(data);
    		if(root==null){
    			root = node;
    		}else{
    			Node curNode = root;
    			Node parent = null;
    			while(true){
    				parent = curNode;
    				if(data<curNode.data){
    					curNode = curNode.left;
    					if(curNode==null){
    						parent.left = node;
    						break;
    					}
    				}else{
    					curNode = curNode.right;
    					if(curNode==null){
    						parent.right = node;
    						break;
    					}
    				}
    			}
    		}	
    	}
    	
    	public void inOrder(Node node){
    		if(node!=null){
    			inOrder(node.left);
    			show(node);
    			inOrder(node.right);
    		}
    	}
    	
    	public void preOrder(Node node){
    		if(node!=null){
    			show(node);
    			preOrder(node.left);
    			preOrder(node.right);
    		}
    	}
    	
    	public void postOrder(Node node){
    		if(node!=null){
    			postOrder(node.left);
    			postOrder(node.right);
    			show(node);
    		}
    	}
    	
    	public void show(Node node){
    		System.out.print(node.data+" ");
    	}
    	
    	public static void main(String[] args) {
    		BST tree = new BST();
    		tree.insert(20);
    		tree.insert(10);
    		tree.insert(50);
    		tree.insert(18);
    		tree.insert(13);
    		tree.insert(7);
    		tree.insert(6);
    		tree.insert(8);
    		tree.insert(19);
    		tree.insert(55);
    		tree.insert(23);
    		tree.insert(21);
    		tree.insert(75);
    		tree.insert(52);
    		tree.insert(40);
    		System.out.println("preOrder:");
    		tree.preOrder(tree.root);
    		System.out.println();
    		System.out.println("inOrder:");
    		tree.inOrder(tree.root);	
    		System.out.println();
    		System.out.println("postOrder:");
    		tree.postOrder(tree.root);
    	}
    	
    	class Node{
    		int data;
    		Node left;
    		Node right;
    		public Node(int data){
    			this.data = data;
    			this.left = null;
    			this.right = null;
    		}
    	}
    }

这段代码通过insert(int data)方法成功构建了文章开始看到的二叉树。最终通过三种遍历方式，看到遍历结果如下：

![2019062200420757.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: /images/20220109/4f2d92e4a30a4641affd01d0118f00e8.png
[2019062200420757.png]: /images/20220109/f66b50dc8fc745a6868e43ee1eb12a86.png