剑指offer-面试题37：序列化二叉树及二叉树的基本操作和测试

佚名 6年前 (2019-04-25) 随笔 1059人围观抢沙发百度已收录

序列化二叉树：即将一棵二叉树转换为字符串，反序列化二叉树即把序列化为二叉树的字符串转换为二叉树。
思想：采用二叉树的前序遍历方法来对二叉树进行序列化
具体代码如下：

 //序列化二叉树
 public String SerializeBinaryTree(TreeNode root)
 {
 StringBuilder sb = new StringBuilder();
 if(root == null)
 {
 sb.append("$,");
 return sb.toString();
 }
 else {
 sb.append(root.value+",");
 //System.out.print(root.value+",");
 sb.append(SerializeBinaryTree(root.getLeftNode()));
 sb.append(SerializeBinaryTree(root.getRightNode()));
 }
 return sb.toString();
 }
 //二叉树的反序列化
 public TreeNode Deserialize(String str)
 {
 index++;
 String[] DLRseq= str.split(",");
 TreeNode node = null;
 if(!DLRseq[index].equals("$"))
 {
 node = new TreeNode(Integer.parseInt(DLRseq[index]));
 node.leftNode = Deserialize(str);
 node.rightNode = Deserialize(str);
 }
 return node;
 }

//以下代码包含了有关二叉树的基本操作，包括：遍历、查找、判断是否为满二叉树等等
package com.zc.algorithm;
import java.util.Queue;
import java.util.Stack;
import java.util.LinkedList;

public class SerializeAndDeserializeBinaryTree {
 int index = -1;//定义一个全局变量，在反序列化中使用
 //树节点
 public class TreeNode
 {
 int value;
 TreeNode leftNode;
 TreeNode rightNode;
 public TreeNode(int value)
 {
 this.value = value;
 }
 //设置左节点
 public void setLeftNode(TreeNode leftNode)
 {
 this.leftNode = leftNode;
 }
 //获取左节点
 public TreeNode getLeftNode()
 {
 return leftNode;
 }
 //设置右节点
 public void setRightNode(TreeNode rightNode)
 {
 this.rightNode = rightNode;
 }
 //获取右节点
 public TreeNode getRightNode()
 {
 return rightNode;
 }
 //前序遍历:递归的方法
 public void preOrderByRecursion()
 {
 System.out.print(this.value + " ");
 //遍历左节点
 if(this.leftNode != null)
 {
 this.leftNode.preOrderByRecursion();
 }
 //遍历右节点
 if( this.rightNode != null)
 {
 this.rightNode.preOrderByRecursion();
 }
 }
 //前序遍历：非递归，采用栈的方式，思路：首先左节点入栈，当没有左节点后，每个左节点依次出栈，并判断出栈的左节点是否有右孩子
 public void preOrderByStack(TreeNode root)
 {
 //定义一个栈
 Stack<TreeNode> stack = new Stack<TreeNode>();
 while(true)
 {
 while(root != null)
 {
 //打印节点的值
 System.out.print(root.value + " ");
 //将节点入栈
 stack.push(root);
 //获取当前节点的左节点
 root = root.getLeftNode();
 }
 if(stack.isEmpty()) break;
 //当所有的左节点遍历完毕，将左节点出栈
 root = stack.pop();
 //获取当前节点的右节点
 root = root.getRightNode();
 }
 }
 //中序遍历:递归方式
 public void middleOrderByRecursion()
 {
 if(this.leftNode != null)
 {
 this.middleOrderByRecursion();
 }
 System.out.print(this.value);
 if(this.rightNode != null)
 {
 this.middleOrderByRecursion();
 }
 }
 //中序遍历：采用栈的方式
 public void middleOrderByStack(TreeNode root)
 {
 Stack<TreeNode> stack = new Stack<TreeNode>();
 while(true)
 {
 while(root != null)
 {
 stack.push(root);
 root = root.getLeftNode();
 }
 if(stack.isEmpty()) break;
 root = stack.pop();
 System.out.print(root.value+",");
 root = root.getRightNode();
 }
 }
 //后序遍历：递归方式
 public void afterOrderByRecursion()
 {
 if(this.leftNode!=null)
 {
 this.afterOrderByRecursion();
 }
 if(this.rightNode != null)
 {
 this.afterOrderByRecursion();
 }
 System.out.print(this.value+" ");
 }
 //后序遍历：栈的方式
 public void afterOrderByStack(TreeNode root)
 {
 }
 //层序遍历
 public void levelOrder(TreeNode root)
 {
 TreeNode temp = null;
 Queue<TreeNode> queue = new LinkedList<TreeNode>();
 queue.offer(root);
 while (!queue.isEmpty())
 {
 temp = queue.poll();
 System.out.print(temp.value+" ");
 if(temp.getLeftNode()!=null)
 {
 queue.offer(temp.getLeftNode());
 }
 if(temp.rightNode !=null)
 {
 queue.offer(temp.getRightNode());
 }
 }
 }

