一丶利用二叉树前序顺序构建二叉树
"#" 代表空结点
/**
*
* A
*
* B C
*
* D E # F
*
* # # # # # #
*
*
* A B D## E## C # F ## 利用前序遍历快速反向创建二叉树
*/
public void createBinaryTreePre(ArrayList<String> data) {
createBinaryTree(data);
}
private Node createBinaryTree(ArrayList<String> data) {
if (0 == data.size()) {
return null;
}
String d = data.get(0);
if ("#".equals(d)) {
data.remove(0);
return null;
}
Node node = new Node(0, d);
data.remove(0);
if (null == root) {
root = node;
}
node.leftChild = createBinaryTree(data);
node.rightChild = createBinaryTree(data);
return node;
}
二丶递归实现二叉树前中后序遍历
/**
* 递归方式实现前序遍历
*/
public void recursionPrerEgodic(Node node) {
if (null == node) {
return;
}
// 先输出根节点
System.out.println("数据：" + node.data);
// 输出左边节点 根节点左边的可以看成是一个子树，递归调用此方法即可
recursionPrerEgodic(node.leftChild);
// 输出右边节点
recursionPrerEgodic(node.rightChild);
}
/**
* 递归方式实现中序遍历
*/
public void recursionMidEgodic(Node node) {
if (null == node) {
return;
}
// 先递归输出左边的节点
recursionMidEgodic(node.leftChild);
// 先输出根节点
System.out.println("数据：" + node.data);
// 最后输出右边节点
recursionMidEgodic(node.rightChild);
}
/**
* 递归方式实现后序遍历
*/
public void recursionPostEgodic(Node node) {
if (null == node) {
return;
}
// 先递归输出左边的节点
recursionPostEgodic(node.leftChild);
// 最后输出右边节点
recursionPostEgodic(node.rightChild);
// 先输出根节点
System.out.println("数据：" + node.data);
}
三丶循环实现二叉树前中后序遍历
/**
* 循环方式实现前序遍历 借助栈实现
*/
public void loopPreEgodic(Node node) {
if (null == node) {
return;
}
// 借用栈实现
Stack<Node> stack = new Stack<Node>();
stack.push(node);
while (!stack.isEmpty()) {
// 从栈中取出数据。
node = stack.pop();
// 取出数据
System.out.println("数据：" + node.data);
// 因为是跟 左 右 而栈是先进后出，所以一定要先把右边压入栈中 再压入左面，
// 如果此节点左右节点不为null，将此节点的左右节点压入栈中
if (null != node.rightChild) {
stack.push(node.rightChild);
}
if (null != node.leftChild) {
stack.push(node.leftChild);
}
}
}
/**
* 循环方式实现中序遍历 借用栈实现
*/
public void loopMidEgodic(Node node) {
if (null == node) {
return;
}
// 借用栈实现
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || null != node) {
// 先遍历出所有左节点放入栈中,停止条件是node指针为null
if (null != node) {
stack.push(node);
// node指针指向左节点
node = node.leftChild;
} else {
// 此时取出栈中的数据
node = stack.pop();
System.out.println("数据：" + node.data);
node = node.rightChild;
}
}
}
/**
* 循环方式实现后序遍历方法一 借用双栈实现
*/
public void loopPostEgodic_1(Node node) {
if (null == node) {
return;
}
// 借用双栈实现
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(node);
while (!s1.isEmpty()) {
node = s1.pop();
// 先不输出，先将根节点压入栈2，最后输出
s2.push(node);
// 注意 以下代码顺序不能换
// 放入栈1后 左在栈底 右 在栈顶，放入栈2后，左在栈顶，右在栈底 ，而根节点早就放在栈2底部了，
if (null != node.leftChild) {
s1.push(node.leftChild);
}
if (null != node.rightChild) {
s1.push(node.rightChild);
}
}
while (!s2.isEmpty()) {
node = s2.pop();
System.out.println("数据:" + node.data);
}
}
/**
* 循环方式实现后序遍历方法二
*/
public void loopPostEgodic_2(Node node) {
if (null == node) {
return;
}
Stack<Node> stack = new Stack<Node>();
stack.push(node);
Node pre = null;
while (!stack.isEmpty()) {
pre = stack.peek();// 注意只取出不移除
if (pre.leftChild != null && node != pre.leftChild && node != pre.rightChild) {
stack.push(pre.leftChild);
}
else if (pre.rightChild != null && node != pre.rightChild) {
stack.push(pre.rightChild);
}
else {
node = stack.pop();
System.out.println("数据:" + node.data);
node = pre;
}
}
}
四丶完整代码
public class WDBinaryTree {
class Node {
int index;
String data;
Node parent;
Node leftChild;
Node rightChild;
public Node(int index, String data) {
super();
this.data = data;
this.index = index;
this.parent = null;
this.leftChild = null;
this.rightChild = null;
}
}
Node root = null;
/**
*
* A
*
* B C
*
* D E # F
*
* # # # # # #
*
*
* A B D## E## C # F ## 利用前序遍历快速反向创建二叉树
*/
public void createBinaryTreePre(ArrayList<String> data) {
createBinaryTree(data);
}
private Node createBinaryTree(ArrayList<String> data) {
if (0 == data.size()) {
return null;
}
String d = data.get(0);
if ("#".equals(d)) {
data.remove(0);
return null;
}
Node node = new Node(0, d);
data.remove(0);
if (null == root) {
root = node;
}
node.leftChild = createBinaryTree(data);
node.rightChild = createBinaryTree(data);
return node;
}
/**
* 获取二叉树的高度
*/
public int getHeight(Node node) {
if (null == node) {
return 0;
}
int i = getHeight(node.leftChild);
int j = getHeight(node.rightChild);
return i > j ? (i + 1) : (j + 1);
}
/**
* 获取二叉树的节点数
*/
public int getNum(Node node) {
if (null == node) {
return 0;
}
return 1 + getNum(node.leftChild) + getNum(node.rightChild);
}
/**
* 递归方式实现前序遍历
*/
public void recursionPrerEgodic(Node node) {
if (null == node) {
return;
}
// 先输出根节点
System.out.println("数据：" + node.data);
// 输出左边节点 根节点左边的可以看成是一个子树，递归调用此方法即可
recursionPrerEgodic(node.leftChild);
// 输出右边节点
recursionPrerEgodic(node.rightChild);
}
/**
* 递归方式实现中序遍历
*/
public void recursionMidEgodic(Node node) {
if (null == node) {
return;
}
// 先递归输出左边的节点
recursionMidEgodic(node.leftChild);
// 先输出根节点
System.out.println("数据：" + node.data);
// 最后输出右边节点
recursionMidEgodic(node.rightChild);
}
/**
* 递归方式实现后序遍历
*/
public void recursionPostEgodic(Node node) {
if (null == node) {
return;
}
// 先递归输出左边的节点
recursionPostEgodic(node.leftChild);
// 最后输出右边节点
recursionPostEgodic(node.rightChild);
// 先输出根节点
System.out.println("数据：" + node.data);
}
/**
* 循环方式实现前序遍历 借助栈实现
*/
public void loopPreEgodic(Node node) {
if (null == node) {
return;
}
// 借用栈实现
Stack<Node> stack = new Stack<Node>();
stack.push(node);
while (!stack.isEmpty()) {
// 从栈中取出数据。
node = stack.pop();
// 取出数据
System.out.println("数据：" + node.data);
// 因为是跟 左 右 而栈是先进后出，所以一定要先把右边压入栈中 再压入左面，
// 如果此节点左右节点不为null，将此节点的左右节点压入栈中
if (null != node.rightChild) {
stack.push(node.rightChild);
}
if (null != node.leftChild) {
stack.push(node.leftChild);
}
}
}
/**
* 循环方式实现中序遍历 借用栈实现
*/
public void loopMidEgodic(Node node) {
if (null == node) {
return;
}
// 借用栈实现
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || null != node) {
// 先遍历出所有左节点放入栈中,停止条件是node指针为null
if (null != node) {
stack.push(node);
// node指针指向左节点
node = node.leftChild;
} else {
// 此时取出栈中的数据
node = stack.pop();
System.out.println("数据：" + node.data);
node = node.rightChild;
}
}
}
/**
* 循环方式实现后序遍历方法一 借用双栈实现
*/
public void loopPostEgodic_1(Node node) {
if (null == node) {
return;
}
// 借用双栈实现
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(node);
while (!s1.isEmpty()) {
node = s1.pop();
// 先不输出，先将根节点压入栈2，最后输出
s2.push(node);
// 注意 以下代码顺序不能换
// 放入栈1后 左在栈底 右 在栈顶，放入栈2后，左在栈顶，右在栈底 ，而根节点早就放在栈2底部了，
if (null != node.leftChild) {
s1.push(node.leftChild);
}
if (null != node.rightChild) {
s1.push(node.rightChild);
}
}
while (!s2.isEmpty()) {
node = s2.pop();
System.out.println("数据:" + node.data);
}
}
/**
* 循环方式实现后序遍历方法二
*/
public void loopPostEgodic_2(Node node) {
if (null == node) {
return;
}
Stack<Node> stack = new Stack<Node>();
stack.push(node);
Node pre = null;
while (!stack.isEmpty()) {
pre = stack.peek();// 注意只取出不移除
if (pre.leftChild != null && node != pre.leftChild && node != pre.rightChild) {
stack.push(pre.leftChild);
}
else if (pre.rightChild != null && node != pre.rightChild) {
stack.push(pre.rightChild);
}
else {
node = stack.pop();
System.out.println("数据:" + node.data);
node = pre;
}
}
}
/**
* 层序 利用队列实现
*/
public void levelEgodic(Node node) {
if (null == node) {
return;
}
Queue<Node> q = new LinkedList<Node>();
q.add(node);
while (!q.isEmpty()) {
//源码： Retrieves and removes the head of this queue,
node = q.poll();// 取出并移除
System.out.println("数据：" + node.data);
if (null != node.leftChild) {
q.add(node.leftChild);
}
if (null != node.rightChild) {
q.add(node.rightChild);
}
}
}
public static void main(String[] args) {
//二叉树的前序遍历顺序，#代表空结点
String[] data = { "A", "B", "D", "#", "#", "E", "#", "#", "C", "#", "F", "#", "#" };
ArrayList<String> dataList = new ArrayList<String>();
for (String s : data) {
dataList.add(s);
}
//构造二叉树
WDBinaryTree tree = new WDBinaryTree();
tree.createBinaryTreePre(dataList);
int i = tree.getHeight(tree.root);
int num = tree.getNum(tree.root);
System.out.println("二叉树的高度为：" + i);
System.out.println("二叉树的节点数为：" + num);
System.out.println("递归实现--");
System.out.println("前序:");
tree.recursionPrerEgodic(tree.root);
System.out.println("中序:");
tree.recursionMidEgodic(tree.root);
System.out.println("后序:");
tree.recursionPostEgodic(tree.root);
// 递归调用一个方法，相当于将数据加入一个栈中，先进后出
System.out.println("循环实现--");
System.out.println("前序:");
tree.loopPreEgodic(tree.root);
System.out.println("中序:");
tree.loopMidEgodic(tree.root);
System.out.println("后序1:");
tree.loopPostEgodic_1(tree.root);
System.out.println("后序2:");
tree.loopPostEgodic_2(tree.root);
System.out.println("层序:");
tree.levelEgodic(tree.root);
}
}
五丶测试结果
图片.png
图片.png
网友评论