做ppt素材的网站,月嫂网站模板,广西代理网站建设公司,开发一个app需要哪些人员文章目录 树概念及结构树的概念树的相关概念树的表示形式树的应用 二叉树概念及结构概念两种特殊的二叉树二叉树的性质二叉树的存储二叉树的基本操作二叉树的遍历前中后序遍历递归实现二叉树的基本操作 二叉树相关oj题 树概念及结构
树的概念
树是一种非线性的数据结构#… 文章目录 树概念及结构树的概念树的相关概念树的表示形式树的应用 二叉树概念及结构概念两种特殊的二叉树二叉树的性质二叉树的存储二叉树的基本操作二叉树的遍历前中后序遍历递归实现二叉树的基本操作 二叉树相关oj题 树概念及结构
树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
有一个特殊的结点称为根结点根节点没有前驱结点除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m m)又是一棵子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。一棵n个结点的树有n-1条边
注意树形结构中子树之间不能有交集,除了根结点外每个结点有且仅有一个父结点否则就不是树形结构
树的相关概念 结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6叶子结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等节点为叶结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点若一个结点含有父结点则这个结点称为其父结点的子结点 如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始根为第1层根的子结点为第2层以此类推树的深度树从根结点开始往下数叶子结点所在的最大层数,也就是树中结点的最大层次 如上图树的深度为4树的高度:深度定义是从上往下的高度定义是从下往上的。其实不用在意这个反正树的深度高度怎么数都一样的。可以看这篇非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林
树的表示形式
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
}树的应用
文件系统管理目录和文件
二叉树概念及结构
概念
一棵二叉树是结点的一个有限集合该集合
或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 从上图可以看出
二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
对于任意的二叉树都是由以下几种情况复合而成的
两种特殊的二叉树
满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是 2 k 2^k 2k-1 则它就是满二叉树。完全二叉树: 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。从上到下,从左向右依次存储。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质
若规定根结点的层数为1则一棵非空二叉树的第i层上最多有 2 i − 1 2^{i-1} 2i−1(i0)个结点若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 2 k − 1 2^k-1 2k−1 (k0)对任何一棵二叉树, 如果其叶结点个数为 n 0 n_0 n0, 度为2的非叶结点个数为 n 2 n_2 n2,则有 n 0 n_0 n0 n 2 n_2 n21,也就是度为0的结点永远比度为2的结点多一个 设度为1的非叶结点个数为n1 一棵n个结点的树有n-1条边( n 1 n_1 n12 n 2 n_2 n2 n-1) n 0 n_0 n0 n 1 n_1 n1 n 2 n_2 n2n 得出 n 0 n_0 n0 n 2 n_2 n21 具有n个结点的完全二叉树的深度k为 l o g 2 ( n 1 ) log_2(n1) log2(n1)向上取整对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有
若i0父结点序号(i-1)/2i0,则i为根结点编号无父结点若2i1n左孩子序号2i1若2i2n右孩子序号2i2 练习题 1.某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 n 0 n_0 n0 n 2 n_2 n21200,选B 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 2n n 0 n_0 n0 n 1 n_1 n1 n 2 n_2 n2 n 1 n_1 n11 n 0 n_0 n0 n 2 n_2 n21
所以 n 0 n_0 n0n,选A 3.一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 767 n 0 n_0 n0 n 2 n_2 n2 n 0 n_0 n0 n 2 n_2 n21
得出 n 0 n_0 n0384,选B 4.一棵完全二叉树的节点数为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 2 9 2^9 29512 ; 2 10 2^{10} 2101024 51253111024 所以9 l o g 2 ( 531 1 ) log_2(5311) log2(5311)10 向上取整选10,也就是B
二叉树的存储
二叉树的链式存储是通过一个一个的节点引用起来的常见的表示方式有二叉和三叉表示方式具体如下
// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树Node parent; // 当前节点的根节点
}二叉树的基本操作
二叉树的遍历
前中后序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——根结点—根的左子树—根的右子树。 中序遍历(Inorder Traversal)——根的左子树—根节点—根的右子树。 后序遍历(Postorder Traversal)——根的左子树—根的右子树—根节点。
层序遍历
自上而下自左至右逐层访问树的结点 练习题 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为() A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA ABDHECFG,选A 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为() A: E B: F C: G D: H 看先序遍历第一个,选A 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为() A: adbce B: decab C: debac D: abcde 选D 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为 ( ) A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF 选A
前中后序遍历递归实现
定义结点
static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}前序遍历
public void preOrder(TreeNode root) {if(root null) {return;//空树是不需要遍历的}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}中序遍历
public void inOrder(TreeNode root) {if(root null) {return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}后序遍历
public void postOrder(TreeNode root) {if(root null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}二叉树的基本操作
1.获取树中节点的个数
用递归外的变量存储个数,采用前序遍历的方法,前序遍历是打印,这次是计数 public static int nodeSize;public void size(TreeNode root) {if(root null) {return;}nodeSize;size(root.left);size(root.right);}子问题思路 public int size(TreeNode root) {if(root null) {return 0;}int count size(root.left) size(root.right)1;return count;}2.获取叶子节点的个数
用递归外的变量存储个数,也是前序遍历的方法 public int leafSize;public void getLeafNodeCount(TreeNode root) {if(root null) {return;}if(root.left null root.right null) {leafSize;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}子问题思路 public int getLeafNodeCount2(TreeNode root) {if(root null) {return 0;} if(root.left null root.right null) {return 1;}return getLeafNodeCount2(root.left) getLeafNodeCount2(root.right);}获取第K层节点的个数 public int getKLevelNodeCount(TreeNode root,int k) {if(root null) {return 0;}if(k 1) {return 1;}return getKLevelNodeCount(root.left,k-1)getKLevelNodeCount(root.right,k-1);}4.获取二叉树的深度(oj题链接)
推荐这种 public int maxDepth(TreeNode root) {if(root null) {return 0;}int leftHeight maxDepth(root.left);int rightHeight maxDepth(root.right);return Math.max(leftHeight,rightHeight) 1;}不推荐,没有保存leftHeight和rightHeight,会重复计算 public int maxDepth(TreeNode root) {if(root null) {return 0;}return (maxDepth(root.left) maxDepth(root.right)? maxDepth(root.left) : maxDepth(root.right)) 1;}5.检测值为value的元素是否存在 public TreeNode find(TreeNode root,int val) {if(root null) return null;if(root.val val) return root;TreeNode leftVal find(root.left,val);if(leftVal ! null) {return leftVal;}TreeNode rightVal find(root.right,val);if(rightVal ! null) {return rightVal;}return null;}二叉树相关oj题
检查两颗树是否相同oj链接
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p null q null) return true;if (p null || q null) return false;if(p.val ! q.val) return false;return isSameTree(p.left,q.left)isSameTree(p.right,q.right);}
}另一颗树的子树oj链接
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p null q null) return true;if (p null || q null) return false;if(p.val ! q.val) return false;return isSameTree(p.left,q.left)isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(subRoot null) return true;if(root null) return false;if(isSameTree(root,subRoot)) {return true;}if(isSubtree(root.left,subRoot)) {return true;}if(isSubtree(root.right,subRoot)) {return true;}return false;}
}翻转二叉树oj链接
class Solution {public TreeNode invertTree(TreeNode root) {if(root null) return null;//if(root.left null root.right null) return root;TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;}
}判断一颗二叉树是否是平衡二叉树oj链接
(1) 时间复杂度(O( n 2 n^2 n2))
class Solution {public boolean isBalanced(TreeNode root) {if(rootnull) {return true;}int leftH getHeight(root.left);int rightH getHeight(root.right);if(Math.abs(leftH-rightH)2isBalanced(root.left) isBalanced(root.right)) {return true;} return false;}public int getHeight(TreeNode root) {if(rootnull) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.max(leftHeight,rightHeight)1; }
}(2)
class Solution {public boolean isBalanced(TreeNode root) {if(rootnull) {return true;}return getHeight(root) 0;}public int getHeight(TreeNode root) {if(rootnull) {return 0;}int leftHeight getHeight(root.left);if(leftHeight -1) {return -1;}int rightHeight getHeight(root.right);if(rightHeight -1) {return -1;}if(Math.abs(leftHeight-rightHeight)1) {return Math.max(leftHeight,rightHeight)1;} else {//不平衡就返回-1return -1;}}
}对称二叉树oj链接
class Solution {public boolean isSymmetric(TreeNode root) {if(root null) {return true;}return isSymmetricChild(root.left,root.right);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {//1.结构上的判断if(leftTree null rightTree ! null || leftTree ! null rightTree null) {return false;}if(leftTree null rightTree null) {return true;}//2.值if(leftTree.val ! rightTree.val) {return false;}return isSymmetricChild(leftTree.left,rightTree.right) isSymmetricChild(leftTree.right,rightTree.left);}
}二叉树的构建及遍历oj链接
import java.util.Scanner;
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}
}public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNextLine()) {String str in.nextLine();Main main new Main();TreeNode root main.createTree(str);inoeder(root);}}int i 0;TreeNode createTree(String str) {TreeNode root null;char ch str.charAt(i);if(ch ! #) {root new TreeNode(ch);i;root.left createTree(str);root.right createTree(str);} else {i;}return root;}public static void inoeder(TreeNode root) {if(root null) {return;}inoeder((root.left));System.out.print(root.val );inoeder(root.right);}
} 二叉树的分层遍历oj链接
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger retList new ArrayList();if(root null) return retList;QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()) {int size queue.size();ListInteger list new ArrayList();while(size ! 0) {TreeNode cur queue.poll();list.add(cur.val);size--;if(cur.left!null) {queue.offer(cur.left);}if(cur.right ! null) {queue.offer(cur.right);}}retList.add(list);} return retList;}
}判断是不是完全二叉树 1.先把根节点放到队列中 2.队列不为空,弹出元素,放入左孩子右孩子(可以为空) 3.当队列弹出元素为null时停止 4.最后判断当前队列的元素是否都是null.只要出现不为null的元素,则当前二叉树不是完全二叉树 public boolean isCompleteTree(TreeNode root) {if(root null) return true;QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur queue.poll();if(cur ! null) {queue.offer(cur.left);queue.offer(cur.right);} else {break;}}while (!queue.isEmpty()) {TreeNode cur queue.poll();if(cur ! null) {return false;}}return true;}给定一个二叉树, 找到该树中两个指定节点的最近公共祖先oj链接
(1)递归
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(rootnull) return root;if(root p || root q) return root;TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);if(left ! nullright ! null) return root;else if(left ! null) return left;else return right;}
}(2) 用两个栈分别存储根节点到q和p的路径,先将路径长度变得一样,由于栈后进先出,遇到一样的结点就是最近公共祖先
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null) return null;StackTreeNode stack1 new Stack();StackTreeNode stack2 new Stack();getPath(root,p,stack1);getPath(root,q,stack2);int size1 stack1.size();int size2 stack2.size();if(size1 size2) {int size size1-size2;while(size ! 0) {stack1.pop();size--;}} else {int size size2-size1;while(size ! 0) {stack2.pop();size--;}}while(!stack1.isEmpty()) {if(stack1.peek().equals(stack2.peek())) {return stack1.pop();} else {stack1.pop();stack2.pop();}}return null;}public boolean getPath(TreeNode root, TreeNode node, StackTreeNode stack) {if(rootnull) return false;stack.push(root);if(root node) return true;boolean flgleft getPath(root.left, node, stack );if(flgleft) return true;boolean flgright getPath(root.right, node, stack );if(flgright) return true;stack.pop();return false;}
}根据一棵树的前序遍历与中序遍历构造二叉树oj链接
class Solution {public int preIndex;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder, inorder, 0, inorder.length-1);}private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inBegin, int inEnd) {if(inBegin inEnd) {return null;}TreeNode root new TreeNode(preorder[preIndex]);int rootIndex findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);preIndex;root.left buildTreeChild(preorder, inorder, inBegin, rootIndex-1);root.right buildTreeChild(preorder, inorder, rootIndex1, inEnd);return root;}private int findRootIndex(int[] inorder, int inBegin, int inEnd,int key) {for(int i inBegin; i inEnd; i) {if(inorder[i] key) {return i;}}return -1;}
}根据一棵树的中序遍历与后序遍历构造二叉树oj链接
class Solution {public int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex postorder.length-1;return buildTreeChild(postorder, inorder, 0, inorder.length-1);}private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inBegin, int inEnd) {if(inBegin inEnd) {return null;}TreeNode root new TreeNode(postorder[postIndex]);int rootIndex findRootIndex(inorder,inBegin,inEnd,postorder[postIndex]);postIndex--;root.right buildTreeChild(postorder, inorder, rootIndex1, inEnd);root.left buildTreeChild(postorder, inorder, inBegin, rootIndex-1);return root;}private int findRootIndex(int[] inorder, int inBegin, int inEnd,int key) {for(int i inBegin; i inEnd; i) {if(inorder[i] key) {return i;}}return -1;}
}二叉树创建字符串oj链接
class Solution {public String tree2str(TreeNode root) {StringBuilder sbu new StringBuilder();tree2strChild(root,sbu);return sbu.toString();}public void tree2strChild(TreeNode root, StringBuilder sbu) {if(root null) {return;}sbu.append(root.val);if(root.left ! null) {sbu.append(();tree2strChild(root.left,sbu);sbu.append());} else {if(root.right null) {return;} else {sbu.append(());}}if(root.right ! null) {sbu.append(();tree2strChild(root.right,sbu);sbu.append());} else {return;}}
}二叉树前序非递归遍历实现oj链接
(1)用栈 时间复杂度O(n) 空间复杂度O(n)
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();if(root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()) {while(cur ! null) {stack.push(cur);list.add(cur.val);cur cur.left;}TreeNode top stack.pop();cur top.right;}return list;}
}(2)Morris 遍历
时间复杂度O(n) 空间复杂度O(1)
class Solution {public ListInteger preorderTraversal(TreeNode root) {ListInteger res new ArrayListInteger();if (root null) {return res;}TreeNode p1 root, p2 null;while (p1 ! null) {p2 p1.left;if (p2 ! null) {while (p2.right ! null p2.right ! p1) {p2 p2.right;}if (p2.right null) {res.add(p1.val);p2.right p1;p1 p1.left;continue;} else {p2.right null;}} else {res.add(p1.val);}p1 p1.right;}return res;}
}二叉树中序非递归遍历实现oj链接
class Solution {public ListInteger inorderTraversal(TreeNode root) {ListInteger list new ArrayList();if(root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;while(cur ! null || !stack.isEmpty()) {while(cur!null) {stack.push(cur);cur cur.left;}TreeNode top stack.pop();list.add(top.val);cur top.right;}return list;}
}二叉树后序非递归遍历实现oj链接
class Solution {public ListInteger postorderTraversal(TreeNode root) {ListInteger list new ArrayList();if(root null) {return list;}StackTreeNode stack new Stack();TreeNode cur root;TreeNode prev null;while(cur ! null || !stack.isEmpty()) {while(cur!null) {stack.push(cur);cur cur.left;}TreeNode top stack.peek();if(top.right null || top.right prev) {stack.pop();list.add(top.val);prev top;} else {cur top.right;}}return list;}
}
