数据结构：二叉树(BinaryTree)原理及其java实现

1、如何定义一个二叉树

通过递归的方式定义二叉树：不能直接定义二叉树，只能定义二叉树结点。节点类的属性包括当前节点的值、左子节点、右子节点（子节点的类型也是二叉树结点类）、构造函数，代码如下：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

3、二叉树的遍历：

三种遍历顺序的区别主要是看根节点的位置深度遍历（DFS）有三种策略：前序遍历、中序遍历、后序遍历

1、前序遍历：根节点-左节点-右节点

// 打印前序遍历 void dfs(TreeNode root) { if(root == null) return; //递归结束条件 System.out.println(root.val); // 根：此位置写其他操作代码 dfs(root.left); // 左 dfs(root.right); // 右 }

2、中序遍历 ：左节点-根节点-右节点

// 打印中序遍历 void dfs(TreeNode root) { if(root == null) return; //递归结束条件 dfs(root.left); // 左 System.out.println(root.val); // 根：此位置写其他操作代码 dfs(root.right); // 右 } // 中序遍历的倒序 void dfs(TreeNode root) { if(root == null) return; //递归结束条件 dfs(root.right); // 右 System.out.println(root.val); // 根：此位置写其他操作代码 dfs(root.left); // 左 }

3、后序遍历 ：左节点-右节点-根节点

// 打印中序遍历 void dfs(TreeNode root) { if(root == null) return; //递归结束条件 dfs(root.left); // 左 dfs(root.right); // 右 System.out.println(root.val); // 根：此位置写其他操作代码 }

3、二叉搜索树（二叉排序树）

根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。

中序搜索二叉树形成的列表是排序列表

参考文章

用Python生成二叉树

【数据结构】理解二叉树的三种遍历--前序、中序、后序 +层序（简明易懂）