欢迎移步博主CSDN：[CSDN博客](https://blog.csdn.net/weixin_42327790/article/details/102884267) # 数据结构之树与二叉树的学习（一） ## 简介 本文主要对数据结构中的树与二叉树进行学习，之前我们学习了数据的线性结构(线性表),但数据之间不只有这种简单的一对一关系，更多时候是一对多，甚至多对多的结构，而树结构作为一种比线性结构更复杂的数据结构，比较适合于描述具有层次关系的数据，即数据间的一对多关系。 --- ## 树 ### 定义 树中常常将数据元素称之为`结点`，树是n个结点的集合。当n=0时，称为空树；任意一颗非空树都满足一下几个条件: * 有且仅有一个特定的称为根的结点 * 当n>1时，除根结点之外的其余结点被分为m个互不相交的有限集合，其中每一个集合又是一棵树 ### 基本术语 * 结点的度与树的度 * 叶子结点与分支结点 * 孩子结点、双亲结点、兄弟结点 * 路径、路径长度 * 祖先、子孙 * 结点的层数、树的深度(高度) * 层序编号 * 有序树、无序树 * 森林 --- ## 二叉树 ### 定义 二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和2棵互不相交的、分别称为根节点的左子树和柚子乎上的二叉树构成。 ### 二叉树的特点 * 每个结点最多有2棵子树 * 二叉树是有序的，次序不能颠倒 ### 基本术语 * 斜树 * 满二叉树 * 完全二叉树 ### 二叉树的遍历 #### 简介 二叉树的存储可以采用顺序存储和连接存储两种方式，相应的代码实现也有些许区别，不过其思想都是一致的，下面我们针对链接存储结构来实现二叉树的几种遍历方式。 **二叉树的构造及其基本操作：** ```java package com.dataStructure; /** * author zbl * * datetime 2019.11.266666 * */ //结点类 public class TreeNode<T> { //指向下一个结点 public TreeNode leftChild; public TreeNode rightChild; public T data; TreeNode(T data){ this.data = data; } } ``` 构架二叉树函数代码实现： * 此处采用迭代左子树实现，创建的是一棵左斜树 ```java //创建二叉树 private TreeNode creatBiTree(LinkedList<T> inputList){ TreeNode<T> tmp = null; //判空 if(inputList == null || inputList.isEmpty()){ return null; } //存数 T data = inputList.removeFirst(); if(data != null){ tmp = new TreeNode(data); tmp.leftChild = this.creatBiTree(inputList); tmp.rightChild = this.creatBiTree(inputList); } //返回根结点 return tmp; } ``` --- #### 前序遍历 输出顺序：根节点、左子树、右子树 递归代码实现： ```java //前序遍历 递归实现 private void preOrder(TreeNode<T> node){ if (node != null){ System.out.println(node.data); preOrder(node.leftChild); preOrder(node.rightChild); } } ``` 非递归代码实现： ```java //前序遍历 非递归 private void preOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ System.out.println(tmp.data); stack.push(tmp); tmp = tmp.leftChild; } //如果节点没有左孩子，则弹出栈顶，访问节点右孩子 if(!stack.isEmpty()){ tmp = stack.pop(); tmp = tmp.rightChild; } } } ``` #### 中序遍历 输出顺序：左子树、根节点、右子树 递归代码实现： ```java //中序遍历 递归实现 private void inOrder(TreeNode<T> node){ if (node != null){ inOrder(node.leftChild); System.out.println(node.data); inOrder(node.rightChild); } } ``` 非递归代码实现： ```java //中序遍历 非递归 private void inOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; //当节点不为空，且栈不为空 while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } //访问叶子节点 System.out.println(tmp.data); //栈非空，说明还未遍历完 if(!stack.isEmpty()){ //父节点出栈 tmp = stack.pop(); //访问父节点 System.out.println(tmp.data); //访问右子树 tmp = tmp.rightChild; } } } ``` #### 后序遍历 输出顺序：左子树、右子树、根节点 递归代码实现： ```java //后序遍历 递归实现 private void postOrder(TreeNode<T> node){ if (node != null){ postOrder(node.leftChild); postOrder(node.rightChild); System.out.println(node.data); } } ``` 非递归代码实现： ```java //后序遍历 非递归 private void postOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } if(!stack.isEmpty()){ tmp = stack.pop(); //若为叶子节点，访问 if(tmp.rightChild == null) System.out.println(tmp.data); tmp = tmp.rightChild; } } } ``` #### 层序遍历 按照从根节点到叶子节点的层次关系进行遍历，属于广度优先遍历。 非递归代码实现： ```java //层序遍历 非递归实现 public void LerverOrder(){ Queue<TreeNode> queue = new LinkedList<TreeNode>(); //根节点入队 queue.offer(node); System.out.println("层序遍历开始"); while(!queue.isEmpty()){ TreeNode<T> tmp = queue.poll(); System.out.println(tmp.data); if(tmp.leftChild != null) queue.offer(tmp.leftChild); if(tmp.rightChild != null) queue.offer(tmp.rightChild); } System.out.println("层序遍历结束"); } ``` ### 完整Java代码 BiTreeOrder遍历接口： ```java package com.dataStructure; public interface BiTreeOrder { //前序遍历 public void PreOrder(); //中序遍历 public void InOrder(); //后序遍历 public void PostOrder(); //层序遍历 public void LerverOrder(); } ``` ReBiTree递归实现类： ```java package com.dataStructure; import sun.reflect.generics.tree.Tree; import java.util.LinkedList; import java.util.Queue; /** * author zbl * * datetime 2019.11.266666 * */ public class ReBiTree<T> implements BiTreeOrder{ //存根结点 protected TreeNode<T> node = null; //构造函数 public ReBiTree(LinkedList<T> inputList){ this.node = this.creatBiTree(inputList); } //空构造函数 public ReBiTree() { } // public void addBiTree() //创建二叉树 private TreeNode creatBiTree(LinkedList<T> inputList){ TreeNode<T> tmp = null; //判空 if(inputList == null || inputList.isEmpty()){ return null; } //存数 T data = inputList.removeFirst(); if(data != null){ tmp = new TreeNode(data); tmp.leftChild = this.creatBiTree(inputList); tmp.rightChild = this.creatBiTree(inputList); } //返回根结点 return tmp; } //前序遍历 public void PreOrder(){ System.out.println("前序遍历开始："); preOrder(this.node); System.out.println("前序遍历结束："); } //前序遍历 递归实现 private void preOrder(TreeNode<T> node){ if (node != null){ System.out.println(node.data); preOrder(node.leftChild); preOrder(node.rightChild); } } //中序遍历 public void InOrder(){ System.out.println("中序遍历开始："); inOrder(this.node); System.out.println("中序遍历结束："); } //中序遍历 递归实现 private void inOrder(TreeNode<T> node){ if (node != null){ inOrder(node.leftChild); System.out.println(node.data); inOrder(node.rightChild); } } //后序遍历 public void PostOrder(){ System.out.println("后序遍历开始："); postOrder(this.node); System.out.println("后序遍历结束："); } //后序遍历 递归实现 private void postOrder(TreeNode<T> node){ if (node != null){ postOrder(node.leftChild); postOrder(node.rightChild); System.out.println(node.data); } } //层序遍历 非递归实现 public void LerverOrder(){ Queue<TreeNode> queue = new LinkedList<TreeNode>(); //根节点入队 queue.offer(node); System.out.println("层序遍历开始"); while(!queue.isEmpty()){ TreeNode<T> tmp = queue.poll(); System.out.println(tmp.data); if(tmp.leftChild != null) queue.offer(tmp.leftChild); if(tmp.rightChild != null) queue.offer(tmp.rightChild); } System.out.println("层序遍历结束"); } } ``` NoReBiTree非递归实现类： ```java package com.dataStructure; import sun.reflect.generics.tree.Tree; import java.util.LinkedList; import java.util.Stack; /** * author zbl * * datetime 2019.11.266666 * */ public class NoReBiTree<T> extends ReBiTree{ //构造函数 public NoReBiTree(LinkedList<T> inputList){ super(inputList); } //前序遍历 非递归 private void preOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ System.out.println(tmp.data); stack.push(tmp); tmp = tmp.leftChild; } //如果节点没有左孩子，则弹出栈顶，访问节点右孩子 if(!stack.isEmpty()){ tmp = stack.pop(); tmp = tmp.rightChild; } } } //中序遍历 非递归 private void inOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; //当节点不为空，且栈不为空 while(tmp != null || !stack.isEmpty()){ //迭代访问节点的左孩子，并入栈 while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } //访问叶子节点 System.out.println(tmp.data); //栈非空，说明还未遍历完 if(!stack.isEmpty()){ //父节点出栈 tmp = stack.pop(); //访问父节点 System.out.println(tmp.data); //访问右子树 tmp = tmp.rightChild; } } } //后序遍历 非递归 private void postOrder(TreeNode<T> node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode<T> tmp = this.node; while(tmp != null || !stack.isEmpty()){ while(tmp != null){ stack.push(tmp); tmp = tmp.leftChild; } if(!stack.isEmpty()){ tmp = stack.pop(); //若为叶子节点，访问 if(tmp.rightChild == null) System.out.println(tmp.data); tmp = tmp.rightChild; } } } } ``` TreeNode节点类： ```java package com.dataStructure; /** * author zbl * * datetime 2019.11.266666 * */ //结点类 public class TreeNode<T> { //指向下一个结点 public TreeNode leftChild; public TreeNode rightChild; public T data; TreeNode(T data){ this.data = data; } } ``` Main主函数: ```java package com.dataStructure; import java.util.LinkedList; /** * author zbl * * datetime 2019.11.266666 * */ public class Main { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<Integer>(); //二叉树值 linkedList.add(1); linkedList.add(2); linkedList.add(4); linkedList.add(null);linkedList.add(null); linkedList.add(5); linkedList.add(null);linkedList.add(null); linkedList.add(3); linkedList.add(null);linkedList.add(6); ReBiTree<Integer> noReBiTree = new ReBiTree<Integer>(linkedList); noReBiTree.PreOrder(); noReBiTree.InOrder(); noReBiTree.PostOrder(); noReBiTree.LerverOrder(); } } ``` ## 参考文献 王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社. 魏梦舒(@程序员小灰)著. 漫画算法--小灰的算法之旅 [M]. 电子工业出版社. 最后修改：2020 年 03 月 14 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
