欢迎移步博主CSDN：CSDN博客
数据结构之树与二叉树的学习（一）
简介
本文主要对数据结构中的树与二叉树进行学习，之前我们学习了数据的线性结构(线性表),但数据之间不只有这种简单的一对一关系，更多时候是一对多，甚至多对多的结构，而树结构作为一种比线性结构更复杂的数据结构，比较适合于描述具有层次关系的数据，即数据间的一对多关系。
树
定义
树中常常将数据元素称之为结点，树是n个结点的集合。当n=0时，称为空树；任意一颗非空树都满足一下几个条件:
- 有且仅有一个特定的称为根的结点
- 当n>1时，除根结点之外的其余结点被分为m个互不相交的有限集合，其中每一个集合又是一棵树
基本术语
- 结点的度与树的度
- 叶子结点与分支结点
- 孩子结点、双亲结点、兄弟结点
- 路径、路径长度
- 祖先、子孙
- 结点的层数、树的深度(高度)
- 层序编号
- 有序树、无序树
- 森林
二叉树
定义
二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和2棵互不相交的、分别称为根节点的左子树和柚子乎上的二叉树构成。
二叉树的特点
- 每个结点最多有2棵子树
- 二叉树是有序的，次序不能颠倒
基本术语
- 斜树
- 满二叉树
- 完全二叉树
二叉树的遍历
简介
二叉树的存储可以采用顺序存储和连接存储两种方式，相应的代码实现也有些许区别，不过其思想都是一致的，下面我们针对链接存储结构来实现二叉树的几种遍历方式。
二叉树的构造及其基本操作：
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;
}
}
构架二叉树函数代码实现：
- 此处采用迭代左子树实现，创建的是一棵左斜树
//创建二叉树
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;
}前序遍历
输出顺序：根节点、左子树、右子树
递归代码实现：
//前序遍历 递归实现
private void preOrder(TreeNode<T> node){
if (node != null){
System.out.println(node.data);
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}非递归代码实现：
//前序遍历 非递归
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){
if (node != null){
inOrder(node.leftChild);
System.out.println(node.data);
inOrder(node.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){
if (node != null){
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.println(node.data);
}
}非递归代码实现：
//后序遍历 非递归
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;
}
}
}层序遍历
按照从根节点到叶子节点的层次关系进行遍历，属于广度优先遍历。
非递归代码实现：
//层序遍历 非递归实现
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遍历接口：
package com.dataStructure;
public interface BiTreeOrder {
//前序遍历
public void PreOrder();
//中序遍历
public void InOrder();
//后序遍历
public void PostOrder();
//层序遍历
public void LerverOrder();
}ReBiTree递归实现类：
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非递归实现类：
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节点类：
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主函数:
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]. 电子工业出版社.
