这个世界总是有很多的废物,很不幸，我就是其中一个。但是我不想成为一个废物，所以你得自救！
有好几个月没有写博客了，这段时间一直也算是忙碌但不充实。给自己制定了一些计划，但是到目前为止只完成一个。今天是2020年12月18日，人类的喜怒哀乐大抵都是一样的。又要开始写博客了，但是我好想没有以前的热情了，只有面对现实的无奈与疲惫。
--------------------------------------------------------------------------------------------------------------
实验要求
（1）假设二叉树的结点值是字符，请根据输入的二叉树后根遍历和中根遍历序列来建立二叉链表表示的二叉树，并对其进行某种遍历，输出遍历序列，以验证建立的二叉树是否正确。（2）任意给定一个结点p，输出从二叉树的根结点到结点p的路径。
首先我们要明白如何根据中序遍历和后序遍历，怎么去确定一个树。我这里简单写了一个，首先找到根节点，以确定左子树与右子树，再找到左子树与右子树的根节点，依次递归，即可构建好树。这个地方的重点在于找到根节点在中序遍历的位置，以确定左右子树。
public static int findIndexOfInorder1(String[] inorder, int inbegin, int inend, String val){//找到后序遍历中的结点在中序遍历的下标
int searchnum=-1;
for(int i=inbegin;i<=inend;i++){
// if(inorder[i]==val){两个字符串比较相同用equals，而不用==
if(inorder[i].equals(val)){
// return i;
searchnum=i;
break;
}
}
return searchnum;
}
构建完树后，我们以中序遍历为例来验证树是否构造正确。这部分我是通过递归实现的
public static void InOrder(Node bitree){
if(bitree==null)
return;
else {
InOrder(bitree.left);
System.out.println(bitree.val);
InOrder(bitree.right);
}
}
非递归方式如下（是需要借助一个栈去实现）
public static List<String> inorderTraversal(Node root) {
List<String> list = new ArrayList<>();
//用栈实现
Stack<Node> stack = new Stack<Node>();
Node cur = root;
Node top = null;
while (cur != null || !stack.isEmpty()){
//内层循环将当前数据入栈
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//出栈并将该元素放入到链表中
top = stack.pop();
list.add(top.val);
//将cur指向栈顶元素的右孩子
cur = top.right;
}
return list;
}
任意给定一个结点p，输出从二叉树的根结点到结点p的路径。也是要借助一个栈，然后先序遍历，如果匹配到，直接输出。找不到就把栈顶元素剔除。
public static boolean searchNode(Node root,Stack<Node> s,Node node) {
if(root == null) return false;
s.push(root);
if(root.val.equals(node.val)) return true;
boolean b = false;
//先去左子树找
if(root.left != null) b = searchNode(root.left,s,node);
//左子树找不到并且右子树不为空的情况下才去找
if(!b && root.right != null) b = searchNode(root.right,s,node);
//左右都找不到，弹出栈顶元素
if(!b) s.pop();
return b;
}
整体代码如下
import java.util.*;
public class TreeTest{
private static class Node{
String val;
Node left;
Node right;
public Node(String val) {
this.val = val;
}
}
// 根据一棵树的中序遍历与后序遍历构造二叉树
public static int postIndex=0;//开始的下标，在后面的方法中又重新赋值了，该全局变量赋的值被覆盖
public static Node buildTreeChild1(String[] inorder, String[] postorder, int inbegin, int inend) {
if(inbegin>inend){return null;}//没有结点了
//1. 将后序遍历的根结点[即最后一个元素]作为遍历的开始
Node root=new Node(postorder[postIndex]);
//2. 找到当前根节点在中序遍历当中的位置
int rootIndex=findIndexOfInorder1(inorder,inbegin,inend,postorder[postIndex]);//后序遍历中的结点在中序遍历的下标
postIndex--;
if(rootIndex==-1){
return null;
}
root.right=buildTreeChild1(inorder,postorder,rootIndex+1,inend);//右子树
root.left=buildTreeChild1(inorder,postorder,inbegin,rootIndex-1);//左子树
return root;
}
public static void InOrder(Node bitree){
if(bitree==null)
return;
else {
InOrder(bitree.left);
System.out.println(bitree.val);
InOrder(bitree.right);
}
}
public static List<String> inorderTraversal(Node root) {
List<String> list = new ArrayList<>();
//用栈实现
Stack<Node> stack = new Stack<Node>();
Node cur = root;
Node top = null;
while (cur != null || !stack.isEmpty()){
//内层循环将当前数据入栈
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//出栈并将该元素放入到链表中
top = stack.pop();
list.add(top.val);
//将cur指向栈顶元素的右孩子
cur = top.right;
}
return list;
}
public static boolean searchNode(Node root,Stack<Node> s,Node node) {
if(root == null) return false;
s.push(root);
if(root.val.equals(node.val)) return true;
boolean b = false;
//先去左子树找
if(root.left != null) b = searchNode(root.left,s,node);
//左子树找不到并且右子树不为空的情况下才去找
if(!b && root.right != null) b = searchNode(root.right,s,node);
//左右都找不到，弹出栈顶元素
if(!b) s.pop();
return b;
}
public static int findIndexOfInorder1(String[] inorder, int inbegin, int inend, String val){//找到后序遍历中的结点在中序遍历的下标
int searchnum=-1;
for(int i=inbegin;i<=inend;i++){
// if(inorder[i]==val){两个字符串比较相同用equals，而不用==
if(inorder[i].equals(val)){
// return i;
searchnum=i;
break;
}
}
return searchnum;
}
public static Node buildTree1(String[] inorder, String[] postorder){//构建二叉树
Node root=null;
if(inorder==null||postorder==null){
return null;
}
if(inorder.length<=0||postorder.length<=0){return null;}
postIndex=postorder.length-1;
// System.out.println(postorder.length);
// return buildTreeChild1(inorder,postorder,0,inorder.length-1);
root=buildTreeChild1(inorder,postorder,0,inorder.length-1);
return root;
}
public static void main(String[] args) {
String[] inorder=null;
String[] postorder=null;
Node root=null;
String p=null;
Scanner input=new Scanner(System.in);
System.out.println("输入想要中序和后序：");
inorder=input.nextLine().split(" ");
postorder =input.nextLine().split(" ");
// System.out.println(postorder.length);
root=buildTree1(inorder,postorder);
System.out.println("对构造的树进行中序遍历");
// //非递归实现中序遍历
// List<String> list = null;
// list=inorderTraversal(root);
// System.out.println(list);
InOrder(root);
System.out.println("输入想要节点P：");
p=input.next();
Node P=new Node(p);
Stack<Node> s= new Stack<Node>();
boolean t;
// System.out.println(root.val);
t=searchNode(root,s,P);
System.out.println(t+"路线为：");
for (Node x : s) {
System.out.println(x.val);
}
}
}