树和二叉树的区别：
- 树中节点的子节点个数没有限制，而二叉树的节点最多为两个
- 树中的节点无左右之分，而二叉树有左右之分
完全二叉树：
若设二叉树的高度为h，除第h层外，其他各层（1~h-1）的节点数都达到最大个数，第h层有叶子节点，并且叶子节点都是从左到右一次排布
满二叉树：
除了叶子节点外每一个节点都要左右子节点，并且叶子节点都处在最底层的二叉树
二叉树的遍历
- 先序遍历(根节点-左孩子-右孩子)
- 中序遍历(左孩子-根节点-右孩子)
- 后序遍历(左孩子-右孩子-根节点)
二叉树.jpg
图示遍历结果：
先序遍历：A-B-D-G-C-E-F
中序遍历：D-G-B-A-E-C-F
后续遍历：G-D-B-E-F-C-A
如图的树，在用代码实现是可定义为String expression = "A(B(D(,G)),C(E,F))"
- 遇到字母，将要创建节点
- 遇到"("，创建左孩子节点
- 遇到","，创建右孩子节点
- 遇到")"，返回到上一层节点
接下来按照上面的思路分析，手撸链表式的二叉树，并且每步有详细的注释。先给展示链式结构二叉树图片。
链式结构二叉树.jpg
- 自定义节点类
// 自定义节点类
public class Node {
private char data; // 存放的元素
private Node leftChild; // 左孩子节点
private Node rightChild; // 右孩子节点
public Node(char data, Node leftChild, Node rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
public String toString() {
return " " + getData();
}
}
- 链表式的二叉树代码实现
public static Node CreateTree(String expression) {
Node node[] = new Node[40]; // 用Node数组临时保存根节点位置
Node head = null, temp = null; //head记录头节点位置，temp是碰到字母时临时生成的节点
int childTag = 0; // 定义一个孩子节点的标记，判断为坐还是右
int height = -1; // 记录根节点在数组中的位置，便于设置其左右孩子节点
char[] exps = expression.toCharArray(); // 将传进来的字符串分割为字符数组
for (int i = 0; i < exps.length; i++) {
char data = exps[i];
switch (data) {
case '(': // 准备创建左孩子节点，并且把"("之前的节点保存到数组中
height++; //位置自增
node[height] = temp; //将"("之前的那个节点保存到数组中
childTag = 1; //准备创建左孩子节点
break;
case ',':
childTag = 2; // 准备创建右孩子节点
break;
case ')': // 返回上一级节点
height--; //位置自减，定位到根节点数组中的上一个位置
break;
default:
temp = new Node(data, null, null);// 碰到字母，直接创建相应节点
if (head == null) {
head = temp;
} else {
switch (childTag) {
case 1:
node[height].setLeftChild(temp);
break;
case 2:
node[height].setRightChild(temp);
break;
}
}
}
}
return head;
}
为了更加便于理解，我将此代码分析的跟Debug模式下的调试结果一样的步骤图给展示一下，便于思路分析。
详细分析.jpg
超级详细的步骤，一步一步的。。。。简直把自己当做计算机来用。手写这么多，等下下面点个赞呗~~~
二叉树的遍历
- 递归方式的遍历
// 先序遍历
public static void PreOrder(Node node) {
if (node == null) {
return;
} else {
System.out.print(node.getData() + " ");
PreOrder(node.getLeftChild());
PreOrder(node.getRightChild());
}
}
// 中序遍历
public static void InOrder(Node node) {
if (node == null) {
return;
} else {
InOrder(node.getLeftChild());
System.out.print(node.getData() + " ");
InOrder(node.getRightChild());
}
}
// 后序遍历
public static void PostOrder(Node node) {
if (node == null) {
return;
} else {
PostOrder(node.getLeftChild());
PostOrder(node.getRightChild());
System.out.print(node.getData() + " ");
}
}
- 非递归方式的遍历
先序遍历
采用栈先进后出的特点，可以将最顶上的节点入栈，然后出栈打印，将其右节点和左节点分别入栈，经过循环取，先出的左节点打印，然后是右节点就可以实现
// 非递归先序遍历
public static void preOrderStack(Node node) {
Stack<Node> stack = new Stack<Node>(); // 创建一个栈
if (node == null) {
return;
}
stack.push(node); // 将顶节点给先入栈
while (!stack.isEmpty()) {
Node temp = stack.pop(); // 节点出栈
System.out.print(temp.getData() + " "); // 打印
if (temp.getRightChild() != null) {
stack.push(temp.getRightChild()); // 右节点不为空就进栈
}
if (temp.getLeftChild() != null) {
stack.push(temp.getLeftChild()); // 左节点不为空就进栈
}
}
}
中序遍历
同样用栈，先从顶部根节点开始，把下面所有的左子节点进行入栈，入完之后，出栈，如果那个节点是叶子节点，没有右节点，则不会进入里层循环，继续出栈，有右节点就会去处理右节点。
// 非递归中序遍历
public static void InOrderStack(Node node) {
Stack<Node> stack = new Stack<Node>();
if (node == null) {
return;
}
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeftChild(); // 通过循环，把从顶部节点到最底下的所有左节点全部入栈
}
node = stack.pop();
System.out.print(node.getData() + " "); // 顶部节点下的左节点入栈后开始往外出，并打印
node = node.getRightChild(); // 开始转到右节点进行处理
}
}
后序遍历
先从左子节点开始入栈，处理完左边节点后，分析右边节点，进行入栈，然后又是重新从此根节点进行搜索，pop栈进行打印，通过回溯去遍历，可以通过自己打断点进一步理解。
// 非递归后序遍历
public static void postOrderStack(Node node) {
Stack<Node> stack = new Stack<Node>();
Map<Node, Boolean> map = new HashMap<Node, Boolean>(); //存放已经被遍历过的节点
if (node == null) {
return;
}
stack.push(node);
while (!stack.isEmpty()) {
Node temp = stack.peek();
if (temp.getLeftChild() != null && !map.containsKey(temp.getLeftChild())) { //map中没有存放才能继续
temp = temp.getLeftChild();
while (temp != null) {
if (map.containsKey(temp)) {
break;
} else {
stack.push(temp);
}
temp = temp.getLeftChild();
} //处理左边孩子节点，从顶部根节点开始，全部入栈
continue;
}
if (temp.getRightChild() != null && !map.containsKey(temp.getRightChild())) {
stack.push(temp.getRightChild()); //将当前节点的右孩子节点入栈
continue;
}
Node t = stack.pop();
map.put(t, true); //经过遍历处理的存放到Map中去
System.out.print(t.getData() + " ");
}
}
