1.如何把一个有序的整数数组放到二叉树二叉树（Binary Tree）也称为二分树、二元树、对分树等，它是n（n≥0）个有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。
在二叉树中，一个元素也称作一个结点。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称作根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。
以下是二叉树的一些常见的基本概念：
1）结点的度。结点所拥有的子树的个数称为该结点的度。
2）叶子结点。度为0的结点称为叶子结点，或者称为终端结点。
3）分支结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点。
4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
5）路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i＜k），就把 n1,n2,…,nk 称为一条由 n1 至 nk 的路径。这条路径的长度是k-1。
6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
8）树的深度。树中所有结点的最大层数称为树的深度。
9）树的度。树中各结点度的最大值称为该树的度，叶子结点的度为0。
10）满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。
11）完全二叉树。一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
二叉树的基本性质如下：
性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
性质2：一棵深度为k的二叉树中，最多具有2k-1个结点，最少有k个结点。
性质3：对于一棵非空的二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个，即如果叶子结点数为n0，度数为2的结点数为n2，则有n0=n2+1
性质4：具有n个结点的完全二叉树的深度为「log2 n」+1。
性质 5：对于具有 n 个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：①如果i＞1，则序号为i的结点的双亲结点的序号为i/2（其中“/”表示整除）；如果i=1，则序号为i的结点是根结点，无双亲结点。②如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i＞n，则序号为i的结点无左孩子。③如果2i+1≤n，则序号为i的结点的右孩子结点的序号为2i+1；如果2i+1＞n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i-1）/2，左孩子的编号为2i+1，右孩子的编号为2i+2。
/**
* @author 龙御修
* @create 2022-05-01 17:04
*/
public class ArraystreeDemo {
/*把有序数组装换为二叉树*/
public static BiTNode arraytotree(int[] arr,int start,int end){
BiTNode root=null;
if(end>=start){
root=new BiTNode();
int mid=(start+end+1)/2;
//树的根节点为素组中间的元素
root.data=arr[mid];
//递归的用左半部分数组构成root的左子树
root.lchild=arraytotree(arr,start,mid-1);
//递归的用有右半部分数组构成root的右子树
root.rchild=arraytotree(arr,mid+1,end);
}
else {
root=null;
}
return root;
}
/*用中序遍历的方式打印出二叉树结点的内容*/
public static void printTreeMidOrder(BiTNode root){
if(root==null)return;
//遍历root结点的左子树
if(root.lchild!=null)
printTreeMidOrder(root.lchild);
//遍历root结点
System.out.print(root.data+" ");
//遍历root结点的右子树
if(root.rchild!=null)
printTreeMidOrder(root.rchild);
}
public static void main(String[] args) {
int[] arr= {1,2,3,4,5,6,7,8,9,10};
System.out.print("数组：");
for(int i=0;i题目描述：给定一棵二叉树，它的每个结点都是正整数或负整数，如何找到一棵子树，使得它所有结点的和最大？
/**
* @author 龙御修
* @create 2022-05-02 17:10
*/
public class SumMaxTree {
private static int maxSum=Integer.MIN_VALUE;
/*求最大子树*/
public static int findMaxSubTree(BiTNode root,BiTNode maxRoot){
if(root==null){
return 0;
}
/*求root左子树所有结点的和*/
int lmax=findMaxSubTree(root.lchild,maxRoot);
/*求root右子树所有结点的和*/
int rmax=findMaxSubTree(root.rchild,maxRoot);
int sum=lmax+rmax+root.data;
/*以root为根的子树的和大于前面求出的最大值*/
if(sum>maxSum){
maxSum=sum;
maxRoot.data=root.data;
}
/*返回以root未根结点的子树的所有结点的和*/
return sum;
}
/*构造二叉树*/
public static BiTNode constructTree(){
BiTNode root=new BiTNode();
BiTNode node1=new BiTNode();
BiTNode node2=new BiTNode();
BiTNode node3=new BiTNode();
BiTNode node4=new BiTNode();
root.data=6;
node1.data=3;
node2.data=-7;
node3.data=-1;
node4.data=9;
root.lchild=node1;
root.rchild=node2;
node1.lchild=node3;
node1.rchild=node4;
node2.lchild=node2.rchild=node3.lchild=node3.rchild=node4.lchild=node4.rchild=null;
return root;
}
public static void main(String[] args) {
BiTNode root=constructTree();
BiTNode maxRoot=new BiTNode();
findMaxSubTree(root,maxRoot);
System.out.println("最大子树和为："+maxSum);
System.out.println("对应子树根结点为："+maxRoot.data);
}
}
class BiTNode{
int data;
BiTNode lchild,rchild;
}题目描述：
两棵二叉树相等是指这两棵二叉树有着相同的结构，并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等？
/**
* @author 龙御修
* @create 2022-05-02 17:37
*/
public class JudgeTwoTree {
/*判断两棵二叉树相等*/
public static boolean isEqual(BiTNode root1,BiTNode root2){
if(root1==null&&root2==null)
return true;
if(root1==null||root2==null)
return false;
if(root1.data== root2.data)
return isEqual(root1.lchild,root2.lchild)&&isEqual(root1.rchild,root2.rchild);
else
return false;
}
/*构造二叉树 */
public static BiTNode constructTree(){
BiTNode root=new BiTNode();
BiTNode node1=new BiTNode();
BiTNode node2=new BiTNode();
BiTNode node3=new BiTNode();
BiTNode node4=new BiTNode();
root.data=6;
node1.data=3;
node2.data=-7;
node3.data=-1;
node4.data=9;
root.lchild=node1;
root.rchild=node2;
node1.lchild=node3;
node1.rchild=node4;
node2.lchild=node2.rchild=node3.lchild=node3.rchild=node4.lchild=node4.rchild=null;
return root;
}
public static void main(String[] args) {
BiTNode root1=constructTree();
BiTNode root2=constructTree();
boolean equal=isEqual(root1,root2);
if(equal)
System.out.println("这两棵数相等");
else
System.out.println("这两棵树不相等");
}
}
class BiTNode{
int data;
BiTNode lchild,rchild;
}题目描述：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整结点的指向，例如下图。
/**
* @author 龙御修
* @create 2022-05-02 17:53
*/
public class TreetoLinkedlist {
private static BiTNode pHead = null;//双向链表头结点
private static BiTNode pEnd = null;//双向链表尾结点
/*把二叉树转换为双向链表*/
public static void inOrderBSTree(BiTNode root) {
if (null == root) {
return;
}
/*转换root的左子树*/
inOrderBSTree(root.lchild);
root.lchild = pEnd;/*使当前结点的左子树指向双向链表中左后一个结点*/
if (null == pEnd) {//双向链表为空，当前遍历的结点为双向链表是头结点
pHead = root;
} else {//使双向链表中最后一个结点的右子树指向当前结点
pEnd.rchild = root;
}
pEnd = root;//将当前结点设为双向链表中最后一个结点
//转换root的右子树
inOrderBSTree(root.rchild);
}
/*把有序数组装换为二叉树*/
public static BiTNode arraytotree(int[] arr,int start,int end){
BiTNode root=null;
if(end>=start){
root=new BiTNode();
int mid=(start+end+1)/2;
//树的根节点为素组中间的元素
root.data=arr[mid];
//递归的用左半部分数组构成root的左子树
root.lchild=arraytotree(arr,start,mid-1);
//递归的用有右半部分数组构成root的右子树
root.rchild=arraytotree(arr,mid+1,end);
}
else {
root=null;
}
return root;
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5,6,7};
BiTNode root;
root=arraytotree(arr,0,arr.length-1);
inOrderBSTree(root);
BiTNode cur;
System.out.print("转换后双向链表正向遍历");
for(cur=pHead;cur!=null;cur=cur.rchild)
System.out.print(cur.data+" ");
System.out.println();
System.out.print("装换后双向链表逆向遍历");
for(cur=pEnd;cur!=null;cur=cur.lchild)
System.out.print(cur.data+" ");
}
}
class BiTNode{
int data;
BiTNode lchild,rchild;
}题目描述：
对于一棵给定的排序二叉树，求两个结点的共同父结点，如在下图中，结点 1 和结点 5的共同父结点为3。
import java.util.Stack;
/**
* @author 龙御修
* @create 2022-05-02 18:28
*/
public class personTree {
/*把有序数组装换为二叉树*/
public static BiTNode arraytotree(int[] arr, int start, int end) {
BiTNode root = null;
if (end >= start) {
root = new BiTNode();
int mid = (start + end + 1) / 2;
//树的根节点为素组中间的元素
root.data = arr[mid];
//递归的用左半部分数组构成root的左子树
root.lchild = arraytotree(arr, start, mid - 1);
//递归的用有右半部分数组构成root的右子树
root.rchild = arraytotree(arr, mid + 1, end);
} else {
root = null;
}
return root;
}
/*获取二叉树从根结点root到node结点的路径*/
private static boolean genPathFromRoot(BiTNode root, BiTNode node, Stack s) {
if (root == null)
return false;
if (root == node) {
s.push(root);
return true;
}
/*如果node结点在root结点的左子树或右子树上，那么root就是node的祖先结点，把它加到栈里*/
if (genPathFromRoot(root.lchild, node, s) || genPathFromRoot(root.rchild, node, s)) {
s.push(root);
return true;
}
return false;
}
/*查找二叉树中两个结点最近的共同父结点*/
public static BiTNode FindParentNode(BiTNode root,BiTNode node1,BiTNode node2){
Stack stack1=new Stack<>();/*保存从root到node1的路径*/
Stack stack2=new Stack<>();/*保存从root到node2的路径*/
//获取从root到node1的路径
genPathFromRoot(root,node1,stack1);
//获取从root到node2的路径
genPathFromRoot(root,node2,stack2);
BiTNode commomParent=null;
/*获取靠近node1和node2的父结点*/
while (stack1.peek()==stack2.peek()){
commomParent=stack1.peek();
stack1.pop();
stack2.pop();
}
return commomParent;
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5,6,7,8,9,10};
BiTNode root;
root=arraytotree(arr,0, arr.length-1);
BiTNode node1=root.lchild.lchild.lchild;
BiTNode node2=root.lchild.rchild;
BiTNode res=null;
res=FindParentNode(root,node1,node2);
if(res!=null)
System.out.print(node1.data+"与"+node2.data+"的最近公共父结点为："+res.data);
else
System.out.println("没有共同的父结点");
}
}
class BiTNode{
int data;
BiTNode lchild,rchild;
} 题目描述：
给定一个二叉树根结点，复制该树，返回新建树的根结点。
/**
* @author 龙御修
* @create 2022-05-02 19:46
*/
public class CopyTree {
public static BiTNode createDupTree(BiTNode root){
if(root==null)
return null;
//二叉树根结点
BiTNode dupTree=new BiTNode();
dupTree.data= root.data;
//复制左子树
dupTree.lchild=createDupTree(root.lchild);
//复制右子树
dupTree.rchild=createDupTree(root.rchild);
return dupTree;
}
public static BiTNode constructTree(){
BiTNode root=new BiTNode();
BiTNode node1=new BiTNode();
BiTNode node2=new BiTNode();
BiTNode node3=new BiTNode();
BiTNode node4=new BiTNode();
root.data=6;
node1.data=3;
node2.data=-7;
node3.data=-1;
node4.data=9;
root.lchild=node1;
root.rchild=node2;
node1.lchild=node3;
node1.rchild=node4;
node2.lchild=node2.rchild=node3.lchild=node3.rchild=node4.lchild=node4.rchild=null;
return root;
}
public static void printTreeMidOrder(BiTNode root){
if(root==null)return;
//遍历root结点的左子树
if(root.lchild!=null)
printTreeMidOrder(root.lchild);
//遍历root结点
System.out.print(root.data+" ");
//遍历root结点的右子树
if(root.rchild!=null)
printTreeMidOrder(root.rchild);
}
public static void main(String[] args) {
BiTNode root1=constructTree();
BiTNode root2=constructTree();
System.out.print("原始二叉树中序遍历：");
printTreeMidOrder(root1);
System.out.println();
System.out.print("新的二叉树中序遍历： ");
printTreeMidOrder(root2);
}
}
class BiTNode{
int data;
BiTNode lchild,rchild;
}题目描述：
反向 DNS 查找指的是使用 Internet IP 地址查找域名。例如，如果在浏览器中输入74.125.200.106，它会自动重定向到google.in。如何实现反向DNS查找缓存？
/**
* @author 龙御修
* @create 2022-05-02 20:12
*/
public class DNSFind {
public static void main(String[] args) {
String[] ipAdds={"10.57.11.127","121.57.61.129","66.125.100.103"};
String[] url={"www.samsung.com","www.samsung.net","www.google.in"};
int n= ipAdds.length;
DNSCache cache=new DNSCache();
/*把IP地址和对应的URL插入到Trie树中*/
for(int i=0;i"+res_url);
else
System.out.println("没有找到对应的URL\n");
}
}
class DNSCache{
/*IP地址最多有11个不同的字符*/
private final int CHAR_COUNT=11;
/*IP地址最大的长度*/
private TrieNode root=new TrieNode();
public class TrieNode{
boolean isLeaf;
String url;
TrieNode[] child;//CHAR_COUNT
public TrieNode(){
this.isLeaf=false;
this.url=null;
this.child=new TrieNode[CHAR_COUNT];
for(int i=0; i
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）