武进网站建设方案,网站建设邀请函,山东做网站找哪家好,二手房地产中介网站建设目录 1、树的概念及结构
1.1、概念
1、树的特点
2、树与非树
1.2、概念 #xff08;重要#xff09;
1.3、树的表示形式
2、二叉树#xff08;重点#xff09;
2.1、概念
2.2、二叉树的特点
2.3、两种特殊的二叉树
1、满二叉树
2、完全二叉树
2.4、二叉树的性…目录 1、树的概念及结构
1.1、概念
1、树的特点
2、树与非树
1.2、概念 重要
1.3、树的表示形式
2、二叉树重点
2.1、概念
2.2、二叉树的特点
2.3、两种特殊的二叉树
1、满二叉树
2、完全二叉树
2.4、二叉树的性质
编辑✨ 练习
2.5、二叉树的存储
2.6、二叉树的遍历
2.6.1、前序遍历先序遍历
2.6.2、中序遍历
2.6.3、后序遍历
2.6.4、层序遍历
2.6.5、二叉树遍历练习
2.7、二叉树的基本操作
2.7.1、获取树中结点的个数
2.7.2、获取叶子节点的个数
2.7.3、获取第k层结点的个数
2.7.4、获取二叉树的高度 1、树的概念及结构
1.1、概念
树是一种非线性的数据结构他是由nn0个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是跟朝上而叶朝下的。
1、树的特点 有一个特殊的节点称为跟节点根节点没有前驱节点除根结点外其余节点被分成M(M 0)个互不相交的集合T1、T2、......、Tm其中每一个集合Ti(1 i m)又是一棵与树类似的子树。每课子树的根节点有且只有一个前驱可以有0个或多个后继树是递归定义的。2、树与非树 1.2、概念 重要 结点的度一个节点含有子树的个数称为该节点的度也可以理解为节点含有的子节点的个数如上图A的度为6。树的度树内各节点的度的最大值如上图树的度为6叶子节点或终端节点度为0的节点常委叶子节点如图B、C、H、I、N、P、Q为叶子节点双亲节点和父节点若一个节点含有子节点则这个结点称为其子节点的父节点如上图A是B的父节点。孩子结点或子节点一个结点含有的子树的根节点称为该节点的子节点如上图:B是A的孩子结点根节点一棵树中没有双亲结点的结点如上图A结点的层次从根节点定义起根为第1层跟的子节点为第2层以此类推。树的高度或深度树中结点的最大层次如上图树的高度为4以下概念只需了解在看书的时候知道是什么意思即可 非终端结点或分支结点度不为0的结点如上图D、E、F、G、J为分支结点兄弟结点具有相同父节点的结点互称为兄弟节点如上图B、C是兄弟结点堂兄弟结点双亲正在同一层的结点互为堂兄弟如上图H、I互为堂兄弟结点结点的祖先从根到该节点所经分支上的所有结点如上图A是所有结点的先祖子孙以某结点为根的子树中任一结点都称为该节点的子孙。如上图所有结点都是A的子孙森林有m(m 0) 棵互不相交的树组成的集合称为森林。对树中每个结点而言其子树的集合几位森林。1.3、树的表示形式
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式如双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。这里我们就简单的了解其中最常用的孩子兄弟表示法。
class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
} 2、二叉树重点
2.1、概念
二叉树是结点的一个有限集合该集合
或者为空或者是由一个根结点加上两颗分别称为左子树和右子树的二叉树组成。2.2、二叉树的特点 每个结点最多有两棵子树所以二叉树中不存在度大于2的结点。注意不是只有两棵子树而是最多有。该节点没有子树或者有一颗子树都是可以的。左子树和右子树是有顺序的次序不能任意颠倒因此二叉树是有序树。即使树中某个节点只有一棵子树也要区分它是左子树还是右子树。2.3、两种特殊的二叉树
1、满二叉树
定义两种方式 在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子都在同一层上这样的二叉树称为满二叉树。一棵二叉树如果每层的结点数都达到最大值则这颗二叉树就是满二叉树单是每个结点都存在左右子树不能算是满二叉树还必须要所有的叶子都在通一层上这就做到了整棵树的平衡。
满二叉树的特点 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。非叶子结点的度一定是2.否则就是去胳膊少腿了。在同一深度的二叉树中满二叉树的结点个数最多叶子树最多。如果一棵满二叉树的层数为k则它的结点总数是.2、完全二叉树
✨定义 对一棵具有n个结点的二叉树按层序编号如果编号为i1in的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同则这颗二叉树称为完全二叉树。 ❗❗❗可以这样理解 完全二叉树的所有结点与同样深度的满二叉树他们按层序编号。两个二叉树中的节点编号是一一对应的。满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。 画图理解 ✨ 完全二叉树的特点 叶子结点只能出现在最下两层最下层的叶子一定集中在最左部连续位置倒数第二层若有叶子节点一定是在右部连续位置如果结点的度为1则该结点只有左孩子即不存在只有右子树的情况同样节点数的二叉树完全二叉树的深度最小2.4、二叉树的性质
1、若规定根结点的层数为1则一棵非空二叉树的第i层上最多有i 0个结点 2、若规定只有根节点的二叉树的深度为1则深度为K的二叉树的最大节点数是(k 0) 3、对任何一棵二叉树如果其叶子结点个数为n0度为2的非叶子结点个数为n2则有n0 n21
论证 通过学习树的知识我们知道一棵N个结点的树有N-1条边 。 这条性质的意思是任何一个二叉树中度为0的结点比度为2的结点多1个 4、具有n个结点的完全二叉树的深度k 向上取整。 5、 对于有n个结点的完全二叉树如果按照从上至下、从左至右的顺序对所有结点从0开始编号则对于序号为i的结点有
若 i 0双亲序号(i-1)/2i 0i为根结点编号无双亲结点若2i1 n左孩子序号2i1否则无左孩子若2i 2 n有孩子序号否则无右孩子
✨ 练习
1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为B
A 、不存在这样的二叉树 B、200 C、198 D、199 ❗题解叶子结点也就是度为0的结点已知度为2的结点为199个根据公式n0 n2 1得度为0的结点为200个。 2、在具有 2n 个结点的完全二叉树中叶子结点个数为A
A n B n1 C n-1 D n/2 ❗题解 3.一个具有767个节点的完全二叉树其叶子节点个数为B
A 383 B 384 C 385 D 386 ❗题解由于结点的个数为奇数所以根据公式n n0n1n2——》767 n0n2得公式1 再由度为0的节点数等于度为2的节点数1n0 n21 得公式2 联立公式1和2得767 n0n0-1 ——》768 2n0 ——》n0 384 故叶子节点个数为384所以选B 4.一棵完全二叉树的节点数为531个那么这棵树的高度为 B
A 11 B 10 C 8 D 12 题解 n个结点的完全二叉树的深度为k 向上取整 所以k 2^9 512说明9层放不下所有结点向上取整 所以这棵树的高度为10 2.5、二叉树的存储
二叉树的存储结构分为顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的结点引用起来的常见的表示方式由二叉和三叉表示方式。
// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树Node parent; // 当前节点的根节点
} 本章博客主要了解孩子表示法 2.6、二叉树的遍历
在学习二叉树的遍历以及后续的二叉树的基本操作的时候首先要生成一个二叉树但是生成一个二叉树需要用到递归有些难度这里我们手动创建一个二叉树方便二叉树的遍历和基本操作方法的学习。
public class TestbinaryTree {//定义二叉树的类static class TreeNode{//定义结点public char val;public TreeNode left;//孩子结点所以用TreeNode类型的引用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;this.root A;return root;}}学习二叉树最简单的方式就是遍历。所谓遍历是指沿着某条搜索路线依次对树中每个结点均作一次且仅作一次访问。访问结点所作的操作依赖于具体的引用问题 比如打印结点内容、节点内容加1.遍历时二叉树上最重要的操作之一时二叉树上进行其他运算的基础。 2.6.1、前序遍历先序遍历
前序遍历 访问根节点——》根的左子树——》根的右子树。
✨遍历流程 先遍历二叉树的根节点若根节点A不为空打印根节点A。再遍历根节点的左子树B若左子树的根节点B不为空打印B。再遍历B结点的左子树D若左子树的根节点D不为空打印D为空打印D返回到D结点的根节点B。遍历B结点的右子树输出根节点的值。依次为例将整棵树遍历完成每个结点只输出一次 。每次输出的都是树的根节点。✨代码示例 这里有两种思路遍历思路和子问题思路
写法一遍历的思路好理解 //前序遍历根——》左子树——》右子树public void preOrder(TreeNode root){if(root null){//递归的开始也是结束条件return ;//若根节点为空则直接返回}System.out.println(root.val );//若根不为空先输出跟结点preOrder(root.left);//通过调用自己实现递归遍历左子树preOrder(root.right);}✨递归过程 写法二 子问题思路难理解
1.这个代码还是存在很多问题的给了返回值类型但是并没有将该方法的返回值用起来 ListInteger ret new ArrayList();//用来记录遍历的结点的值public ListInteger preorderTraversal(TreeNode root){if(root null){return ret;//根节点为空返回ret;}ret.add(root.val);//将根节点的值放到ret当中preorderTraversal(root.left);//遍历左子树preorderTraversal(root.right);//遍历右子树return ret;}
2、这个是子问题思路比较合理的写法。 public ListInteger preorderTraversal(TreeNode root) {ListInteger ret new ArrayList();//每次调用这个方法都会产生新的空间用来记录这个方法遍历的内容if (root null) {return ret;//根节点为空返回ret;}ret.add(root.val);//将二叉树的根节点的值放到ret当中//将左子树遍历到的内容放到左子树的数组中ListInteger leftTree preorderTraversal(root.left);//遍历左子树并用ListInteger类型的引用来接收方法的返回值ret.addAll(leftTree);//addAll方法用来向ret集合中添加一个集合对象所包含的所有内容//将右子树遍历到的内容放到右子树的数组中ListInteger rightTree preorderTraversal(root.right);//遍历右子树ret.addAll(rightTree);return ret;} 2.6.2、中序遍历
中序遍历根的左子树——》根节点——》根的右子树
✨遍历流程 先遍历二叉树的左子树若根节点A不为空遍历A的左子树B.若B不为空遍历他的左子树D若D的左子树为空则返回输出D再遍历右子树若右子树为空则B的左子树遍历完成返回到B并输出B。再遍历B的右子树若为空则A的左子树遍历完成返回输出A再遍历A的右子树以此为例知道整棵树遍历完成。✨代码示例
1、遍历的思路 //中序遍历左子树——》根节点——》右子树public void inOrder(TreeNode root){if(root null){//递归的开始和结束条件return;//若根节点为空则返回}inOrder(root.left);//若根节点不为空则递归左子树System.out.println(root.val );//左子树递归完成打印根节点inOrder(root.right);//再递归右子树}
中序遍历的代码递归过程就不再演示了思路前序遍历相似。
2、子问题思路 public ListCharacter inOrder(TreeNode root) {ListCharacter ret new ArrayList();//每次调用这个方法都会产生新的空间。if (root null) {return ret;//根节点为空返回ret;}//将左子树遍历到的结点的内容放到左子树的数组中ListCharacter leftTree inOrder(root.left);//遍历左子树并用ListInteger类型的引用来接收方法的返回值ret.addAll(leftTree);//addAll方法用来向ret集合中添加一个集合对象所包含的所有内容ret.add(root.val);//将二叉树的第一个根节点的值放到ret当中//将右子树遍历到的结点的内容放到左子树的数组中ListCharacter rightTree inOrder(root.right);//遍历右子树ret.addAll(rightTree);return ret;} 2.6.3、后序遍历
后序遍历根的左子树——》根的右子树——》根节点
✨遍历流程 先遍历二叉树的左子树若跟结点A不为空则遍历A的左子树B。若B不为空则遍历B的左子树D。若D不为空则遍历D的左子树若D的左子树为空则返回到D再遍历D的右子树。若D的右子树为空则返回输出根节点D则B的左子树就遍历完成返回到B再遍历B的右子树。若B的右子树为空则返回B并输出A的左子树B再返回A再遍历A的右子树C。以此为例。直到遍历完整棵树。✨代码示例
1、遍历思路 //后序遍历左子树——》右子树——》根节点public void postOrder(TreeNode root){if(root null){//递归的开始和结束条件return;//若根节点为空则返回}postOrder(root.left);//若根节点不为空则递归左子树postOrder(root.right);//再递归右子树System.out.println(root.val );//左右子树都递归完成打印根节点} 2、子问题思路 public ListCharacter postOrder(TreeNode root) {ListCharacter ret new ArrayList();//每次调用这个方法都会产生新的空间。if (root null) {return ret;//根节点为空返回ret;}//将左子树遍历到的结点的内容放到左子树的数组中ListCharacter leftTree postOrder(root.left);//遍历左子树并用ListInteger类型的引用来接收方法的返回值ret.addAll(leftTree);//addAll方法用来向ret集合中添加一个集合对象所包含的所有内容//将右子树遍历到的结点的内容放到左子树的数组中ListCharacter rightTree postOrder(root.right);//遍历右子树ret.addAll(rightTree);ret.add(root.val);//将二叉树的第一个根节点的值放到ret当中return ret;}
✨遍历测试 以createTree中手动生成的树为例前序遍历ABDEHCFG中序遍历DBEHAFCG后序遍历DHEBFGCA。与测试结果相同。 public class Test {public static void main(String[] args) {TestbinaryTree testbinaryTree new TestbinaryTree();TestbinaryTree.TreeNode root testbinaryTree.createTree();System.out.println(前序遍历);testbinaryTree.preOrder(root);System.out.println();System.out.println(中序遍历);testbinaryTree.inOrder(root);System.out.println();System.out.println(后序遍历);testbinaryTree.postOrder(root);System.out.println();}} 2.6.4、层序遍历 设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根结点然后从左到右访问第二层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问数的结点的过程就是层序遍历。 2.6.5、二叉树遍历练习
1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为(A)
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
【题解】 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为A)
A: E B: F C: G D: H 【题解】 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为D)
A: adbce B: decab C: debac D: abcde 【题解】 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为(A)
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
【题解】 ❗❗❗ 总结 当前序遍历序列和中序遍历序列同时知道可以得到后续遍历序列。当中序遍历序列和后序遍历序列同时知道可以得到前序遍历序列。但是当后序遍历序列和前序遍历序列同时知道不能得到中序遍历序列。前序遍历序列和后序遍历序列可以知道二叉树的根节点中序遍历序列可以知道根节点的左右子树。2.7、二叉树的基本操作
2.7.1、获取树中结点的个数 这个方法的递归公式可以用子问题思路来思考。 左子树结点个数右子树结点个数根节点 总节点数 当有左子树和右子树则用上述的公式若没有则可以直接输出根节点1. 【代码示例】
1、子问题思路 public int size(TreeNode root){if(root null){return 1;}int leftSize size(root.left);//这里的递归每次走左边结点查看子树的左右结点然后将子树的左右结点加根节点的值返回。int rightSize size(root.right);return leftSize rightSize 1;}
2、遍历思路 每个结点都是一个子树的根节点当根节点不为空时则1 public int nodeSize;public void size1(TreeNode root){if(root null){return ;}nodeSize;size1(root.left);size1(root.right);} ❗❗❗这个方法存在一个问题当有两个二叉树都要求结点个数时引用第一次结果是正确的但是第二次就会出错因为nodeSize 属性是属于某个引用的在test类当中用同一个引用调用两次这个方法那么第二次nodeSize的结果是将两个树中的结点都加在了一起。 ❗❗❗总结这个方法的时间复杂度为O(N) 空间复杂度为O(logN) 原因在于二叉树的遍历是先遍历左子树再遍历右子树所以再极端情况下他能开辟的空间就是树的高度。 2.7.2、获取叶子节点的个数
❗❗❗思路 当一个二叉树的结点的左右子树都为空则这个结点就是二叉树的叶子结点。所以当根节点为空时二叉树为空返回0当根节点不为空时且二叉树中某个结点的左右子树都为空时则这个结点为叶子节点返回1✨代码示例
1、子问题思路 public int getLeafNodeCount(TreeNode root){if(root null){return 0;}if(root.right nullroot.left null){//这里判断是叶子节点记录一个结点1.return 1;}//这两个if条件作为递归的结束条件int leftSize getLeafNodeCount(root.left);int rightSize getLeafNodeCount(root.right);return leftSizerightSize;//将左右两个子树的叶子结点加起来}
2、遍历思路 public int leafSize;public void getLeafNodeCount2(TreeNode root){if(root null){return;}if(root.left nullroot.right null){leafSize;//遍历一个叶子节点1}getLeafNodeCount2(root.left);//调用该方法遍历左子树。getLeafNodeCount2(root.right);} 2.7.3、获取第k层结点的个数
以下面的二叉树为例第k 3层的结点的个数。 ✨子问题思路 当要求A树的第3层结点个数时则要求A树的左子树B的k-1层结点个数和A树的右子数C的k-1层结点个数的合。 ✨代码示例 //获取第k层结点的个数public int getLevelNodeCount(TreeNode root,int k){if(root null){return 0;}if(k 1){return 1;}int leftSize getLevelNodeCount(root.left,k-1);int rightSize getLevelNodeCount(root.right,k-1);return leftSizerightSize;}2.7.4、获取二叉树的高度
以下列的二叉树为例 ✨子问题思路 每次遍历的都是树的根节点当根节点为空时递归结束。那么左子树的高度也就确定。以同样的方式遍历右子树确定右子树的高度再将两个树的高度进行比较最大的高度1就是该二叉树的高度。✨代码示例 //获取二叉树的高度public int getHeight(TreeNode root){if(root null){return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return (leftHeightrightHeight)?(leftHeight1):(rightHeight1);}
