算法练习(8) - 二叉树递归

含义

二叉树是一种常见的数据结构,由根节点自上而下,通过比较,将数据按照和父节点比较结果大右小左的插入的一种数据结构.

二叉树的一些基本方法手写

// define data structure
public class BinaryTreeNode{
	Integer value;
	BinaryTreeNode left;
	BinaryTreeNode right;
	
	// 插入节点
	public static insertNode(BinaryTreeNode treeNode , Integer value){
	
		if(treeNode.value == null){
			treeNode.value = value;
		}
		if(treeNode.value > value ){
			if(treeNode.left == null){
				BinaryTreeNode node = new BinaryTreeNode();
			}
			insertNode(node,value);
		}
		if(treeNode.value < value ){
			if(treeNode.right == null){
				BinaryTreeNode node = new BinaryTreeNode();
			}
			insertNode(node,value);
		}
	}
	
	// 先序遍历
	public static void foreachpreOrder(BinaryTreeNode tree){
		if(tree != null){
			System.out.println(node.value);
			// do something ...
		}else{
			return;
		}
		foreachpreOrder(tree.left);
		foreachpreOrder(tree.right);
	}
	
	// 求深度
	public static void findPath(BinaryTreeNode tree){
		if(tree == null){
			return 0;
		}
		int leftDepth = findPath(node.left);
		int rightDepth = findPath(node.right);
		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
	}
}


public class Test01{
	public static void main(String args[]){
		BinaryTreeNode binaryTree = new BinaryTreeNode();
		BinaryTreeNode.insertNode(binaryTree, 6);
		BinaryTreeNode.insertNode(binaryTree, 4);
		BinaryTreeNode.insertNode(binaryTree, 5);
		BinaryTreeNode.insertNode(binaryTree, 1);
		BinaryTreeNode.insertNode(binaryTree, 3);
		BinaryTreeNode.insertNode(binaryTree, 7);
		// 先序遍历
		BinaryTreeNode.foreachpreOrder(binaryTree);
		// 求深度
		BinaryTreeNode.findPath(binaryTree);
		
	}
}