数据结构之什么是树？

数据结构之什么是树？

文章目录

• 什么是树？
• 什么是二叉树？
• 二叉树的实现
• • 链式存储结构
  • • 实现代码
  • 数组
• 二叉查找树
• 二叉树的遍历
• • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历
• 最后

什么是树？

数据结构中的树和现实生活中的树虽然不是同一种事物，但是却有着相同的特点。

数据结构中的树，其实就是一种和现实生活中的树有着相似结构的数据逻辑结构，从同一个“根”衍生出许多“枝干”，最后衍生出更多的“叶子”。

树的定义：

树是n（你>=0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。
1、有且仅有一个特定的称为根的节点。
2、当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

         7/   10    8/    /  4   1  3   6

• 根节点：树的最上面的那个节点，被称为根节点，所有非空树有且只有一个根节点。在上图中，元素7为根节点。

• 叶子节点：树的末端，没有“孩子”节点的节点被称作叶子节点。在上图中，元素4、1、3、6为叶子节点。

• 子树：树的非根节点，以及它的孩子节点，组成的树结构被称为子树。在上图中，由元素10、4、1组成的树结构为整棵树的子树。

• 树的高度：树的最大层级数，被称为树的高度或深度。在上图中，树的高度为3。

• 父节点：一个节点的上一层级的节点被称为当前节点的父节点。根节点没有父节点。在上图中，节点10是节点4、1的父节点。

• 孩子节点：一个节点的下一层级的节点被称为当前节点的孩子节点。叶子节点没有孩子节点。在上图中，节点10是节点7的孩子节点。

• 兄弟节点：一个节点同一层级的节点被称为当前节点的兄弟节点。所有节点都有n（n>=0）个兄弟节点。在上图中，节点8是节点10的兄弟节点。

什么是二叉树？

二叉树（binary tree）是数的一种特殊形式。二叉，顾名思义，这种数的每个节点最多有2个孩子节点。

注意：这里是最多有2两个，可能只有1个节点，或者没有孩子节点。

二叉树节点的两个孩子节点，一个被称为左孩子（lift child），一个被称为右孩子（right child）。这两个孩子节点的顺序是固定的，不能够颠倒或者混淆。

二叉树有两种特殊形式，分别叫做满二叉树和完全二叉树。

什么是满二叉树？

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就叫做满二叉树。

      满二叉树7/   10    8/    /  4   1  3   6

什么是完全二叉树？

对于一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树的所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

      完全二叉树7/   10    8/    /4   1  3

二叉树的实现

二叉树的实现方法一般有两种，分别为：

• 链式存储结构
• 数组

链式存储结构

链式存储结构实现二叉树，每个二叉树的节点拥有存储数据的data变量，同时有着指向左右孩子节点的指针变量，这样就可以简单实现二叉树的数据结构了。

实现代码

public class BinaryTree {/*** 二叉树根节点指针*/private TreeNode root;/*** 获取二叉树的根节点** @return 二叉树的根节点*/public TreeNode root() {;}/*** 通过数组创建二叉树时数组的索引位置*/private int createBinaryTreeByArrIndex = 0;/*** 通过数组创建二叉树的构造方法** @param arr 数组*/public BinaryTree(Integer[] arr) {// 通过数组构建二叉树，并保存二叉树根节点的指针 = createBinaryTree(arr);}/*** 创建二叉树的方法** @param arr 数组* @return root根节点指针*/public TreeNode createBinaryTree(Integer[] arr) {TreeNode node = null;// 如果数组为空，或者索引越界，则直接返回空的二叉树if (arr == null || arr.length == 0 || createBinaryTreeByArrIndex < 0|| createBinaryTreeByArrIndex > arr.length - 1) {return null;}// 通过索引获取数组对应位置的数据Integer data = arr[createBinaryTreeByArrIndex++];if (data != null) {// 如果这个数据不为空，则创建节点，并返回node = new TreeNode(data);// 数组的下一个节点为该节点的左孩子节点node.leftChild = createBinaryTree(arr);// 数组的下一个节点为该节点的右孩子节点node.rightChile = createBinaryTree(arr);}return node;}/*** 二叉树节点*/class TreeNode {/*** 二叉树节点存储节点数据的变量*/private Integer data;/*** 二叉树节点左孩子节点指针*/private TreeNode leftChild;/*** 二叉树节点右孩子节点指针*/private TreeNode rightChile;/*** 获取节点数据的方法** @return 节点数据*/public Integer data() {return this.data;}/*** 获取节点左孩子节点指针的方法** @return 节点左孩子节点指针*/public TreeNode leftChild() {return this.leftChild;}/*** 获取节点右孩子节点指针的方法** @return 节点右孩子节点指针*/public TreeNode rightChile() {return this.rightChile;}/*** 节点构造方法** @param data 节点数据*/TreeNode(Integer data) {this.data = data;}}
}

数组

使用数组存储时，会按照层级顺序把二叉树的节点放入数组中对应的位置上去。如果某一个节点的左孩子或者右孩子缺失，则数组对应的位置也会空出来。

其中二叉树的根节点存储在数组的第一位，即下标为0的位置。

如果一个二叉树的父节点下标为parent，则该节点的左孩子节点的下标即为2*parent+1，该节点的右孩子节点的下标为2*parent+2。

同理而言，一个左孩子节点的下标为leftChild，则该左孩子节点的父节点为(leftChile-1)/2。

如果一个右孩子节点的下标为rightChild，则该右孩子节点的父节点为(rightChild-1)/2。

二叉查找树

什么是二叉查找树？

二叉查找树是一种特殊的二叉树，这种树的主要作用是进行查找操作的。

• 如果左子树不为空，则左子树上的所有节点的值均小于根节点的值。

• 如果右子树不为空，则右子树上的所有节点的值均大于根节点的值。

• 左右子树也都是二叉查找树。

二叉树的遍历

二叉树的遍历，从节点之间的位置关系角度来看，二叉树的遍历分为4种：

• 前序遍历
• 中序遍历
• 后续遍历
• 层序遍历

如果从宏观的角度来看，二叉树的遍历归结为两大类：

• 深度优先遍历（前序遍历，中序遍历，后续遍历）

• 广度优先遍历（层序遍历）

前序遍历

二叉树的前序遍历，输出顺序为根节点、左子树、右子树。

