二叉树数据结构及其算法操作（Java）
2018-03-10 本文已影响0人
dreamsfuture
二叉树的定义
class TreeNode
{
int value;
TreeNode parent;
TreeNode left;
TreeNode right;
public TreeNode(int value, TreeNode parent, TreeNode left, TreeNode right) {
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
}
向二叉树中插入节点
public BinaryNode insert(T data,BinaryNode root){
//终止条件
if(root==null){
root=new BinaryNode(data,null,null);
}
//比较插入结点的值，决定向左子树还是右子树搜索
if (data < root.data){//左
root.left=insert(data,root.left);
}
else if(data > root.data){//右
root.right=insert(data,root.right);
}
else {
;//已有元素就没必要重复插入了
}
return root;
}
搜索二叉树中最大值和最小值
public BinaryNode findMin(BinaryNode root){
if (root==null)//终止条件
return null;
else if (root.left==null)//如果没有左结点,那么t就是最小的
return root;
return findMin(root.left);
}
private BinaryNode findMax(BinaryNode root){
if (root==null)//终止条件
return null;
else if (root.right==null)
return root;
return findMax(root.right);
}
搜索二叉树的深度（height）和节点数（size）
public int height(BinaryNode root){
if (root==null){
return 0;
}
else {
int l=height(root.left);
int r=height(root.right);
return (l>r) ? (l+1):(r+1);//返回并加上当前层
}
}
public int size(BinaryNode root){
if (root == null)
return 0;
else
{
//对比汉诺塔:H(n)=H(n-1) + 1 + H(n-1)
return size(root.left) + 1 + size(root.right);
}
}
二叉搜索树的遍历算法
（前根）前序遍历：根节点->左子树->右子树
（中根）中序遍历：左子树->根节点->右子树
（后根）后序遍历：左子树->右子树->根节点
1. 前序遍历（先根遍历）
①递归算法
public void preOrder(BinaryNode root){
if (root!=null) {//递归结束条件
//先访问根结点
System.out.println(root.data);
//遍历左子树
preOrder(root.left);
//遍历右子树
preOrder(root.right);
}
}
②非递归算法
public void preOrder(BinaryNode root){
//构建用于存放结点的栈
LinkedStack<BinaryNode> stack=new LinkedStack<>();
//边循环边输出中节点，一直到最低，然后开始搜索其对应的右子树
while (root!=null||!stack.isEmpty()){
if (root!=null){
//访问该结点
System.out.println(root.data);
//将已访问过的结点入栈
stack.push(root);
//继续访问其左孩子，直到root为null
root=root.left;
}
else {
//若p=null 栈不为空,则说明已沿左子树访问完一条路径, 从栈中弹出栈顶结点,并访问其右孩子
root=stack.pop();//获取已访问过的结点记录
root=root.right;
}
}
}
中续遍历（中根遍历）
特点：二叉搜索树的中序遍历是按照节点值依次递增的搜索顺序遍历
①递归算法
public void inOrder(BinaryNode root) {
if (root!=null) {//递归结束条件
//先遍历左子树
inOrder(root.left);
//再遍历根结点
System.out.println(root.data);
//最后遍历右子树
inOrder(root.right);
}
}
②非递归算法
public void inOrder(BinaryNode root){
//构建用于存放结点的栈
LinkedStack<BinaryNode> stack=new LinkedStack<>();
//需要从最低左子树开始输出，所以循环至最低
while (root!=null||!stack.isEmpty()){
while (root!=null){//把左孩子都入栈,至到左孩子为null
stack.push(root);
root=root.left;
}
//如果栈不为空,因为前面左孩子已全部入栈
if(!stack.isEmpty()){
root=stack.pop();
//访问p结点
System.out.println(root.data);
//访问p结点的右孩子
root=root.right;
}
}
}
后续遍历（后根遍历）
①递归算法
public void postOrder(BinaryNode root) {
if (root!=null) {//递归结束条件
//先遍历左子树
postOrder(root.left);
//再遍历右子树
postOrder(root.right);
//最后遍历根结点
System.out.println(root.data);
}
}
②非递归算法
public void postOrder(BinaryNode root){
//构建用于存放结点的栈
LinkedStack<BinaryNode> stack=new LinkedStack<>();
BinaryNode<T> currentNode =root;
BinaryNode<T> prev=root;
//需要从最低叶子节点开始输出结果
while (currentNode!=null||!stack.isEmpty()){
//把左子树加入栈中,直到左子树最低处的叶子结点，终止条件是叶子节点的左子树为null
while (currentNode!=null){
stack.push(currentNode);
currentNode=currentNode.left;
}
//开始访问当前结点的父结点的右孩子
if(!stack.isEmpty()){
//获取右孩子，先不弹出
BinaryNode temp=stack.peek().right;
//先判断是否有右孩子或者右孩子是否已被访问过
if(temp==null||temp==prev){ //没有右孩子||右孩子已被访问过
//如果没有右孩子或者右孩子已被访问,则弹出父结点并访问
currentNode=stack.pop();
//当前节点左右子树为null则输出，因为此节点为叶子节点或者已经被访问过了
System.out.println(currentNode.data);
//记录已访问过的结点
prev=currentNode;
//访问过的节点置为null
currentNode=null;
}
else { //有右孩子,则开始遍历右子树
currentNode=temp;
}
}
}
层续遍历
public void levelOrder(BinaryNode root) {
//存放需要遍历的结点,左结点一定优先右节点遍历
LinkedQueue<BinaryNode> queue=new LinkedQueue<>();
StringBuffer sb=new StringBuffer();
while (root!=null){
//记录经过的结点
System.out.println(root.data);
//先按层次遍历结点,左结点一定在右结点之前访问
if(root.left!=null){
//孩子结点入队
queue.add(root.left);
}
if (root.right!=null){
queue.add(root.right);
}
//访问下一个结点
root=queue.poll();
}
}
利用中序遍历和前序遍历或/后序遍历构建二叉树
前序遍历和中序遍历[3]
建树思想：
- 选取前序遍历的第一个val构建树节点作二叉树的根root，然后在中序遍历中找到root.val值，返回此值在中序遍历的索引位置，前序遍历数组索引加一，因为每一个数值都能成为根；
- 以中序遍历返回的索引分割中序遍历数组，左子数组为左子树，右子数组为右子树，递归放入到创建节点的函数中。
- 返回的结果为每一个创建的根root，即利用前序遍历创建的每一个节点，中序遍历只是用于分割左右子树的作用。
public class CreateTreeByInOrderAndPreOrder {
int[] inOrderResult ={4,2,5,1,6,3};
int[] preOrderResult ={1,2,4,5,3,6};
static int preIndex = 0;
public TreeNode createTreeNode(int[] preOrder, int preStart, int preEnd) {
if (preStart > preEnd){return null;}
//为当前数据创建一个新的树节点
TreeNode root = new TreeNode(preOrder[preIndex++]);
if (preStart == preEnd){return root;}
//在中序遍历中找到当前节点的位置索引
int inOrderIndex = finIndexInInorder(root.val);
root.left = createTreeNode(preOrder, preOrderStart + 1, inOrderIndex );
root.right = createTreeNode(preOrder, inOrderIndex + 1, preOrderEnd);
return root;
}
private int finIndexInInorder(int rootValue) {
for (int i = 0; i < inOrderResult.length; i++) {
if (rootValue == inOrderResult[i]) {
return i;
}
}
return -1;
}
}
后序遍历与中序遍历
public class CreateTreeByPostOrderAndInOrder {
int[] inOrderResult ={4,8,2,5,1,6,3,7};
int[] postOrderResult = {8,4,5,2,6,7,3,1};
int postOderIndex = inOrderResult.length -1;
public TreeNode createTreeNode(int[] postOrder, int postStart, int postEnd) {
if (postStart > postEnd){return null;}
TreeNode root = new TreeNode(postOrder[postOrderIndex--]);
if (postStart == postEnd){return root;}
int inOrderIndex = finIndexInInorder(root.val);
root.right = createTreeNode(postOrder,inOrderIndex, postEnd-1);
root.left = createTreeNode(postOrder, postStart, inOrderIndex-1);
return root;
}
private int finIndexInInorder(int rootValue) {
for (int i = 0; i < inOrderResult.length; i++) {
if (rootValue == inOrderResult[i]) {
return i;
}
}
return -1;
}
}
参考文献：
[1] java数据结构与算法之树基本概念及二叉树（BinaryTree）的设计与实现
[2] 数据结构（六）——二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现
[3] 中序遍历+先/后序遍历创建二叉树