 //判断一棵树是否是完全二叉树（层次遍历的变形）
 public boolean isCompleteBinaryTree(TreeNode root) {
 TreeNode node = root;
 Queue<TreeNode> queue = new LinkedList<TreeNode>();
 queue.offer(root);
 while (!queue.isEmpty())
 {
 TreeNode pre = queue.poll();
 if(pre == null)
 {
 break;
 }
 queue.offer(pre.leftNode);
 queue.offer(pre.rightNode);
 }
 while(!queue.isEmpty())
 {
 TreeNode cur = queue.poll();
 if(cur != null)
 {
 return false;
 }
 }
 return true;
 }


 }
 //二叉树
 public class BinaryTree
 {
 TreeNode root;
 int counts = 0;
 //设置根节点
 public void setRoot(TreeNode root)
 {
 this.root = root;
 }
 //获取根节点
 public TreeNode getRoot() {
 return this.root;
 }
 //前序遍历：递归方式
 public void preOrderByRecursion()
 {
 root.preOrderByRecursion();
 }
 //前序遍历：栈方式
 public void preOrderByStack(TreeNode root)
 {
 root.preOrderByStack(root);
 }
 //中序遍历：递归方式
 public void middleOrderByRecursion()
 {
 root.middleOrderByRecursion();
 }
 //中序遍历：栈方式
 public void middleOrderByStack(TreeNode root)
 {
 root.preOrderByStack(root);
 }
 //后序遍历：递归方式
 public void afterOrderByRecursion()
 {
 root.afterOrderByRecursion();
 }
 //层序遍历
 public void levelOrderByQueue(TreeNode root)
 {
 root.levelOrder(root);
 }
 //获取二叉树的高度
 public int getHeight()
 {
 TreeNode cur = this.root;
 int height = 0;
 while(cur!=null)
 {
 cur = cur.leftNode;
 height++;
 }
 return height;
 }
 //求叶子节点数：递归方式
 public void getCountsOfLeaf(TreeNode root)
 {
 if(root == null)
 {
 return ;
 }
 if(root.leftNode == null || root.rightNode==null)
 {
 counts++;
 }
 this.getCountsOfLeaf(root.leftNode);
 this.getCountsOfLeaf(root.rightNode);
 }
 //求叶子节点数：非递归方式
 public int getCountsOfLeafByRecursion(TreeNode root)
 {

 int counts = 0;
 if(root == null)
 {
 return counts;
 }
 Stack<TreeNode> stack = new Stack<TreeNode>();
 TreeNode node = null;
 stack.push(root);
 while(!stack.isEmpty())
 {
 node = stack.pop();
 if(node.leftNode == null && node.rightNode==null)
 {
 counts++;
 }
 if(node.leftNode != null)
 {
 stack.push(node.leftNode);
 }
 if(node.rightNode!=null)
 {
 stack.push(node.rightNode);
 }
 }
 return counts;
 }
 //查找某个节点
 public TreeNode findNode(TreeNode root, int k)
 {
 if(root == null)
 {
 return null;
 }
 else if(root.value == k)
 {
 return root;
 }
 TreeNode leftNode = findNode(root.leftNode,k);
 if(leftNode != null)
 {
 return leftNode;
 }
 TreeNode rightNode = findNode(root.rightNode,k);
 if(rightNode != null)
 {
 return rightNode;
 }
 return null;
 }
 //获取K层的所有节点值
 public int getNodeNumber(TreeNode root ,int k)
 {
 if(k==1)
 {
 if(root == null)
 {
 return 0;
 }
 System.out.println(root.value);
 return 1;
 }
 return getNodeNumber(root.leftNode,k-1)+ getNodeNumber(root.rightNode,k-1);
 }
 //返回某节点的父节点
 public TreeNode getParent(TreeNode root, int x)
 {
 if(root == null)
 {
 return null;
 }
 TreeNode leftNode = root.leftNode;
 TreeNode rightNode = root.rightNode;
 if(leftNode!=null && leftNode.value == x)
 {
 return root;
 }
 if(rightNode!=null&& rightNode.value == x)
 {
 return root;
 }
 TreeNode leftParent = getParent(root.leftNode,x);
 if(leftParent!=null)
 {
 return leftParent;
 }
 TreeNode rightParent = getParent(root.rightNode,x);
 if(rightParent != null)
 {
 return rightParent;
 }
 return null;
 }


 }

