树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上叶朝下的。
树具有以下特点:
树形结构中,子树之间不能有交集,否则就不是树形结构
树有很多表示方式,如:双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等,
最常见的是孩子兄弟表示法。
- class Node{
- int value;//树中存储的数据
- Node firstChild;//第一个孩子的引用
- Node nextBrother;//下一个兄弟引用
- }
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵别称为左子树和右子树的二叉树组成。
二叉树不存在度大于2的结点
二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
二叉树的存储结构分为:顺序存储和类似于链表的链式存储
- class TreeNode {
- public char val;
- public TreeNode left;//左孩子的引用
- public TreeNode right;//右孩子的引用
-
- public TreeNode(char val) {
- this.val = val;
- }
- }
- public void preOrder(TreeNode root) {
- if(root == null) {
- return;
- }
- System.out.print(root.val+" ");
- //递归遍历左子树
- preOrder(root.left);
- //递归遍历右子树
- preOrder(root.right);
- }
- public void inOrder(TreeNode root) {
- if(root == null) {
- return;
- }
- inOrder(root.left);
- System.out.print(root.val+" ");
- inOrder(root.right);
- }
- public void postOrder(TreeNode root) {
- if(root == null) {
- return;
- }
- postOrder(root.left);
- postOrder(root.right);
- System.out.print(root.val+" ");
- }
- public void levelOrder(TreeNode root) {
- Queue
queue = new LinkedList<>(); - if(root == null) {
- return;
- }
- queue.offer(root);
- while (!queue.isEmpty()) {
- TreeNode cur = queue.poll();
- System.out.print(cur.val+" ");
- if(cur.left != null) {
- queue.offer(cur.left);
- }
- if(cur.right != null) {
- queue.offer(cur.right);
- }
- }
- System.out.println();
- }