简单网站制作,wordpress小说站模板,广州网站导航,系统清理优化工具相关概念树的表示二叉树二叉树性质二叉树储存 实现一颗二叉树创建遍历#xff08;前中后序#xff09;获取树中节点个数获取叶子节点个数获取第k层节点个数获取二叉树高度检测值为value元素是否存在层序遍历#xff08;需要队列来实现#xff09;判断是否为完全二叉树… 相关概念树的表示二叉树二叉树性质二叉树储存 实现一颗二叉树创建遍历前中后序获取树中节点个数获取叶子节点个数获取第k层节点个数获取二叉树高度检测值为value元素是否存在层序遍历需要队列来实现判断是否为完全二叉树需要队列来实现 相关概念 重点概念后续学习将会反反复复出现
对我们当前学习稍微不重要 树的表示
树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法AVL树、红黑树、B树会用到、孩子兄弟表示法等等。我们了解一下孩子兄弟表示法 代码表示
class Node{int value;//我们当前学习就是简简单单的存个int数字Node firstChild;Node nextNorther;}二叉树
二叉树每一个节点的度小于等于2其实就是每一个节点的孩子个数不超过两个。二叉树的有次序是指你把右子树放左边画出来结果就是两个不同的树 任意二叉树都是由以下的情况组合的 满二叉树每层的结点数都达到最大值如果层数是k满二叉树的节点个数为2^k-1
完全二叉树你按左右到上下编号1-n一定是连续的
二叉树性质
前提规定第一层是根节点的二叉树 1第i层最多节点个数2^(i-1) 2深度为k总节点个数最多是2^k-1 (完全二叉树的情况)
3非常重要任意的二叉树叶子节点个数比度为2的节点个数多一个度为0就是叶子不涉及到度为1的节点 n0n21 如果要把n1也扯上关系使用n-1n00n11n2*2n是总节点个数解释一颗n个节点的树有N-1条边而叶子节点不产生边度为1的节点只产生一条边度为2的节点产生两条边 比如有4层 其实就是2的4次方等于2的3次方2都平方2的1次方2的0次方1。 题目 某二叉树共有399个结点其中有199个度为2的结点则该二叉树中的叶子结点数为 A不存在这样的二叉树 B200 C198 D199
4具有n个结点的完全二叉树的深度k为log(n1)向上取整 不受到你最后层节点个数影响最后层一个跟2的n-1个是一样因为用最大节点个数推导出来的 5对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有 若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1n左孩子序号2i1否则无左孩子 若2i2n右孩子序号2i2否则无右孩子 注意完全二叉树度为1的节点要么是1个要么是0个。奇数个节点就没有度为1的节点偶数个节点就有一个度为1的节点。如果题目告诉你2n个节点那就说明有度为1的节点
二叉树储存 如何遍历 先序根—左子树----右子树(这个比较容易理解) 中序左子树—根—右子树先访问左子树然后你左子树又得按照中序进行 后序左子树–右子树—根
实现一颗二叉树
创建
//创建一颗树
class tree{//树的节点还是内部类实现类似链表class Listnode{//一个节点包含三个域char val;Listnode left;//左边Listnode right;//右边public Listnode(char val) {this.val val;}}public Listnode create(){//先把节点和值创建好然后再绑关系Listnode Anew Listnode(A);Listnode Bnew Listnode(B);Listnode Cnew Listnode(C);Listnode Dnew Listnode(D);Listnode Enew Listnode(E);Listnode Fnew Listnode(F);Listnode Gnew Listnode(G);//这里的B和C是节点A.leftB;A.rightC;B.leftD;B.rightE;C.leftF;C.rightG;return A;//返回根节点}
遍历前中后序
前序 public void print1(Listnode root){if(rootnull) {return ;}System.out.println(root.val);print1(root.left);print1(root.right);}中序这次我们就不打印遍历把值存在顺序表里 public ListCharacter print2(Listnode root){ListCharacter listnew ArrayList();if(rootnull){return list;}//System.out.println(root.val);list.add(root.val);print2(root.left);print2(root.right);return list;}后序
public ListCharacter print3(Listnode root){ListCharacter retnew ArrayList();if(rootnull){return ret;}//System.out.println(root.val);ret.add(root.val);//先把头放进去然后左边放一个表右边放一个表最后放到retListCharacter sprint3(root.left);ret.addAll(s);ListCharacter s1print3(root.right);ret.addAll(s1);return ret;
}获取树中节点个数
//获取树中节点的个数int num0;public int size(Listnode root){//遍历计数器if(rootnull) {return 0;}num;size(root.left);size(root.right);return num;}//子问题计数public int size1(Listnode root){if(rootnull) {return 0;}int tmp size1(root.left)size1(root.right)1;//(把走到每个节点都分为左边、右边和它自己)return tmp;}获取叶子节点个数 // 获取叶子节点的个数int ret30;public void getLeafNodeCount(Listnode root){
//自己为空肯定就结束了if(rootnull){return ;}//如果左边和右边同时为空就计数if(root.leftnullroot.rightnull){ret3;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);}// 子问题思路-求叶子结点个数public int getLeafNodeCount1(Listnode root){
//自己为空肯定就结束了if(rootnull){return 0;}//如果左边和右边同时为空就计数if(root.leftnullroot.rightnull){return 1;}return getLeafNodeCount1(root.left)getLeafNodeCount1(root.right);}
获取第k层节点个数 // 获取第K层节点的个数,直接子问题public int getKLevelNodeCount(Listnode root,int k){
//我们之前不是求了一棵树节点个数吗假设我要求k层在k-1的左右子树的和if(rootnull||k0) {return -1;}if(k1){//这时候条件就不再是root.leftnullroot.rightnull而是k-1层的孩子节点我都要计算return 1;}int tmpgetKLevelNodeCount(root.left,k-1)getKLevelNodeCount(root.right,k-1);return tmp;}
获取二叉树高度
非常巧妙递归的结束rootnull返回上一级到叶子节点发现height1height2不成立叶子节点的右边1如果是root.left遍历下的就返回给这里的值。画个图就好理解 // 获取二叉树的高度public int getHeight(Listnode root) {if(rootnull){return 0;}int height1 getHeight(root.left);int height2 getHeight(root.right);if (height1height2){return height11;//加1是关键每结束一层1}elsereturn height21;} 检测值为value元素是否存在 // 检测值为value的元素是否存在public Listnode find(Listnode root, int val) {if (root null) {return null;}if (root.val val) {return root;}find(root.left, val);//这里应该把find(root.left,val)存到ret里避免下面用这个又要重复再递归一次if (find(root.left, val).val val) {return root;} //如果我在左边找到就不去右边//如果我在右边找到就直接结束如果都没找到find(root.right, val);if (find(root.right, val).val val) {return root;}return null;}
层序遍历需要队列来实现
因为二叉树没法按这种顺序来遍历就得依靠别的数据结构 这样子它的打印顺序就是从左到右画图分析好
判断是否为完全二叉树需要队列来实现
队列逻辑按层次遍历弹出把Null也放入队列里当弹出Null的时候发现队列全为Null就说明是完全二叉树 。不全为null就不是完全二叉树。 // 判断一棵树是不是完全二叉树 这题逻辑还是非常清晰public boolean isCompleteTree(TreeNode root) {if(root null) {return true;}QueueTreeNode qu new LinkedList();qu.offer(root);while (!qu.isEmpty()) {TreeNode cur qu.poll();if(cur ! null) {qu.offer(cur.left);qu.offer(cur.right);}else {break;}}//判断队列剩下的值 是否有 非null的数据while (!qu.isEmpty()) {TreeNode pop qu.poll();if(pop ! null) {return false;}}return true;}
