首页 > 代码库 > java实现二叉树相关代码-----数据结构
java实现二叉树相关代码-----数据结构
接口
/*1.开发时间:2014-11-5 *2.开发者:赵远 *3.维护者:赵远 *3.程序说明:树的接口 *4.注意事项:暂且没有 * **/ package Tree; import Tree.node; public interface TreeNode { // class Node {}; // 1. 求二叉树中的节点个数 int GetNodeNum(node root); // 2. 求二叉树的深度 int GetDepth(node root); // 3. 前序遍历,中序遍历,后序遍历 void PreOrderTraverse(node root); void InOrderTraverse(node root); void PostOrderTraverse(node root); // 4.分层遍历二叉树(按层次从上往下,从左往右) void LevelTraverse(node root); // 5. 将二叉查找树变为有序的双向链表 // 6. 求二叉树第K层的节点个数 // 7. 求二叉树中叶子节点的个数 // 8. 判断两棵二叉树是否结构相同 // 9. 判断二叉树是不是平衡二叉树 // 10. 求二叉树的镜像 // 11. 求二叉树中两个节点的最低公共祖先节点 // 12. 求二叉树中节点的最大距离 // 13. 由前序遍历序列和中序遍历序列重建二叉树 // 14.判断二叉树是不是完全二叉树 }
节点
package Tree; //* 结点类。 public class node { public Object data; // 该节点存储的值。 public node leftChild; // 指向左子节点的引用。 public node rightChild; // 指向右子节点的引用。 public node(Object value) { this.data = value; leftChild = null; rightChild = null; } }
具体实现
/*1.开发时间:2014-11-13 *2.开发者:赵远 *3.维护者:赵远 *3.程序说明:二叉树的方法實現 *4.注意事项:暂且没有 * **/ package Tree; import Tree.node; import Tree.ArrayQueue; public class BinaryTreeNode implements TreeNode { private node root; // 根节点 BinaryTreeNode() { root = null; } // 1. 求二叉树中的节点个数 // 递归解法: // (1)如果二叉树为空,节点个数为0 // (2)如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1 public int GetNodeNum(node root) { if (root == null) // 递归出口 return 0; return GetNodeNum(root.rightChild) + GetNodeNum(root.leftChild) + 1; }; // 2. 求二叉树的深度 // 递归解法: // (1)如果二叉树为空,二叉树的深度为0 // (2)如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1 public int GetDepth(node root) { if (root == null) // 递归出口 return 0; int depthLeft = GetDepth(root.leftChild); int depthRight = GetDepth(root.rightChild); return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1); }; // 3. 前序遍历,中序遍历,后序遍历 // 前序遍历递归解法: // (1)如果二叉树为空,空操作 // (2)如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树 // private void Visit(Node root){函数独立 // if (root == null) // return ; // System.out.print("......"); // Visit(root.leftChild); // 前序遍历左子树 // Visit(root.rightChild); // 前序遍历右子树 // }; public void PreOrderTraverse(node root) { if (root == null) return; System.out.print(root.data + " "); PreOrderTraverse(root.leftChild); PreOrderTraverse(root.rightChild); // Visit(root); 函数独立 }; // 中序遍历递归解法 // (1)如果二叉树为空,空操作。 // (2)如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树 public void InOrderTraverse(node root) { if (root == null) return; InOrderTraverse(root.leftChild); System.out.print(root.data + " "); InOrderTraverse(root.rightChild); // }; // 后序遍历递归解法 // (1)如果二叉树为空,空操作 // (2)如果二叉树不为空,后序遍历左子树,后序遍历右子树,访问根节点 public void PostOrderTraverse(node root) { PostOrderTraverse(root.leftChild); PostOrderTraverse(root.rightChild); System.out.print(root.data + " "); }; // 4.分层遍历二叉树(按层次从上往下,从左往右) // 队列初始化,将根节点压入队列。 // 当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节 // 点不为空,将其压入队列。 public void LevelTraverse(node root) { ArrayQueue q = new ArrayQueue(); if (root == null) return; q.enQueue(root); while (!q.isEmpty()) { root.data = q.getFront(); q.deQueue(); System.out.print(root.data + " "); // 访问节点 if (root.leftChild != null) q.enQueue(root.leftChild); if (root.rightChild != null) q.enQueue(root.rightChild); } return; } // 5. 求二叉树第K层的节点个数 // 递归解法: // (1)如果二叉树为空或者k<1返回0 // (2)如果二叉树不为空并且k==1,返回1 // (3)如果二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树k-1层节点个数之和 int GetNodeNumKthLevel(node root, int k) { if(root == null || k < 1) return 0; if(k == 1) return 1; int numLeft = GetNodeNumKthLevel(root.leftChild, k-1); // 左子树中k-1层的节点个数 int numRight = GetNodeNumKthLevel(root.rightChild, k-1); // 右子树中k-1层的节点个数 return (numLeft + numRight); } // 6. 求二叉树中叶子节点的个数 // 递归解法: // (1)如果二叉树为空,返回0 // (2)如果二叉树不为空且左右子树为空,返回1 // (3)如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数 int GetLeafNodeNum(node root) { if(root == null) return 0; if(root.leftChild == null && root.rightChild == null) return 1; int numLeft = GetLeafNodeNum(root.leftChild); // 左子树中叶节点的个数 int numRight = GetLeafNodeNum(root.leftChild); // 右子树中叶节点的个数 return (numLeft + numRight); } // 7. 判断两棵二叉树是否结构相同 // 不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。 // 递归解法: // (1)如果两棵二叉树都为空,返回真 // (2)如果两棵二叉树一棵为空,另一棵不为空,返回假 // (3)如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假 boolean StructureCmp(node root1, node root2) { if(root1 == null && root2 == null) // 都为空,返回真 return true; else if(root1 == null || root2 == null) // 有一个为空,一个不为空,返回假 return false; boolean resultLeft = StructureCmp(root1.leftChild,root2.leftChild); // 比较对应左子树 boolean resultRight = StructureCmp(root1.rightChild, root2.rightChild); // 比较对应右子树 return (resultLeft && resultRight); } // 8. 判断二叉树是不是平衡二叉树 // 递归解法: // (1)如果二叉树为空,返回真 // (2)如果二叉树不为空,如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假 boolean IsAVL(node root, int height) { if(root == null) // 空树,返回真 { height = 0; return true; } int heightLeft = 0; boolean resultLeft = IsAVL(root.leftChild, heightLeft); int heightRight = 0; boolean resultRight = IsAVL(root.rightChild, heightRight); if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL,并且高度相差不大于1,返回真 { height = max(heightLeft, heightRight) + 1; return true; } else { height = max(heightLeft, heightRight) + 1; return false; } } private int max(int heightLeft, int heightRight) { return heightLeft>heightRight?heightLeft:heightRight; } private int abs(int i) { if(i>0) return i; else return -i; } //9.递归方法插入节点 public node insert(node root, Object x) { node p = null ; p.data=http://www.mamicode.com/x;>引用一个队列
package Tree; /** * * @author 上课 */ public class ArrayQueue implements Queue { private Object[] data; private int front; private int rear; public ArrayQueue(int capacity) { this.data = new Object[capacity]; this.front = this.rear = 0; } public ArrayQueue() { this(1024); } public void clear() { this.front = this.rear = 0; } public boolean isEmpty() { return this.front == this.rear; } public Object getFront() { if (isEmpty()) { throw new UnsupportedOperationException("队列已空"); } return data[front]; } public void enQueue(Object o) { if (isFull()) { throw new UnsupportedOperationException("队列已满"); } this.data[rear++] = o; rear %= data.length; } public Object deQueue() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. } private boolean isFull() { return ((rear + 1) % data.length) == front; } }
java实现二叉树相关代码-----数据结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。