网站加友情链接的好处,宁安市建设局网站,网站简繁体转换.rar,淄博网站建设网宽目录
一、树
1、初识树
2、树的一些概念
3、树的表示形式
二、二叉树
1、初识二叉树
2、两种特殊的二叉树
3、二叉树的性质
4、二叉树的遍历
5、实现一棵二叉树
6、二叉树题目#xff08;没代码的后面会给补上#xff09; 一、树
1、初识树 #xff08;1…目录
一、树
1、初识树
2、树的一些概念
3、树的表示形式
二、二叉树
1、初识二叉树
2、两种特殊的二叉树
3、二叉树的性质
4、二叉树的遍历
5、实现一棵二叉树
6、二叉树题目没代码的后面会给补上 一、树
1、初识树 1根节点没有前驱。 2子树的根节点只有一个前驱可以有0个或多个后继。 3每个子树都是不相交的子树之间不能有交集。 4N个结点有N-1条边 2、树的一些概念 1、结点的度这个结点有几个子树度就为几 2、树的度所有结点度的最大值就是树的度 3、根结点没有前驱的结点 4、叶子结点或终端结点没有后继的结点没有子树即度为0的结点 5、分支结点或非终端结点有后继的结点有子树即度不为0的结点 6、双亲结点或父结点结点的前驱就是该结点的父结点 7、孩子结点或子结点结点的后继就是该结点的子结点 8、兄弟结点具有相同父结点的结点互为兄弟结点 9、堂兄弟结点父结点在同一层的结点互为堂兄弟结点 10、结点的祖先从根结点到该结点一路上经过的所有结点都是该结点的祖先如根结点是除自身外所有结点的祖先 11、子孙该结点后面的所有结点都是该结点的子孙如除根结点外所有结点都是根结点的子孙 12、结点的层次根为第1层以此类推 13、深度该结点的层次就是深度 14、树的高度树中结点的最大层次就是树的高度 15、森林由mm0棵互不相交的树组成的集合称为森林空树也叫森林 3、树的表示形式
树可以有双亲表示法孩子表示法孩子双亲表示法孩子兄弟表示法等等
二、二叉树
1、初识二叉树 1二叉树是树 2二叉树的每个根结点都只有两棵子树分别为左子树和右子树 3二叉树也可以是空树 4二叉树的度 2所以二叉树的结点个数 度为0的结点个数度为1的结点个数度为2的结点个数 2、两种特殊的二叉树
1满二叉树 除叶子结点外结点的度都为2结点总数为(2^k)-1k为树的高度 2完全二叉树 从上到下从左到右中间不少结点。 满二叉树是特殊的完全二叉树。 完全二叉树中度为1的结点个数 要么为0要么为1 —— 结点总数是偶数时度为1的结点个数为 1结点总数是奇数时度为1的结点个数为 0 3、二叉树的性质 1、二叉树的第 k 层最多有 2^(k-1) 个结点空树除外 2、深度为 k 的二叉树最多有(2^k)-1个结点 3、任意一棵二叉树叶子结点的个数 比 度为2的结点的个数 多 1 4、n个结点的完全二叉树深度k为(2^k) -1 nk为 log以2为底n1的对数向上取整 5、完全二叉树 若父结点下标为 i则 左孩子下标为2*i1右孩子下标为2*i2 若子结点下标为 i则父结点下标为i-1/2 题目
1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为B、 200 1991
2.在具有 2n 个结点的完全二叉树中叶子结点个数为A、n2n n01n0-1
3.一个具有767个节点的完全二叉树其叶子节点个数为B、384767 n00n0-1
4、二叉树的遍历
前序遍历根左子树右子树
中序遍历左子树根右子树
后序遍历左子树右子树根
层序遍历从上到下从左到右
如写出下面这棵二叉树的前序遍历中序遍历后序遍历层序遍历的结果 前序遍历A B D E H C F G 中序遍历D B E H A F C G 后序遍历D H E B F G C A 层序遍历A B C D E F G H 题目
1、设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为(D)
A: adbce B: decab C: debac D: abcde 后序遍历从后往前每一个结点都是根结点。拿着根结点去中序遍历里看根结点的左边属于左子树的结点根结点的右边属于右子树的结点。 如后序遍历从后往前第一个结点就是整棵树的根结点 a然后看中序遍历则b 属于左子树的结点dce 属于右子树的结点。然后再看后序遍历从后往前第二个结点以此类推。 由此题引出两个问题
问题一如果只给一个遍历能否创建一棵二叉树 不能。因为有可能存在两棵不同的树某一个遍历是一样的。 问题二如果只给前序遍历和后序遍历能否创建一棵二叉树 不能。前序遍历和后序遍历都是只能确定根的位置但不能确定左子树或右子树。 5、实现一棵二叉树
二叉树的存储结构物理结构有顺序存储和链式存储
这里我们使用孩子表示法来实现一个链式存储结构的二叉树。 1、前序遍历 2、中序遍历 3、后序遍历
4、获取树中结点的个数 5、获取叶子结点的个数 6、获取第 k层 结点的个数
7、获取二叉树的高度
8、获取第k层的所有结点有点 带返回值的前序遍历 和 获取第 k层 结点的个数 的结合版
9、找到值为value的元素
10、层序遍历和层序遍历相关的想到用 队列用队列会比较方便
11、判断这棵树是不是完全二叉树用 队列 public class MyBinaryTree {static class TreeNode{public char val;public TreeNode leftTree;//存储左子树的引用public TreeNode rightTree;//存储右子树的引用public TreeNode(char val){this.val val;}}//创建一棵树public TreeNode createTree(){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.leftTree B;A.rightTree C;B.leftTree D;B.rightTree E;C.leftTree F;C.rightTree G;E.rightTree H;return A;}//前序遍历public void preOrder(TreeNode root){if(root null){return;}System.out.print(root.val );preOrder(root.leftTree);preOrder(root.rightTree);}//带返回值public ListCharacter preorderTraversal(TreeNode root) {//子问题思路先放根然后放左子树然后放右子树ListCharacter list new ArrayList();//递归的终止条件if(root null){return list;}list.add(root.val);list.addAll(preorderTraversal(root.leftTree));list.addAll(preorderTraversal(root.rightTree));return list;}//中序遍历public void inOrder(TreeNode root){if(root null){return;}inOrder(root.leftTree);System.out.print(root.val );inOrder(root.rightTree);}//后序遍历public void postOrder(TreeNode root){if(root null){return;}postOrder(root.leftTree);postOrder(root.rightTree);System.out.print(root.val );}//获取树中结点的个数public int size(TreeNode root){//左子树结点的个数右子树结点的个数1//递归的终止条件if(root null){return 0;}return size(root.leftTree)size(root.rightTree)1;}//获取叶子结点的个数public int getLeafNodeCount(TreeNode root){//左子树叶子结点的个数右子树叶子结点的个数if(root null){return 0;}//满足下面条件的就是叶子结点,递归的终止条件if(root.leftTree null root.rightTree null){return 1;}return getLeafNodeCount(root.leftTree) getLeafNodeCount(root.rightTree);}//获取第 k层 结点的个数public int getKLevelNodeCount(TreeNode root,int k){//第k层结点的个数 左子树第k-1层结点的个数右子树第k-1层结点的个数if(k 0){throw new KWrongFulException(k不合法异常);}//如果k大于树的高度k还没减到0root先变成null返回0//下面两个都算循环的终止条件if(root null){return 0;}if(k 1){return 1;}return getKLevelNodeCount(root.leftTree,k-1)getKLevelNodeCount(root.rightTree,k-1);}//获取二叉树的高度public int getHeight(TreeNode root){//左子树的高度右子树的高度的最大值 1if(root null){return 0;}int leftHeight getHeight(root.leftTree);int rightHeight getHeight(root.rightTree);return leftHeight rightHeight ? leftHeight1 : rightHeight1;}//获取第 k 层的所有结点//有点像 带返回值的前序遍历 和 获取第 k层 结点的个数 的结合public ListCharacter KLevel(TreeNode root,int k){ListCharacter list new LinkedList();if(root null){return list;}//把 第 k 层的每一个结点都 add 进 list返回给父结点if(k 1){list.add(root.val);return list;}//父结点接收到两个子结点返回的 listadd到自己的list里list.addAll(KLevel(root.leftTree,k-1));list.addAll(KLevel(root.rightTree,k-1));//然后返回给他的父结点于是层层递进最后根结点的list里 放的就是 第k层 的所有结点return list;}//找到值为value的元素public TreeNode find(TreeNode root,char val){//先找根然后找左子树然后找右子树找到就返回找不到返回null//下面两个都是递归的终止条件if(root null){return null;}if(root.val val){return root;}TreeNode ret1 find(root.leftTree,val);//如果 ret1 里面不是空说明找到了//如果 ret1 里面是空说明没找到if (ret1 ! null){return ret1;}TreeNode ret2 find(root.rightTree,val);if (ret2 ! null){return ret2;}return null;}//层序遍历用到队列先进先出//层序遍历不用递归比较方便本来就是按顺序从上到下从左到右输出的呀// 不像前序中序和后序遍历必须得递归public void levelOrder(TreeNode root){QueueTreeNode queue new LinkedList();if(root null){return;}queue.offer(root);while(!queue.isEmpty()){TreeNode ret queue.poll();System.out.print(ret );if(ret.leftTree ! null){queue.offer(ret.leftTree);}if(ret.leftTree ! null){queue.offer(ret.rightTree);}}}//有返回值的层序遍历用到队列比较方便//难点在如何确定每一层这里我们用到了队列中的size//每一轮都要定义一个sizepublic ListListCharacter levelOrderTraversal(TreeNode root){ListListCharacter tmp new ArrayList();QueueTreeNode queue new LinkedList();if(root null){return tmp;}queue.offer(root);while(!queue.isEmpty()){int size queue.size();ListCharacter list new ArrayList();while(size 0) {TreeNode ret queue.poll();size--;list.add(ret.val);if (ret.leftTree ! null) {queue.offer(ret.leftTree);}if (ret.rightTree ! null) {queue.offer(ret.rightTree);}}tmp.add(list);}return tmp;}//判断这棵树是不是完全二叉树用队列public boolean isCompleteTree(TreeNode root){QueueTreeNode queue new LinkedList();if(root null){return true;}queue.offer(root);while(!queue.isEmpty()){TreeNode ret queue.peek();if(ret null){break;}queue.poll();queue.offer(ret.leftTree);queue.offer(ret.rightTree);}//走到这队列里要么都是null要么除了null还有结点后者说明不是完全二叉树while(!queue.isEmpty()){TreeNode ret queue.poll();if(ret ! null){return false;}}return true;}
}6、二叉树题目没代码的后面会给补上 1、判断两棵树相不相等
2、判断其中一棵树是不是另一棵树的子树
3、翻转二叉树
4、判断是不是平衡二叉树
5、判断两棵二叉树是不是镜像对称
6、判断是不是轴对称二叉树
7、二叉树的层序遍历
8、二叉树的构建和遍历
9、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
10、二叉搜索树转换成排序双向链表
11、二叉树前序非递归遍历实现
12、二叉树中序非递归遍历实现
13、二叉树后序非递归遍历实现
14、根据一棵树的前序遍历与中序遍历构造二叉树
15、根据一棵树的中序遍历与后序遍历构造二叉树
16、二叉树创建字符串1判断两棵树是否相同 链接
//时间复杂度O(min(m,n))其中 m和n 分别是两个二叉树的结点数
public boolean isSameTree(TreeNode p, TreeNode q) {//先判断根一样不再判断左子树一样不再判断右子树一样不只有全一样(结构和值都一样)才返回true//如果都是空树if(p null q null){return true;}//如果一个是空树一个不是if((p null q ! null) || (p ! null q null)){return false;}//走到这则两个都不是空树//值不相等if(p.val ! q.val){return false;}//走到这既不是空树根的值也相等return isSameTree(p.left,q.left) isSameTree(p.right,q.right);
}
2判断其中一棵树是不是另一棵树的子树 链接
/*** 2、判断其中一棵树是不是另一棵树的子树* 时间复杂度O(m*n)其中 m和n 分别是两个二叉树的结点数*/public boolean isSubtree(TreeNode root, TreeNode subRoot) {//题目中已经给出了两棵树都不是空树//如果一直没有匹配root就会一直root.leftroot会为空if(root null || subRoot null){return false;}//先判断subRoot是否和root相等if(isSameTree(root,subRoot)) return true;//再判断subRoot是否是root的左子树的子树if(isSubtree(root.left,subRoot)) return true;//再判断subroot是否是root的右子树的子树if(isSubtree(root.right,subRoot)) return true;return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//先判断根一样不再判断左子树一样不再判断右子树一样不只有全一样(结构和值都一样)才返回true//如果都是空树if(p null q null){return true;}//如果一个是空树一个不是if((p null q ! null) || (p ! null q null)){return false;}//走到这则两个都不是空树//值不相等if(p.val ! q.val){return false;}//走到这既不是空树根的值也相等return isSameTree(p.left,q.left) isSameTree(p.right,q.right);}
3翻转二叉树 链接
public TreeNode invertTree(TreeNode root) {//先翻转根结点的左子树和右子树再翻转左子树的左子树和右子树再翻转右子树的左子树和右子树if(root null){return null;}TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;
}
4判断是不是平衡二叉树 链接
//判断是不是平衡二叉树时间复杂度O(n)public boolean isBalanced(TreeNode root) {//平衡二叉树每棵子树的高度差都要 1if(root null){return true;}int ret height(root);if(ret -1){return false;}return true;}//求二叉树的高度时间复杂度是O(n)//求根结点高度的时候其实已经求了所有结点的高度如果发现左树右树高度差大于1说明已经不平衡了就返回-1//否则就返回左树右树高度最大值1//所以我们需要在每次获得左树和右树高度的时候都接收判断一下如果发现接收到的是-1说明已经出现了不平衡//如果一直没有接收到-1说明这个二叉树的每棵子树都是平衡的所以这棵二叉树是高度平衡的二叉树。//求二叉树的高度public int height(TreeNode root){if(root null){return 0;}//求左子树的高度int leftH height(root.left);if(leftH -1){return -1;}//求右子树的高度int rightH height(root.right);if(rightH -1){return -1;}//如果左右子树的高度差 1返回左右子树高度的最大值1//如果左右子树的高度差 1返回-1说明已经出现不平衡了if(Math.abs(leftH - rightH) 1){return Math.max(leftH,rightH) 1;}else{return -1;}}
5判断两棵树是不是镜像对称
public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){//如果两个都是空树if(leftTree null rightTree null){return true;}//如果一个是空树一个不是if((leftTree null rightTree ! null) || (leftTree ! null rightTree null)){return false;}//到这两个都不是空树if(leftTree.val ! rightTree.val){return false;}//到这两个都不是空树且根的值相同return isMirrorSymmetry(leftTree.left,rightTree.right) isMirrorSymmetry(leftTree.right,rightTree.left);
}
6判断是不是轴对称二叉树 链接
public boolean isSymmetric(TreeNode root) {if(root null){return true;}//从第二层开始比较左子树和右子树是否是镜像的return isMirrorSymmetry(root.left,root.right);}//先比较根是否是镜像的再比较子树是否是镜像的public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){//如果两个都是空树if(leftTree null rightTree null){return true;}//如果一个是空树一个不是if((leftTree null rightTree ! null) || (leftTree ! null rightTree null)){return false;}//到这两个都不是空树if(leftTree.val ! rightTree.val){return false;}//到这两个都不是空树且根的值相同return isMirrorSymmetry(leftTree.left,rightTree.right) isMirrorSymmetry(leftTree.right,rightTree.left);}
7二叉树的层序遍历 链接
//有返回值的层序遍历用到队列比较方便
//难点在如何确定每一层这里我们用到了队列中的size
//每一轮都要定义一个sizepublic ListListInteger levelOrder(TreeNode root) {ListListInteger tmp new ArrayList();QueueTreeNode queue new LinkedList();if(root null){return tmp;}queue.offer(root);while(!queue.isEmpty()){int size queue.size();ListInteger list new ArrayList();while(size 0) {TreeNode ret queue.poll();size--;list.add(ret.val);if (ret.left ! null) {queue.offer(ret.left);}if (ret.right ! null) {queue.offer(ret.right);}}tmp.add(list);}return tmp;
}
8二叉树的构建和遍历 链接
public class Main {static class TreeNode{public char val;public TreeNode leftTree;//存储左子树的引用public TreeNode rightTree;//存储右子树的引用public TreeNode(char val){this.val val;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNextLine()) { String str scanner.nextLine();//str里存的就是读入的字符串//首先遍历字符串拿到字符串中的每个元素//并创建结点通过前序遍历构造一棵二叉树TreeNode root createTree(str);//然后再中序遍历输出inOrder(root);}}//通过前序遍历构造二叉树public static int i 0;public static TreeNode createTree(String str){TreeNode root null;//通过i拿到字符串中的每个字符char ch str.charAt(i);i;if(ch #){return null;}//把拿到的元素创建成结点root new TreeNode(ch);root.leftTree createTree(str);root.rightTree createTree(str);return root; }//中序遍历输出public static void inOrder(TreeNode root){if(root null){return;}inOrder(root.leftTree);System.out.print(root.val );inOrder(root.rightTree);}
}
9给定一个二叉树, 找到该树中两个指定节点的最近公共祖先 链接 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null){return null;}// p 和 q 其中有一个是rootif(p root || q root){return root;}// p 和 q 分别在 root 的两侧// p 和 q 都在 root 的左侧 或 root 的右侧TreeNode ret1 lowestCommonAncestor(root.left,p,q);TreeNode ret2 lowestCommonAncestor(root.right,p,q);if(ret1 ! null ret2 ! null){return root;}else if(ret1 ! null){return ret1;}else if(ret2 ! null){return ret2;}else{return null;}
}
10二叉搜索树转换成排序双向链表 链接
public TreeNode convert(TreeNode pRootOfTree) {//二叉搜索树根左边的比根小根右边的比根大//中序遍历二叉搜索树是有序的是从小到大的//所以转换成排序的双向链表采用中序遍历的方法if(pRootOfTree null){return null;}convertChild(pRootOfTree);TreeNode head pRootOfTree;//链表的头就是二叉搜素树最左边的那个结点while(head.left ! null){head head.left;}return head;}public TreeNode prev null;public void convertChild(TreeNode pRoot){if(pRoot null){return;}convertChild(pRoot.left);if(prev ! null){prev.right pRoot;}pRoot.left prev;prev pRoot;convertChild(pRoot.right);}
11二叉树前序非递归遍历实现 链接
public TreeNode cur null;public ListInteger preorderTraversal(TreeNode root) {StackTreeNode stack new Stack();ListInteger list new ArrayList();//用到栈//前序遍历根左右。往左走一直入栈只有这个节点没用了才能出栈。if(root null){return list;}cur root;while(cur ! null || !stack.empty()){while(cur ! null){stack.push(cur);list.add(cur.val);cur cur.left;}//cur 等于空说明cur的左走完了此时栈顶元素就是cur//根和左走完了此时才能弹出栈顶元素因为直到这时栈顶元素才没用了cur stack.pop();cur cur.right;}return list;}
12二叉树中序非递归遍历实现 链接
13二叉树后序非递归遍历实现 链接
14根据一棵树的前序遍历与中序遍历构造二叉树 链接
15根据一棵树的中序遍历与后序遍历构造二叉树 链接
16二叉树创建字符串 链接