         3/   2     8/       9   10     4

上述的二叉树中，前序遍历的输出循序为：3、2、9、10、8、4。

public static void main(String[] args) {Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};// 构建二叉树BinaryTree binaryTree = new BinaryTree(arr);// 获取二叉树的根节点BinaryTree.TreeNode root = ();System.out.println("前序遍历：");// 前序遍历preOrderTraveral(root);System.out.println();preOrderTraveralWithStack(root);
}/*** 前序遍历** @param node 节点*/
public void preOrderTraveral(BinaryTree.TreeNode node) {if (node == null) {return;}System.out.print(node.data() + "t");preOrderTraveral(node.leftChild());preOrderTraveral(node.rightChile());
}/*** 前序遍历，非递归** @param root 二叉树根节点*/
public void preOrderTraveralWithStack(BinaryTree.TreeNode root) {Stack<BinaryTree.TreeNode> stack = new Stack<>();BinaryTree.TreeNode treeNode = root;while (treeNode != null || !stack.isEmpty()) {while (treeNode != null) {System.out.print(treeNode.data() + "t");stack.push(treeNode);treeNode = treeNode.leftChild();}if (!stack.isEmpty()) {treeNode = stack.pop();treeNode = treeNode.rightChile();}}
}

中序遍历

二叉树的中序遍历，输出顺序为左子树、根节点、右子树。

         3/   2     8/       9   10     4

上述的二叉树中，中序遍历的输出循序为：9、2、10、3、8、4。

public static void main(String[] args) {Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};// 构建二叉树BinaryTree binaryTree = new BinaryTree(arr);// 获取二叉树的根节点BinaryTree.TreeNode root = ();System.out.println("中序遍历：");// 中序遍历inOrderTraveral(root);System.out.println();inOrderTraveralWithStack(root);
}/*** 中序遍历** @param node 节点*/
public void inOrderTraveral(BinaryTree.TreeNode node) {if (node == null) {return;}inOrderTraveral(node.leftChild());System.out.print(node.data() + "t");inOrderTraveral(node.rightChile());
}/*** 中序遍历，非递归** @param root 二叉树根节点*/
public void inOrderTraveralWithStack(BinaryTree.TreeNode root) {Stack<BinaryTree.TreeNode> stack = new Stack<>();BinaryTree.TreeNode treeNode = root;while (treeNode != null || !stack.isEmpty()) {while (treeNode != null) {stack.push(treeNode);treeNode = treeNode.leftChild();}if (!stack.isEmpty()) {treeNode = stack.pop();System.out.print(treeNode.data() + "t");treeNode = treeNode.rightChile();}}
}

后序遍历

二叉树的后序遍历，输出顺序为左子树、右子树、根节点。

         3/   2     8/       9   10     4

上述的二叉树中，后序遍历的输出循序为：9、10、2、4、8、3。

public static void main(String[] args) {Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};// 构建二叉树BinaryTree binaryTree = new BinaryTree(arr);// 获取二叉树的根节点BinaryTree.TreeNode root = ();System.out.println("后序遍历：");// 后序遍历postOrderTraveral(root);System.out.println();postOrderTraveralWithStack(root);
}/*** 后序遍历** @param node 节点*/
public void postOrderTraveral(BinaryTree.TreeNode node) {if (node == null) {return;}postOrderTraveral(node.leftChild());postOrderTraveral(node.rightChile());System.out.print(node.data() + "t");
}/*** 后序遍历，非递归** @param root 二叉树根节点*/
public void postOrderTraveralWithStack(BinaryTree.TreeNode root) {Stack<BinaryTree.TreeNode> stack = new Stack<>();List<Integer> list = new ArrayList<>();BinaryTree.TreeNode treeNode = root;while (treeNode != null || !stack.isEmpty()) {while (treeNode != null) {list.add(treeNode.data());stack.push(treeNode);treeNode = treeNode.rightChile();}if (!stack.isEmpty()) {treeNode = stack.pop();treeNode = treeNode.leftChild();}}for (int i = list.size() - 1; i >= 0; i--) {System.out.(i) + "t");}
}

层序遍历

二叉树的层序遍历，输出顺序按照一层一层往下输出，所以也叫作广度优先遍历。

         3/   2     8/       9   10     4

上述的二叉树中，层序遍历的输出循序为：3、2、8、9、10、4。

public static void main(String[] args) {Integer[] arr = new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4};// 构建二叉树BinaryTree binaryTree = new BinaryTree(arr);// 获取二叉树的根节点BinaryTree.TreeNode root = ();System.out.println("层序遍历：");// 层序遍历levelOrderTraveralWithQueue(root);
}/*** 层序遍历** @param root 二叉树根节点*/
public void levelOrderTraveralWithQueue(BinaryTree.TreeNode root) {Queue<BinaryTree.TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {BinaryTree.TreeNode node = queue.poll();System.out.print(node.data() + "t");BinaryTree.TreeNode leftChild = node.leftChild();if (leftChild != null) {queue.offer(leftChild);}BinaryTree.TreeNode rightChile = node.rightChile();if (rightChile != null) {queue.offer(rightChile);}}
}

最后

本文Github 已收录，欢迎Star。