数据结构已在之前文章中表示过，但还是在此处表示一下
public class TreeNode<T> {
T val;
TreeNode left = null;
TreeNode right = null;
public TreeNode(T val) {
this.val = val;
}
}
来熟悉一下二叉树的preOrder,inOrder,postOrder
image.png
现在，假设仅仅知道前序和中序遍历，如何求后序遍历呢？比如，已知一棵树的前序遍历是”GDAFEMHZ”，而中序遍历是”ADEFGHMZ”应该如何求后续遍历?
第一步，root最简单，前序遍历的第一节点G就是root。
第二步，继续观察前序遍历GDAFEMHZ，除了知道G是root，剩下的节点必然是root的左右子树之外，没法找到更多信息了。
第三步，那就观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。
第四步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。
第五步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的右子树的第一个节点就是右子树的根节点。
如何知道哪里是前序遍历中的左子树和右子树的分界线呢？通过中序遍历去数节点的个数。
在上一次中序遍历中，root左侧是A、D、E、F，所以有4个节点位于root左侧。那么在前序遍历中，必然是第1个是G，第2到第5个由A、D、E、F过程，第6个就是root的右子树的根节点了，是M。
第六步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。
第七步，其实，如果仅仅要求写后续遍历，甚至不要专门占用空间保存还原后的树。只需要稍微改动第六步，就能实现要求。仅需要把第六步的递归的过程改动为如下:
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
我总结之后大概就是，前序找到根节点，中序通过根节点分左右，同时前序也分了左右，再在前序的分类好的子树中第一个就是当前子树的根节点，同时中序又分好左右...以此类推
以下开始实现这个思路：
这是示例二叉树
image.png
建立示例二叉树
//建立示例二叉树
static TreeNode createSampleTree(){
TreeNode a=new TreeNode("a");
TreeNode b=new TreeNode("b");
TreeNode c=new TreeNode("c");
TreeNode d=new TreeNode("d");
TreeNode e=new TreeNode("e");
TreeNode f=new TreeNode("f");
TreeNode g=new TreeNode("g");
TreeNode h=new TreeNode("h");
a.left=d;
a.right=c;
d.right=b;
c.left=e;
c.right=f;
b.left=g;
f.left=h;
return a;
}
根据本文集 4.basic的PrintTree()方法输出当前二叉树的情况
image.png
与实际相符，开始复习输出前中后序遍历的代码
package Chapter4;
import javax.sound.midi.Soundbank;
import java.util.Stack;
public class BinarySearchTree {
//建立示例二叉树
static TreeNode createSampleTree(){
TreeNode a=new TreeNode("a");
TreeNode b=new TreeNode("b");
TreeNode c=new TreeNode("c");
TreeNode d=new TreeNode("d");
TreeNode e=new TreeNode("e");
TreeNode f=new TreeNode("f");
TreeNode g=new TreeNode("g");
TreeNode h=new TreeNode("h");
a.left=d;
a.right=c;
d.right=b;
c.left=e;
c.right=f;
b.left=g;
f.left=h;
return a;
}
//前序遍历 递归
static void preOrderRecursive(TreeNode root){
System.out.print(root.val+",");
if(root.left != null){
preOrderRecursive(root.left);
}
if(root.right != null){
preOrderRecursive(root.right);
}
}
//前序遍历 非递归
static void preOrderNotRecursive(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
String output="";
while(root!=null || stack.size()>0) {
while (root != null) {
output += root.val+",";
stack.push(root);
if (root.left != null) {
root = root.left;
}else{
break;
}
}
if (stack.size() > 0) {
TreeNode roots = stack.pop();
root = roots.right;
}
}
System.out.println(output);
}
//中序遍历 递归
static void inOrderRecursive(TreeNode root){
if(root.left != null){
inOrderRecursive(root.left);
}
System.out.print(root.val+",");
if(root.right!=null){
inOrderRecursive(root.right);
}
}
//中序遍历 非递归
static void inOrderNotRecursive(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
String output="";
while (!stack.isEmpty() || root!=null) {
while (root != null) {
stack.push(root);
if (root.left != null) {
root = root.left;
}else{
break;
}
}
if (!stack.isEmpty()) {
TreeNode roots = stack.pop();
output += roots.val + ",";
root = roots.right;
}
}
System.out.println(output);
}
//后序遍历 递归
static void postOrderRecursive(TreeNode root){
if(root.left!=null){
postOrderRecursive(root.left);
}
if(root.right!=null){
postOrderRecursive(root.right);
}
System.out.print(root.val+",");
}
//后序遍历 非递归
static void postOrderNotRecursive(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
String output="";
TreeNode lastNode=new TreeNode("");
while(root != null){
stack.push(root);
root=root.left;
}
while (!stack.isEmpty()){
TreeNode roots=stack.pop();
if(roots.right==null || roots.right==lastNode){
output+=roots.val+",";
lastNode=roots;
}else{
stack.push(roots);
roots=roots.right;
while(roots != null){
stack.push(roots);
roots=roots.left;
}
}
}
System.out.println(output);
}
public static void main(String[] args) {
TreeNode root=createSampleTree();
PrintTreeNode.PrintTree(root);
System.out.println("前序遍历递归：");
preOrderRecursive(root);
System.out.println();
System.out.println("前序遍历非递归：");
preOrderNotRecursive(root);
System.out.println("中序遍历递归：");
inOrderRecursive(root);
System.out.println();
System.out.println("中序遍历非递归：");
inOrderNotRecursive(root);
System.out.println("后序遍历递归：");
postOrderRecursive(root);
System.out.println();
System.out.println("后序遍历非递归：");
postOrderNotRecursive(root);
}
}
温习完各种遍历后，开始实现 已知前序遍历和中序遍历得到树的代码了！
package Chapter4;
import javax.sound.midi.Soundbank;
import java.util.Stack;
public class BinarySearchTree {
//建立示例二叉树
static TreeNode createSampleTree(){
TreeNode a=new TreeNode("a");
TreeNode b=new TreeNode("b");
TreeNode c=new TreeNode("c");
TreeNode d=new TreeNode("d");
TreeNode e=new TreeNode("e");
TreeNode f=new TreeNode("f");
TreeNode g=new TreeNode("g");
TreeNode h=new TreeNode("h");
a.left=d;
a.right=c;
d.right=b;
c.left=e;
c.right=f;
b.left=g;
f.left=h;
return a;
}
//前序遍历 递归
static void preOrderRecursive(TreeNode root){
System.out.print(root.val+",");
if(root.left != null){
preOrderRecursive(root.left);
}
if(root.right != null){
preOrderRecursive(root.right);
}
}
//前序遍历 非递归
static void preOrderNotRecursive(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
String output="";
while(root!=null || stack.size()>0) {
while (root != null) {
output += root.val+",";
stack.push(root);
if (root.left != null) {
root = root.left;
}else{
break;
}
}
if (stack.size() > 0) {
TreeNode roots = stack.pop();
root = roots.right;
}
}
System.out.println(output);
}
//中序遍历 递归
static void inOrderRecursive(TreeNode root){
if(root.left != null){
inOrderRecursive(root.left);
}
System.out.print(root.val+",");
if(root.right!=null){
inOrderRecursive(root.right);
}
}
//中序遍历 非递归
static void inOrderNotRecursive(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
String output="";
while (!stack.isEmpty() || root!=null) {
while (root != null) {
stack.push(root);
if (root.left != null) {
root = root.left;
}else{
break;
}
}
if (!stack.isEmpty()) {
TreeNode roots = stack.pop();
output += roots.val + ",";
root = roots.right;
}
}
System.out.println(output);
}
//后序遍历 递归
static void postOrderRecursive(TreeNode root){
if(root.left!=null){
postOrderRecursive(root.left);
}
if(root.right!=null){
postOrderRecursive(root.right);
}
System.out.print(root.val+",");
}
//后序遍历 非递归
static void postOrderNotRecursive(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
String output="";
TreeNode lastNode=new TreeNode("");
while(root != null){
stack.push(root);
root=root.left;
}
while (!stack.isEmpty()){
TreeNode roots=stack.pop();
if(roots.right==null || roots.right==lastNode){
output+=roots.val+",";
lastNode=roots;
}else{
stack.push(roots);
roots=roots.right;
while(roots != null){
stack.push(roots);
roots=roots.left;
}
}
}
System.out.println(output);
}
//通过前序遍历和中序遍历得到后序遍历
static void getPostByPreAndIn(String preOrder,String inOrder){
String postOrder="";
//get preCharArray
String[] preOrderArray=preOrder.split(",");
//get inCharArray
String[] inOrderArray=inOrder.split(",");
TreeNode root=getTreeNode(preOrderArray,inOrderArray);
System.out.println("通过中序遍历和前序遍历得到的后序遍历：");
postOrderNotRecursive(root);
}
static int getIndex(String[] array,String index){
for(int i=0;i<array.length;i++){
if(index.equals(array[i])){
return i;
}
}
return -1;
}
static String[] getNewCharArray(String[] original,int startIndex,int endIndex){
String[] returnArray=new String[endIndex-startIndex];
int count=0;
for(int i=startIndex;i<endIndex;i++){
returnArray[count]=original[i];
count++;
}
return returnArray;
}
static TreeNode getTreeNode(String[] preArray,String[] inArray){
if(preArray.length == 0){
return null;
}
TreeNode root=new TreeNode(preArray[0]);
int rootIndex=getIndex(inArray,preArray[0]);
String[] inArrayLeft=getNewCharArray(inArray,0,rootIndex);
String[] inArrayRight=getNewCharArray(inArray,rootIndex+1,inArray.length);
String[] preArrayLeft=getNewCharArray(preArray,1,inArrayLeft.length+1);
String[] preArrayRight=getNewCharArray(preArray,inArrayLeft.length+1,inArray.length);
root.left=getTreeNode(preArrayLeft,inArrayLeft);
root.right=getTreeNode(preArrayRight,inArrayRight);
return root;
}
public static void main(String[] args) {
TreeNode root=createSampleTree();
PrintTreeNode.PrintTree(root);
System.out.println("前序遍历递归：");
preOrderRecursive(root);
System.out.println();
System.out.println("前序遍历非递归：");
preOrderNotRecursive(root);
System.out.println("中序遍历递归：");
inOrderRecursive(root);
System.out.println();
System.out.println("中序遍历非递归：");
inOrderNotRecursive(root);
System.out.println("后序遍历递归：");
postOrderRecursive(root);
System.out.println();
System.out.println("后序遍历非递归：");
postOrderNotRecursive(root);
getPostByPreAndIn("a,d,b,g,c,e,f,h,","d,g,b,a,e,c,h,f,");
}
}
二叉查找树的增查删
知识点：
二叉查找树是满足以下条件的二叉树：1.左子树上的所有节点值均小于根节点值，2右子树上的所有节点值均不小于根节点值，3，左右子树也满足上述两个条件。
二叉查找树的插入过程如下：1.若当前的二叉查找树为空，则插入的元素为根节点，2.若插入的元素值小于根节点值，则将元素插入到左子树中，3.若插入的元素值不小于根节点值，则将元素插入到右子树中。
二叉查找树的删除，分三种情况进行处理：
1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。
2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。
3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。
image
image
image
知识点来源
https://www.cnblogs.com/aiyelinglong/archive/2012/03/27/2419972.html
二叉查找树的插入：
//二叉查找树的递归插入
static TreeNode insert(TreeNode root,int element){
if(root==null){
TreeNode treeNode=new TreeNode(element);
return treeNode;
}
int rootVal=Integer.parseInt(root.val.toString());
if(rootVal>element){
root.left=insert(root.left,element);
}else{
root.right=insert(root.right,element);
}
return root;
}
//二叉查找树的非递归插入
static TreeNode insert_1(TreeNode root,int element){
if(root==null){
TreeNode treeNode=new TreeNode(element);
return treeNode;
}
TreeNode newTreeNode=root;
while(newTreeNode!=null){
int rootVal=Integer.parseInt(newTreeNode.val.toString());
if(rootVal>element){
if(newTreeNode.left!=null){
newTreeNode=newTreeNode.left;
}else{
TreeNode newTree=new TreeNode(element);
newTreeNode.left=newTree;
break;
}
}else{
if(newTreeNode.right!=null){
newTreeNode=newTreeNode.right;
}else{
TreeNode newTree=new TreeNode(element);
newTreeNode.right=newTree;
break;
}
}
}
return root;
}
//二叉树的查找
static TreeNode search(TreeNode treeNode,int element){
if(treeNode==null){
return null;
}
int rootVal=Integer.parseInt(treeNode.val.toString());
if(rootVal==element){
return treeNode;
}
if(rootVal>element){
treeNode=search(treeNode.left,element);
}else{
treeNode=search(treeNode.right,element);
}
return treeNode;
}
//二叉树的查找非递归
static TreeNode search_1(TreeNode treeNode,int element){
if(treeNode==null){
return null;
}
while(treeNode!=null){
int rootVal=Integer.parseInt(treeNode.val.toString());
if(rootVal==element){
return treeNode;
}else{
if(rootVal>element){
treeNode=treeNode.left;
}else{
treeNode=treeNode.right;
}
}
}
return treeNode;
}
//删除的非递归
static Boolean delete(TreeNode treeNode,int element){
if(treeNode==null){
return false;
}else{
while(treeNode!=null){
int rootVal=Integer.parseInt(treeNode.val.toString());
if(rootVal>element){
if(treeNode.left!=null){
int leftVal=Integer.parseInt(treeNode.left.val.toString());
if(leftVal==element){
//需要删除的节点下并没有其他子节点
//直接删除此结点
if(treeNode.left.left==null && treeNode.left.right==null){
treeNode.left=null;
return true;
}else{
if(treeNode.left.left!=null && treeNode.left.right!=null){
//需要删除的节点下有两个子节点（既左右节点都存在）
//找出此结点右子树中的最小结点，用以代替要删除的结点，然后删除此最小结点
TreeNode rightSmarllest=treeNode.left.right;
while (rightSmarllest.left!=null){
rightSmarllest=rightSmarllest.left;
}
treeNode.left.val=rightSmarllest.val;
treeNode.left.right=rightSmarllest.right;
return true;
}else{
//需要删除的节点下有一个子节点（左或右）
//删除此结点，将此结点父节点连接到此结点左（右）子树
if(treeNode.left.left==null){
treeNode.left=treeNode.left.right;
}
if(treeNode.left.right==null){
treeNode.left=treeNode.left.left;
}
}
}
}else{
treeNode=treeNode.left;
}
}
}else{
if(treeNode.right!=null){
int rightVal=Integer.parseInt(treeNode.right.val.toString());
if(rightVal==element){
if(treeNode.right.left==null && treeNode.right.right==null){
treeNode.right=null;
return true;
}else{
if(treeNode.right.left!=null && treeNode.right.right!=null){
//左右子树都不为空
TreeNode rightSmarllest=treeNode.right.right;
while (rightSmarllest.right!=null){
rightSmarllest=rightSmarllest.left;
}
treeNode.right.val=rightSmarllest.val;
treeNode.right.right=rightSmarllest.right;
return true;
}else{
if(treeNode.right.left==null){
treeNode.right=treeNode.right.right;
return true;
}
if(treeNode.right.right==null){
treeNode.right=treeNode.right.left;
return true;
}
}
}
}else{
treeNode=treeNode.right;
}
}
}
}
}
return true;
}
//删除的递归写法
static TreeNode delete_1(TreeNode root,int element){
if(root == null){
return null;
}
int rootVal=Integer.parseInt(root.val.toString());
if(rootVal>element){
root.left=delete_1(root.left,element);
}else if(rootVal<element){
root.right=delete_1(root.right,element);
}else{
if(root.left ==null || root.right == null){
if(root.left==null){
root=root.right;
}else{
root=root.left;
}
}else{
TreeNode rightSmallest=root.right;
while(rightSmallest.left!=null){
rightSmallest=rightSmallest.left;
}
root.val=rightSmallest.val;
root.right=delete_1(root.right,Integer.parseInt(rightSmallest.val.toString()));
}
}
return root;
}
二叉树 的生成以及创建测试
static TreeNode createBinarySearchTree(){
TreeNode root=new TreeNode(10);
root=insert(root,5);
root=insert(root,11);
root=insert(root,4);
root=insert(root,6);
root=insert(root,12);
return root;
}
public static void main(String[] args) {
// TreeNode root=createSampleTree();
// PrintTreeNode.PrintTree(root);
// System.out.println("前序遍历递归：");
// preOrderRecursive(root);
// System.out.println();
// System.out.println("前序遍历非递归：");
// preOrderNotRecursive(root);
// System.out.println("中序遍历递归：");
// inOrderRecursive(root);
// System.out.println();
// System.out.println("中序遍历非递归：");
// inOrderNotRecursive(root);
// System.out.println("后序遍历递归：");
// postOrderRecursive(root);
// System.out.println();
// System.out.println("后序遍历非递归：");
// postOrderNotRecursive(root);
// getPostByPreAndIn("a,d,b,g,c,e,f,h,","d,g,b,a,e,c,h,f,");
TreeNode root=createBinarySearchTree();
System.out.println("原二叉搜索树：");
PrintTreeNode.PrintTree(root);
System.out.println("root没有8，请搜索！");
TreeNode searchNode1=search(root,8);
if(searchNode1==null){
System.out.println("没找到！");
}else{
PrintTreeNode.PrintTree(searchNode1);
}
TreeNode searchNode_1=search_1(root,8);
if(searchNode_1==null){
System.out.println("没找到！");
}else{
PrintTreeNode.PrintTree(searchNode1);
}
System.out.println("root有8，请搜索！");
root=insert_1(root,8);
TreeNode searchNode2=search(root,8);
if(searchNode2==null){
System.out.println("没找到！");
}else{
PrintTreeNode.PrintTree(searchNode2);
}
TreeNode searchNode_2=search(root,8);
if(searchNode_2==null){
System.out.println("没找到！");
}else{
PrintTreeNode.PrintTree(searchNode2);
}
System.out.println();
// System.out.println("开始删除！");
// if(delete(root,8)){
// PrintTreeNode.PrintTree(root);
// System.out.println("删除成功！");
// }else{
// System.out.println("找不到该元素！");
// }
// System.out.println("开始删除11！");
// if(delete(root,11)){
// PrintTreeNode.PrintTree(root);
// System.out.println("删除成功！");
// }else{
// System.out.println("找不到该元素！");
// }
System.out.println("开始删除11！");
PrintTreeNode.PrintTree(delete_1(root,11));
System.out.println("开始删除5！");
PrintTreeNode.PrintTree(delete_1(root,5));
// System.out.println("开始删除5！");
// if(delete(root,5)){
// PrintTreeNode.PrintTree(root);
// System.out.println("删除成功！");
// }else{
// System.out.println("找不到该元素！");
// }
}
