二叉树的实现及先序、中序、后序遍历 - JAVA

定义
二叉树：在数据结构中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作为

“左子树”和右子树。二叉树通常被用于实现二叉查找树和二叉堆。

特点
二叉树的每个节点至多只有两颗子树（不存在度大于2的结点），需要注意的是二叉树的子树

是有左右之分的，次序不能颠倒。其第i层最多有个结点；深度为k的二叉树最多有

个结点；对于任意一颗二叉树T，如果其叶子结点树为n0,度为2的结点树为n2，则n0=n2 + 2(根结

点除外)。

存储表示
二叉树可以使用数组或者顺序表来表示，这种实现方式更有利于紧凑的存储和更好的访问

局部性，但是他需要连续的存储空间，在极端的情况下，如果一颗二叉树只有右子树，那么空

间的浪费将会异常的严重。

二叉树还可以使用链表的存储方式来实现，这也是推荐的实现方式。在Java中具体的树节点

的具体表示情况如下：

[java]
class TreeNode {
private T data;
private TreeNode leftNode;
private TreeNode rightNode;

public TreeNode(T data, TreeNode leftNode, TreeNode rightNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}

class TreeNode {
private T data;
private TreeNode leftNode;
private TreeNode rightNode;

public TreeNode(T data, TreeNode leftNode, TreeNode rightNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
对于二叉树的具体操作笔者不会去详细的实现，感兴趣的是二叉树的遍历方式。

二叉树的遍历
对于二叉树的遍历方式一般分为三种先序、中序、后序三种方式

先序遍历
若二叉树为空，则不进行任何操作：否则

1、访问根结点。

2、先序方式遍历左子树。

3、先序遍历右子树。

中序遍历

若二叉树为空，则不进行任何操作：否则

1、中序遍历左子树。
2、访问根结点。

3、中序遍历右子树。

后序遍历

若二叉树为空，则不进行任何操作：否则

1、后序遍历左子树。
2、后序遍历右子树。

3、放问根结点。

遍历的情况如下：

二叉树遍历的代码实现：

[java]
package com.kiritor;

/**
* Java二叉树的实现以及遍历
*
* @author Kiritor
*/
public class BinaryTree {

/**
* 输出结点信息*/
public void printNode(TreeNode node)
{
System.out.print(node.getData()+" ");
}
/**
* 定义结点
* */
class TreeNode {
private T data;
private TreeNode leftNode;
private TreeNode rightNode;

public TreeNode(T data, TreeNode leftNode, TreeNode rightNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public TreeNode getLeftNode() {
return leftNode;
}

public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}

public TreeNode getRightNode() {
return rightNode;
}

public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}

}

// 初始化二叉树
public TreeNode init() {
TreeNode D = new TreeNode("D", null, null);
TreeNode H = new TreeNode("H", null, null);
TreeNode I = new TreeNode("I", null, null);
TreeNode J = new TreeNode("J", null, null);
TreeNode P = new TreeNode("P", null, null);
TreeNode G = new TreeNode("G", P, null);

二叉树的实现及先序、中序、后序遍历 (一)