松门建设规划局网站,冠县网站建设是什么,wordpress例行维护,网站制作成都目录
树的概念
树的表示形式
二叉树
二叉树的性质
题目
二叉树的存储
链式存储
初始化二叉树
二叉树的遍历
前序遍历#xff1a;根#x1f449;左子树#x1f449;右子树 中序遍历#xff1a;左子树#x1f449;根#x1f449;右子树
后序遍历#xff1a;左子…目录
树的概念
树的表示形式
二叉树
二叉树的性质
题目
二叉树的存储
链式存储
初始化二叉树
二叉树的遍历
前序遍历根左子树右子树 中序遍历左子树根右子树
后序遍历左子树右子树根
选择题
代码代码
前序遍历的存储问题 树的概念
树是一种非线性的数据结构是由nn0个有限结点组成一个具有层次关系的集合
它像是一颗倒挂的树即根朝上叶结点朝下 注意
除了根结点外每个节点有且只有一个父结点
一棵n个结点的树由n-1条边 结点的度一个结点含有子树的个数上面A的度就是6
树的度所有结点度的最大值max(node degree)上面树的度就是6
叶结点/终端结点度为0的结点上面B,C,H,I,K,L,M,N,P,Q就是叶结点
父结点一个结点如果有条线连着上面一个结点那上面这个结点就是这个结点的父结点
比如A是B的父结点
子节点结点含有的子树的根结点B是A的子结点
根结点没有父结点的结点
结点层次根是第一层其子结点是第2层。。。。
树的高度树结点最大层次树高度为4
分支结点度不为0的结点比如D,E,J....
兄弟结点有相同父结点的结点
堂兄弟结点双亲在同一层的结点互为堂兄弟如H,I就是堂兄弟结点 树的表示形式
孩子兄弟表达法 二叉树
一颗二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上左子树和右子树的二叉树组成
特点
二叉树不存在度大于2的结点所以他的每颗子树都是二叉树 满二叉树每层结点树都达到最大值。如果一棵二叉树的层数为k且结点总数是2^k-1那它就是一棵满二叉树 完全二叉树对于深度为k有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 满二叉树是一种特殊的完全二叉树
二叉树的性质
1.若规定的根结点层数是1那一棵非空二叉树的第i层上最多有2^(i-1)个结点 2.规定只有根结点的二叉树深度为1则深度为k的二叉树最大结点数是2^k -1
3.对于任意一棵二叉树如果叶结点个数为n0度为2的非叶结点个数为n2则有n0 n21
换句话说叶结点(度为0)的个数总是要比度为2的结点个数多1个 如上图叶结点的个数有6个度为2的结点个数为5个 51 6
推导公式
等式1假设一棵树有n个结点度为0的有n0个度为1的有n1个度为2的有n2个那么
n n0 n1 n2
等式2一棵n个结点的树有n-1条边
一般的度为0的结点不会产生边度为1的结点(n1个)产生n1 * 1条边度为2的结点(n2个)产生
n2 * 2 条边
那么 n-1 n12*n2
把等式1和2联立n0n1n2-1 n1 2 * n2 -- n0 n2 1
4.具有n个结点的完全二叉树的深度k为上取整 5. 对于具有 n 个结点的完全二叉树 如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 则对于 序号为 i 的结点有 若 i0 双亲序号 (i-1)/2 i0 i 为根结点编号 无双亲结点 若 2i1n 左孩子序号 2i1 否则无左孩子 若 2i2n 右孩子序号 2i2 否则无右孩子 假设父结点下标是i则左孩子下标为 2*i1右孩子下标是2*i2
反推如果孩子下标为i则父结点下标是(i-1) / 2 题目 偶数个结点的完全二叉树度为1的结点一定只有1个
而奇数个结点的度为1的结点为0个
所以可以列个等式
2n n0 1 n2 n0 1 n0 - 1
所以 n0 n 选A 二叉树的存储
分为顺序存储和链式存储
顺序存储堆可以看看我后面的博客这篇博客讲链式存储
链式存储 初始化二叉树
目前的思路
先创建结点以穷举的方式造一棵二叉树根据下面这张图来创建 public class BinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}public TreeNode root;//创建一棵二叉树创建成功后返回根结点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.left B;A.right C;B.left D;B.right E;C.left F;C.right G;E.right H;return A;}
}
测试一下 煤油问题
二叉树的遍历
遍历指的是沿着某条路线遍历
前序遍历根左子树右子树
遇到根就打印 中序遍历左子树根右子树 后序遍历左子树右子树根 留一道题请写出下图的前序中序和后序遍历答案在文章末尾 选择题 首先把这个树画出来 画出来后就很简单了答案就是A 怎么画出这棵树 根结点就是E 注意后序遍历是可以确定树的根的就是最后一个字母a
那放到中序遍历中a的左边b就是左子树a的右边dce构成右子树
后序遍历里面a后面的c是一个子树根根据中序那d和e就很自然排在c的左和右了 画出来就是这样前序遍历就是abcde 后序遍历确定根是F那根据中序遍历F前面的ABCDE构成左子树没有右子树
F后面每一个元素都是前一个元素的根结点画出来就是这样 层次输出FEDCBA
问题如果给你前序遍历和后序遍历可以画出一棵二叉树吗
不可以。因为前序和后序确定的都是根
代码代码 // 前序遍历void preOrder(TreeNode root){if(root null){return;}System.out.println(root.val );preOrder(root.left);preOrder(root.right);}
有点难理解其实这段代码的分析过程跟我们在造树的过程差不多 图太大了只能截一部分了... 剩下的俩就很简单了 // 中序遍历void inOrder(TreeNode root){if(root null){return;}inOrder(root.left);System.out.println(root.val );inOrder(root.right);}// 后序遍历void postOrder(TreeNode root){if(root null){return;}postOrder(root.left);postOrder(root.right);System.out.println(root.val );}
前序遍历的存储问题
144. 二叉树的前序遍历 - 力扣LeetCode
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
遍历思路遍历到是我就存储进去
class Solution {ListInteger list new ArrayList();public ListInteger preorderTraversal(TreeNode root) {if(root null){return list;}list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}
}
套娃存列表思想 public ListInteger preorderTraversal(TreeNode root) {ListInteger list new ArrayList();if(root null){return list;}list.add(root.val);ListInteger leftTree preorderTraversal(root.left);list.addAll(leftTree);ListInteger rightTree preorderTraversal(root.right);list.addAll(rightTree);return list;}
画个图解释一下只画了左子树 每次返回就把拼接好的列表归到父结点的列表中 图片遍历答案 前序ABDEHCFG
中序DBEHAFCG
后序DHEBFGCA