 //序列化二叉树
 public String SerializeBinaryTree(TreeNode root)
 {
 StringBuilder sb = new StringBuilder();
 if(root == null)
 {
 sb.append("$,");
 return sb.toString();
 }
 else {
 sb.append(root.value+",");
 //System.out.print(root.value+",");
 sb.append(SerializeBinaryTree(root.getLeftNode()));
 sb.append(SerializeBinaryTree(root.getRightNode()));
 }
 return sb.toString();
 }
 //二叉树的反序列化
 public TreeNode Deserialize(String str)
 {
 index++;
 String[] DLRseq= str.split(",");
 TreeNode node = null;
 if(!DLRseq[index].equals("$"))
 {
 node = new TreeNode(Integer.parseInt(DLRseq[index]));
 node.leftNode = Deserialize(str);
 node.rightNode = Deserialize(str);
 }
 return node;
 }
 
 public static void main(String[] args)
 {
 SerializeAndDeserializeBinaryTree sdTree = new SerializeAndDeserializeBinaryTree();
 //创建一颗树
 BinaryTree binTree = sdTree.new BinaryTree();
 //创建根节点
 TreeNode root = sdTree.new TreeNode(1);
 //把根节点赋值给树
 binTree.setRoot(root);
 //设置左节点
 TreeNode leftNode = sdTree.new TreeNode(2);
 root.setLeftNode(leftNode);
 //设置右节点
 TreeNode rightNode = sdTree.new TreeNode(3);
 root.setRightNode(rightNode);
 //设置第二层的左右节点
 leftNode.setLeftNode(sdTree.new TreeNode(4));

 leftNode.setRightNode(sdTree.new TreeNode(5));
 rightNode.setLeftNode(sdTree.new TreeNode(6));
 rightNode.setRightNode(sdTree.new TreeNode(7));
 binTree.preOrderByRecursion();
 System.out.println();
 // String str = "1,2,4,$,$,5,$,$,3,6,$,$,7,$,$";
 System.out.println("序列化二叉树");
 String result = sdTree.SerializeBinaryTree(root);
 System.out.println("序列后的结果：" + result);
 System.out.println("================");
 System.out.println("反序列化二叉树,打印的结果为：");
 binTree.preOrderByStack(sdTree.Deserialize(result));
 System.out.println();
 System.out.println("树的高度为：");
 System.out.println(binTree.getHeight());
 System.out.println("树的叶子节点数为：");
 binTree.getCountsOfLeaf(root);
 System.out.println(binTree.counts);
 System.out.println("采用栈的方式获取树的叶子节点数");
 System.out.println(binTree.getCountsOfLeafByRecursion(root));
 System.out.println("寻找某个节点");
 int k = 5;
 TreeNode node = binTree.findNode(root,k);
 System.out.println(node.value);
 }

}