关键词：
定义
一个有穷的结点集合，可以为空。若不为空，则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。
- 二叉树的五种基本形态：
- 二叉树的子树是有顺序之分的，称为左子树和右子树
- 几种特殊的二叉树
- 斜二叉树
- 完美二叉树（满二叉树）
- 完全二叉树
有n个结点的二叉树，对树中结点按从上之下，从左至右的顺序进行编号，编号为i(1<=1<=n)结点与满二叉树中编号为i结点在二叉树中位置相同
二叉树的几个重要性质：
- 在二叉树的第i层上最多有2 i-1 个节点 。（i>=1）
- 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
- 对任何非空二叉树T，若n0表示度数为0的节点 n2表示度数为2的节点,那么n0=n2+1;
- 具有n个结点的完全二叉树的深度为 log2 n + 1
这里在补充一下树的其他一些性质和概念：
- 结点的度：结点所拥有的子树的个数称为结点的度；
- 树的度：树中各节点的度的最大值；因此，二叉树的度最大为2；
- 结点的层数：规定根节点的层数为1，其余结点的层数为他的双亲结点层数加1
- 输的深度：树中所有结点的最大层数。
二叉树的抽象数据类型(ADT)
对于二叉树的元素，主要的操作包括：
1. 判别二叉树是否为空
2. 遍历二叉树，按特定的顺序访问每个结点
- 前序遍历：根节点–>左子树–>右子树
- 中序遍历：左子树–>根节点–>右子树
- 后序遍历：左子树–>右子树–>根节点
- 层序遍历：从上至下，从左至右。
3. 创建一个二叉树
二叉树的存储结构
顺序存储结构
使用顺序存储结构，对完全二叉树这种结构是非常合适的。可以按照从上之下，从左至右顺序存储n个结点的完全二叉树的结点父子关系。
完全二叉树的这种存储结构，有以下特点
- 非根节点（序号i>1)的父节点序号（数组下标）是 i/2 (取整）。
- 结点（序号为i）的左孩子结点的序号是2*i,如果2*i>n,则没有左孩子；
- 结点（序号为i）的右孩子结点的序号是2*i+1,如果2*i+1>n,则没有右孩子。
一般普通的二叉树，在其空余位置补充控制，当做是完全二叉树，采用数组结构存储，将导致存储空间的浪费。
链式存储结构
二叉树的链式存储结构中，每一个结点包含三个关键属性:指向左子树的指针，数据域，指向右子树的指针；根据这个叙述，我们可以按如下结构定义结点。
结点定义
/**
* Created by engineer on 2017/10/23.
* <p>
* 二叉树结点定义
*/
public class TreeNode<T>
// 数据域
private T data;
// 左子树
private TreeNode<T> leftChild;
// 右子树
private TreeNode<T> rightChild;
public TreeNode(T data)
this(null, data, null);
public TreeNode(TreeNode<T> leftChild, T data, TreeNode<T> rightChild)
this.leftChild = leftChild;
this.data = data;
this.rightChild = rightChild;
public T getData()
return data;
public TreeNode<T> getLeftChild()
return leftChild;
public TreeNode<T> getRightChild()
return rightChild;
二叉树初始化
我们就以下图为例，构造一颗二叉树。
/**
* 构建二叉树
*
* @return 树根
*/
TreeNode CreateTree()
TreeNode<String> nodeH = new TreeNode<>("H");
TreeNode<String> nodeG = new TreeNode<>("G");
TreeNode<String> nodeF = new TreeNode<>(nodeH, "F", null);
TreeNode<String> nodeE = new TreeNode<>(nodeG, "E", null);
TreeNode<String> nodeD = new TreeNode<>("D");
TreeNode<String> nodeC = new TreeNode<>(null, "C", nodeF);
TreeNode<String> nodeB = new TreeNode<>(nodeD, "B", nodeE);
TreeNode<String> nodeA = new TreeNode<>(nodeB, "A", nodeC);
return nodeA;
这样，我们就按上图所示构建了一颗二叉树，返回二叉树的根结点。
二叉树的遍历
二叉树的遍历是二叉树最要的操作，也是二叉树的核心。从二叉树的定义我们可以得知，二叉树是一种递归形式的数据结构，根结点下的左右子树又分别是二叉树；因此这使得二叉树的遍历离不开递归这种思想。
很显然，对于二叉树的三种遍历，我们就可以借助其自身的特性，通过递归实现。
- 二叉树的递归遍历实现
/**
* 访问每个结点
*
* @param node
*/
private void visitNode(TreeNode node)
System.out.print(node.getData().toString());
System.out.print(" ");
/**
* 前序遍历-递归实现
*
* @param node
*/
void preTraversal(TreeNode node)
if (node != null)
visitNode(node);
preTraversal(node.getLeftChild());
preTraversal(node.getRightChild());
/**
* 中序遍历-递归实现
*
* @param node
*/
void traversal(TreeNode node)
if (node != null)
traversal(node.getLeftChild());
visitNode(node);
traversal(node.getRightChild());
/**
* 后序遍历-递归实现
* @param node
*/
void postTraversal(TreeNode node)
if (node != null)
postTraversal(node.getLeftChild());
postTraversal(node.getRightChild());
visitNode(node);
可以看到，使用递归实现二叉树的遍历十分简单，但我们也可以考虑使用非递归的形式，使用栈。
严格来说，使用栈实现二叉树的遍历，其实还是递归思想，只不过是我们自己用栈完成了递归实现中系统帮我们完成的工作。
本质上来说，二叉树这种递归的数据结构，他的遍历是离不开递归思想的，只不过看我们怎么去理解递归的实现了。
- 二叉树的非递归实现
/**
* 前序遍历-迭代实现
* @param node
*/
void preTraversalIteration(TreeNode node)
// 创建一个栈
Stack<TreeNode> mStack = new Stack<>();
while (true)
while (node != null) // 非叶子结点的子树
// 前序遍历，先访问根结点
visitNode(node);
// 将当前结点压入栈
mStack.push(node);
// 对左子树继续进行前序遍历
node=node.getLeftChild();
if (mStack.isEmpty())
//所有元素已遍历完成
break;
// 弹出栈顶结点
node=mStack.pop();
// 右子树前序遍历
node=node.getRightChild();
/**
* 中序遍历-迭代实现
* @param node
*/
void TraversalIteration(TreeNode node)
// 创建一个栈
Stack<TreeNode> mStack = new Stack<>();
while (true)
while (node != null) // 非叶子结点的子树
// 将当前结点压入栈
mStack.push(node);
// 对左子树继续进行中序遍历
node=node.getLeftChild();
if (mStack.isEmpty())
//所有元素已遍历完成
break;
// 弹出栈顶结点
node=mStack.pop();
// 中序遍历，访问根结点
visitNode(node);
// 右子树中序遍历
node=node.getRightChild();
/**
* 后序遍历-迭代实现
* @param node
*/
void postTraversalIteration(TreeNode node)
// 创建一个栈
Stack<TreeNode> mStack = new Stack<>();
while (true)
if (node != null)
//当前结点非空，压入栈
mStack.push(node);
// 左子树继续遍历
node=node.getLeftChild();
else
// 左子树为空
if(mStack.isEmpty())
return;
if (mStack.lastElement().getRightChild() == null)
// 栈顶元素右子树为空，则当前结点为叶子结点，输出
node=mStack.pop();
visitNode(node);
while (node == mStack.lastElement().getRightChild())
visitNode(mStack.lastElement());
node=mStack.pop();
if (mStack.isEmpty())
break;
if (!mStack.isEmpty())
node=mStack.lastElement().getRightChild();
else
node=null;
可以看到，虽说是非递归实现，但本质上还是依靠栈先进后出的特性，实现了递归访问每个结点的操作，无非就是在前、中、后三种顺序下，访问结点的时机不同而已。这里，前序和中序遍历的实现其实很容易理解，后续遍历的实现很考究对栈的使用理解。
- 层序遍历
最后，再来说一说层序遍历。顾名思义，层序遍历就是从上到下按层，从左至右依次访问每个结点。这种遍历非常用规律，就是从根节点下一层开始，优先访问每一层所有的双亲结点，然后依次访问每个结点的左右儿子。也就是说，从上到下，先遇见到结点先访问，后遇到的结点后访问，这典型的就是队列的思想，因此我们可以使用队列实现二叉树的层序遍历。
/**
* 层序遍历
* @param node
*/
void levelTraversal(TreeNode node)
//创建队列
Queue<TreeNode> mNodeQueue = new LinkedList<>();
// 根结点加入队列
mNodeQueue.add(node);
TreeNode temp;
while (!mNodeQueue.isEmpty())
//元素出队列
temp=mNodeQueue.poll();
//输出
visitNode(temp);
if (temp.getLeftChild() != null)
// 左子树入队列
mNodeQueue.add(temp.getLeftChild());
if (temp.getRightChild() != null)
//右子树入队列
mNodeQueue.add(temp.getRightChild());
测试二叉树的实现
最后，用一个测试类测试一下我们对二叉树的实现。
/**
* Created by engineer on 2017/10/24.
*/
public class BinaryTreeTest
public static void main(String[] args)
BinaryTree mBinaryTree = new BinaryTree();
TreeNode root = mBinaryTree.CreateTree();
System.out.print("前序遍历-递归实现:");
mBinaryTree.preTraversal(root);
System.out.print("\\n中序遍历-递归实现:");
mBinaryTree.traversal(root);
System.out.print("\\n后序遍历-递归实现:");
mBinaryTree.postTraversal(root);
System.out.println();
System.out.print("\\n前序遍历-迭代实现:");
mBinaryTree.preTraversalIteration(root);
System.out.print("\\n中序遍历-迭代实现:");
mBinaryTree.TraversalIteration(root);
System.out.print("\\n后序遍历-迭代实现:");
mBinaryTree.postTraversalIteration(root);
System.out.println();
System.out.print("\\n层序遍历:");
mBinaryTree.levelTraversal(root);
得到输出：
前序遍历-递归实现:A B D E G C F H
中序遍历-递归实现:D B G E A C H F
后序遍历-递归实现:D G E B H F C A
前序遍历-迭代实现:A B D E G C F H
中序遍历-迭代实现:D B G E A C H F
后序遍历-迭代实现:D G E B H F C A
层序遍历:A B C D E F G H 嗯，和预期想象的一致。
好了，二叉树的存储结构和遍历就到这里了。
树的存储结构；树与二叉树的转换；树和森林的遍历算法
文章目录树的存储结构树、森林与二叉树的转换树和森林的遍历树的存储结构树、森林与二叉树的转换树和森林的遍历 查看详情
java数据结构与算法之顺序存储二叉树
顺序存储二叉树顺序存储二叉树的概念从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组要求:1)右图的二叉树的结点，要求以数组的方式来存放arr:[1,2,3,4,5,6,6]2)要求在遍历... 查看详情
数据结构(13)---二叉树之链式结构(前序遍历,中序遍历,后序遍历,层序遍历)
二叉树之链式结构文章目录二叉树之链式结构前言二叉树链式结构的创建二叉树的遍历二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的层序遍历计算二叉树中节点的个数计算叶子节点的个数第k层节点个数查找某... 查看详情
树二叉树存储结构二叉数遍历&数据结构基本概念和术语(代码片段)
文章目录树、二叉树、存储结构、二叉数遍历&数据结构基本概念和术语数据结构基本概念和术语第四章树的基本概念二叉树的基本概念什么是二叉树二叉树的基本/特殊状态二叉树的存储结构链式存储结构顺序结构存储二叉树... 查看详情
王道数据结构与算法树(八——1)(代码片段)
✍、目录脑图树[第一部分]✍、目录脑图1、树1.1、树的基本概念1.2、结点之间的关系描述1.3、有序树、无序树、森林1.4、树的常考性质2、二叉树2.1、满二叉树2.2、完全二叉树2.3、二叉排序树2.4、平衡二叉树2.5、总结3、二叉树的... 查看详情
二叉树的遍历
一、二叉树的遍历：1、前序遍历：根左右2、中序遍历：左根右3、后序遍历：左右根4、层次遍历：一层一层的遍历，类似广度优先二、二叉树的存储结构 二叉树以二叉链表结构存储，也就是1个数据域，两个指针域（分别指... 查看详情
java集合与数据结构二叉树(代码片段)
Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情
java集合与数据结构二叉树(代码片段)
Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情
基本数据结构-二叉树
摘要 书中第10章10.4小节介绍了有根树，简单介绍了二叉树和分支数目无限制的有根树的存储结构，而没有关于二叉树的遍历过程。为此对二叉树做个简单的总结，介绍一下二叉树基本概念、性质、二叉树的存储结构和遍历过... 查看详情
二叉树（非递归）四种遍历(代码片段)
...#34;>红</font>黑树树的概念与结构树是一种非线性的数据结构，它是由n（ 查看详情
二叉树的存储结构及四种遍历(c语言)(代码片段)
二叉树的存储结构:typedefstructTNode*Position;typedefPositionBinTree;/*二叉树类型*/structTNode/*树结点定义*/ElementTypeData;/*结点数据*/BinTreeLeft;/*指向左子树*/BinTreeRight;/*指向右子树*/;二叉树的四种遍历:voidInorderTraversal(BinTreeBT) 查看详情
java集合与数据结构——二叉树02
文章目录Java集合与数据结构——二叉树(二)初阶面试题二叉树的前中后遍历前序遍历中序遍历后序遍历获取二叉树的高度获取二叉树的最大深度求整颗二叉树的叶子节点数量遍历思路：子问题思路：查找二叉树中对应val... 查看详情
.数据结构与算法基础(代码片段)
目录第六章.数据结构与算法基础（重点）第一节.数组与矩阵数组稀疏矩阵第二节.数据结构的定义第三节.线性表链表详解顺序存储与链式存储对比队列与栈第四节.广义表第五节.树与二叉树树的概念二叉树的分类二叉树... 查看详情
重拾数据结构
从现在开始决定整理下“数据结构和算法的相关知识”，以下为复习成果： 1.数组、单链表和双链表 2.栈 3.队列 4.树与二叉树（上）{二叉树的创建与递归遍历} 树与二叉树（中）{二叉树的非递归遍历与... 查看详情
树（二叉树）的建立和遍历算法（前序，中序，后序）
最近学习树的概念，有关二叉树的实现算法记录下来。。。 不过学习之前要了解的预备知识：树的概念；二叉树的存储结构；二叉树的遍历方法。。 二叉树的存储结构主要了解二叉链表结构，也就是一... 查看详情
二叉树-遍历和存储结构
在《二叉树的定义和性质》中我们已经认识了二叉树这种数据结构。我们知道链表的每个节点可以有一个后继，而二叉树（BinaryTree）的每个节点可以有两个后继。比如这样定义二叉树的节点：typedefstructnode*link;structnode unsigned... 查看详情
数据结构学习笔记——广义表树和二叉树的基本知识(代码片段)
目录一、广义表二、树和森林三、二叉树（一）概念（二）性质1、二叉树的性质2、满二叉树的性质3、完全二叉树的性质四、平衡二叉树五、二叉树的存储结构（一）二叉树的顺序存储结构（二）... 查看详情
数据结构学习笔记——树的存储结构以及树森林与二叉树之间的转换(代码片段)
目录一、树的存储结构（一）双亲表示法（二）孩子链表表示法（三）孩子兄弟表示法二、树、森林与二叉树的转换（一）树转换成二叉树（二）二叉树还原成树（三）森林转换成二... 查看详情