二叉树是树的一种，由一个根节点和两棵互不相交左右子树的二叉树组成。
二叉树有很多性质，就不一一举例了~
先来说一下最简单的关于二叉树常用的3种遍历方式。层序遍历就略过了~
前序遍历：根节点，左节点，右节点。
结果就是：ABDGHCEIF
前序遍历
中序遍历：左节点，根节点，右节点。
结果就是：GDHBAEICF
中序遍历
后序遍历：左节点，右节点，根节点。
结果就是：GHDBIEFCA
后序遍历
概念就说到这里，开始敲代码~
首先，建立数节点。
public class TreeNode {
private int index;
private String data; //数据域
private TreeNode leftChild; //左子树
private TreeNode rightChild; //右子树
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeNodeString(String data) {
this.data = data;
}
public TreeNode(int index, String data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}
然后我们来构建一个二叉树：
/**
* 构建二叉树
* A
* B C
* D E F
* G H I
*/
public void createBinaryTree() {
//我们需要一个根节点
root = new TreeNode(1, "A");
TreeNode treeNodeB = new TreeNode(2, "B");
TreeNode treeNodeC = new TreeNode(3, "C");
TreeNode treeNodeD = new TreeNode(4, "D");
TreeNode treeNodeE = new TreeNode(5, "E");
TreeNode treeNodeF = new TreeNode(6, "F");
TreeNode treeNodeG = new TreeNode(7, "G");
TreeNode treeNodeH = new TreeNode(8, "H");
TreeNode treeNodeI = new TreeNode(9, "I");
//分别对应节点的左右子树。
root.leftChild = treeNodeB;
root.rightChild = treeNodeC;
treeNodeB.leftChild = treeNodeD;
treeNodeD.leftChild = treeNodeG;
treeNodeD.rightChild = treeNodeH;
treeNodeC.leftChild = treeNodeE;
treeNodeC.rightChild = treeNodeF;
treeNodeE.rightChild = treeNodeI;
}
二叉树建立完成之后，
开始遍历，首先使用循环的方式进行前序遍历，循环需要借助栈来实现遍历。
/**
* 前序遍历 非递归
* @param treeNode
*/
public void nonRecOrder(TreeNode treeNode){
if(treeNode == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
//首先把根节点放入栈中
stack.push(treeNode);
while (!stack.isEmpty()){
//弹出根结点
TreeNode node = stack.pop();
System.out.println("data:" + node.data);
//如果有右子结点，则压入节点
if(node.rightChild!=null){
//如果左节点有值，则右节点在栈底，最后才会输出
stack.push(node.rightChild);
}
//如果有右左结点，则压入节点
if(node.leftChild!=null){
//下次循环把左子节点当根节点继续弹出
stack.push(node.leftChild);
}
}
}
接着来介绍使用递归的方式进行遍历
/**
* 前序遍历 递归
* @param treeNode
*/
public void preOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//首先把每个节点当成根节点输出
System.out.println("data:" + treeNode.data);
//如果左节点有值，则输出左节点
preOrder(treeNode.leftChild);
///如果右节点有值，输出右节点。
preOrder(treeNode.rightChild);
}
}
/**
* 中序遍历 递归
* @param treeNode
*/
public void midOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//递归左子树，直到左节点为null，return。
midOrder(treeNode.leftChild);
//输出节点。
System.out.println("data:" + treeNode.data);
//递归右子树
midOrder(treeNode.rightChild);
}
}
/**
* 后序遍历 递归
* @param treeNode
*/
public void postOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//递归左子树，直到左节点为null，return。
postOrder(treeNode.leftChild);
//递归右子树，直到左节点为null，return。
postOrder(treeNode.rightChild);
//输出节点
System.out.println("data:" + treeNode.data);
}
}
二叉树的遍历理解了还是比较简单的，下面来看一下二叉树的重建。
已知 前序遍历结果 ：ABDGHCEIF 中序遍历结果：GDHBAEICF，求二叉树。
根据前序遍历的特性，可以知道A是根节点，这种在中序中可以得出 A节点左边的就是左节点，右边的就是右节点。这个规律可以使用递归
整个二叉树的
左子树的
下面就来看看重建二叉树的递归代码，具体的在代码中都有注释
/**
* 已知前序和中序
* @param pre 前序集合
* @param startPre 前序集合起始点
* @param endPre 前序集合总长度
* @param in 中序集合
* @param startIn 中序集合起始点
* @param endIn 中序集合总长度
* @return
*/
public TreeNode resetBinaryTreeString(String[] pre ,int startPre,int endPre,String[] in,int startIn,int endIn){
//如果开始大于结束，就说明这个树已经结束了
if(startPre > endPre || startIn > endIn) {
return null;
}
//把前序的头节点放入树中当根节点
TreeNode node = new TreeNode(pre[startPre]);
//遍历中序的所有节点
for (int i = startIn; i <= endIn; i++) {
//找到根节点在中序中的位置
if(pre[startPre] == in[i]){
node.leftChild = resetBinaryTreeString(
pre, //前序集合
startPre + 1, //前序左子树起始点： startPre + 1
startPre + (i - startIn),//左子树长度：i是root节点在中序遍历的位置,
// (i - startIn)是中序遍历中左子树的长度，
// 所以左子树的总长度：前序的 startPre + 中序遍历中左子树的长度
in, //中序集合
startIn, //中序左子树的起始点：startIn
i - 1); //中序左子树的总长度：i -1
node.rightChild = resetBinaryTreeString(
pre, //前序集合
startPre + (i - startIn) + 1,//前序右子树起始点： 前序左子树的长度+1 , {startPre + (i - startIn)} + 1
endPre, //前序右子树总长度： 前序的总长度
in, //中序集合
i + 1, //中序右子树的起始点：i+1
endIn); //中序右子树总长度： 中序的总长度
break;
}
}
return node;
}
这些是最近看二叉树的一些收获~简单的分享一下。
下面贴上全部代码：
public class BinaryTree {
private TreeNode root;
public BinaryTree() {
root = new TreeNode(1, "A");
}
/**
* 构建二叉树
* A
* B C
* D E F
* G H I
*/
public void createBinaryTree() {
root = new TreeNode(1, "A");
TreeNode treeNodeB = new TreeNode(2, "B");
TreeNode treeNodeC = new TreeNode(3, "C");
TreeNode treeNodeD = new TreeNode(4, "D");
TreeNode treeNodeE = new TreeNode(5, "E");
TreeNode treeNodeF = new TreeNode(6, "F");
TreeNode treeNodeG = new TreeNode(7, "G");
TreeNode treeNodeH = new TreeNode(8, "H");
TreeNode treeNodeI = new TreeNode(9, "I");
root.leftChild = treeNodeB;
root.rightChild = treeNodeC;
treeNodeB.leftChild = treeNodeD;
treeNodeD.leftChild = treeNodeG;
treeNodeD.rightChild = treeNodeH;
treeNodeC.leftChild = treeNodeE;
treeNodeC.rightChild = treeNodeF;
treeNodeE.rightChild = treeNodeI;
}
/**
* 前序遍历 递归
* @param treeNode
*/
public void preOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
//首先输出根节点。
System.out.println("data:" + treeNode.data);
//不断的调用自身函数，把左节点输出。
preOrder(treeNode.leftChild);
//根节点和左节点输出完成，输出右节点。
preOrder(treeNode.rightChild);
}
}
/**
* 中序遍历 递归
* @param treeNode
*/
public void midOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
midOrder(treeNode.leftChild);
System.out.println("data:" + treeNode.data);
midOrder(treeNode.rightChild);
}
}
/**
* 后序遍历 递归
* @param treeNode
*/
public void postOrder(TreeNode treeNode){
if(treeNode == null){
return;
}else{
postOrder(treeNode.leftChild);
postOrder(treeNode.rightChild);
System.out.println("data:" + treeNode.data);
}
}
/**
* 前序遍历 非递归
* @param treeNode
*/
public void nonRecOrder(TreeNode treeNode){
if(treeNode == null){
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(treeNode);
while (!stack.isEmpty()){
//弹出根结点
TreeNode node = stack.pop();
System.out.println("data:" + node.data);
//如果有右子结点，则压入节点
if(node.rightChild!=null){
//如果左节点有值，则右节点在栈底，最后才会输出
stack.push(node.rightChild);
}
//如果有右左结点，则压入节点
if(node.leftChild!=null){
//下次循环把左子节点当根节点继续弹出
stack.push(node.leftChild);
}
}
}
/**
* 已知前序和中序
* @param pre 前序集合
* @param startPre 前序集合起始点
* @param endPre 前序集合总长度
* @param in 中序集合
* @param startIn 中序集合起始点
* @param endIn 中序集合总长度
* @return
*/
public TreeNode resetBinaryTreeString(String[] pre ,int startPre,int endPre,String[] in,int startIn,int endIn){
//如果开始大于结束，就说明这个树已经结束了
if(startPre > endPre || startIn > endIn) {
return null;
}
//把前序的头节点放入树中当根节点
TreeNode node = new TreeNode(pre[startPre]);
//遍历中序的所有节点
for (int i = startIn; i <= endIn; i++) {
//找到根节点在中序中的位置
if(pre[startIn] == in[i]){
node.leftChild = resetBinaryTreeString(
pre, //前序集合
startPre + 1, //前序左子树起始点： startPre + 1
startPre + (i - startIn),//左子树长度：i是root节点在中序遍历的位置,
// (i - startIn)是中序遍历中左子树的长度，
// 所以左子树的总长度：前序的 startPre + 中序遍历中左子树的长度
in, //中序集合
startIn, //中序左子树的起始点：startIn
i - 1); //中序左子树的总长度：i -1
node.rightChild = resetBinaryTreeString(
pre, //前序集合
startPre + (i - startIn) + 1,//前序右子树起始点： 前序左子树的长度+1 , {startPre + (i - startIn)} + 1
endPre, //前序右子树总长度： 前序的总长度
in, //中序集合
i + 1, //中序右子树的起始点：i+1
endIn); //中序右子树总长度： 中序的总长度
break;
}
}
return node;
}
public static void main(String[] args){
BinaryTree binaryTree= new BinaryTree();
binaryTree.createBinaryTree();
System.out.println("非递归前序");
binaryTree.nonRecOrder(binaryTree.root);
System.out.println("递归前序");
binaryTree.preOrder(binaryTree.root);
System.out.println("递归中序");
binaryTree.midOrder(binaryTree.root);
System.out.println("递归后序");
binaryTree.postOrder(binaryTree.root);
String[] pre = {"A","B","D","G","H","C","E","I","F"};
String[] mid = {"G","D","H","B","A","E","I","C","F"};
TreeNode root = binaryTree.resetBinaryTreeString(pre, 0, pre.length - 1, mid, 0, mid.length - 1);
System.out.println("重建二叉树前序");
binaryTree.preOrder(root);
}
public class TreeNode {
/**
*
*/
private int index;
/**
* 数据域
*/
private String data;
/**
* 左子树
*/
private TreeNode leftChild;
/**
* 右子树
*/
private TreeNode rightChild;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public TreeNode(int index, String data) {
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public TreeNode(String data) {
this.data = data;
}
}
}
