网站运营方案设计,马鞍山建设集团有限公司网站,如何建设好英文网站,在wordpress中rss订阅的步骤是什么?#x1f435;本篇文章将对二叉树的相关概念、性质和遍历等知识进行讲解 一、什么是树
在讲二叉树之前#xff0c;先了解一下什么是树#xff1a;树是一种非线性结构#xff0c;其由许多节点和子节点组成#xff0c;整体形状如一颗倒挂的树#xff0c;比如下图#xff1… 本篇文章将对二叉树的相关概念、性质和遍历等知识进行讲解 一、什么是树
在讲二叉树之前先了解一下什么是树树是一种非线性结构其由许多节点和子节点组成整体形状如一颗倒挂的树比如下图 A就是这棵树的根BDEF、D、CG、G等都可以看作这颗树的一颗子树在树形结构中子树之间不能由交集否则不能称为树如下图就不是树 二、树的相关概念 1. 结点的度一个结点含有子结点的个数称为该结点的度如A的度为2B的度3D的度为0
2. 树的度所有结点度的最大值称为树的度比如上树中B的度最大则该树的度为3
3. 叶子结点/终端结点度为0的结点称为叶子结点如上树中的D E F G
4. 双亲结点/父结点一个结点的前驱结点称为该结点的父结点如B的父结点为A
5. 孩子结点/子结点一个结点的后继结点称为该结点的子结点如B的子结点有D E F
6. 根结点没有双亲结点的结点称为根结点上树的根结点为A
7. 结点的层次从根结点那一层开始定义A为第一层有时是从0开始B C所处第二层依此类推
8. 树的高度树中结点的最大层次为称为该树的高度上树的高度为3 三、二叉树
二叉树是一种特殊的树一棵所有结点的度都小于等于2的树称为二叉树 二叉树特别讲究顺序如上图中如果G为C的左孩子则又是一颗完全不同的二叉树 3.1 满二叉树
从根结点开始从上到下从左到右每一层都放满了结点的树称为满二叉树如下图 若一个满二叉树有k层则其每一层有2^(k - 1)个结点整个树共有(2^k) - 1个结点 3.2 完全二叉树
从根结点开始从上到下从左到右依次存放结点最后一层可以不满这样的二叉树称为完全二叉树如下图 下图不是完全二叉树 3.3 二叉树的性质
1. 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i - 1)个结点
2. 若规定根结点的层数为1则一棵非空二叉树的最大结点数是(2^i) - 1
3. 对任何一棵二叉树如果其叶结点个数为n0度为2的结点个数为n2则有n0n21
4. 具有n个结点的完全二叉树的高度为log₂(n 1)向上取整如3.x为4或者log₂(n) 1向下取整如3.x为3
5. 具有n个结点的完全二叉树从上到下从左到右依次编号规定根结点的编号为0则编号为i的结点双亲编号(i - 1) / 2左孩子编号2i 1若2i 1 n则无左孩子右孩子编号2i 2若2i 2 n则无右孩子
下面讲一道例题 一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 【解析】由于二叉树中的结点的度都不大于2所以设度为012的结点的个数分别为n0n1n2则n0 n1 n2 767由性质3n0 n2 1得2*n0 n1 768在完全二叉树中度为1的结点只可能有1个或0个如果n1 1则n0不是一个整数所以n1只可能为0经计算n0 384 3.4 二叉树的存储
二叉树有两种存储方式分别为链式存储和顺序存储这里主要讲解链式存储接下来用代码以穷举的方式先构造下面这个二叉树 public class BinaryTree {static class TreeNode{public char val; public TreeNode left; //指向该结点的左孩子public TreeNode right; //指向该结点的右孩子public TreeNode(char val) {this.val val;}}
}
接下来以穷举的方式构造二叉树 public TreeNode creatTree() {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;E.right H;C.left F;C.right G;return A; //返回这个树的根结点}3.5 二叉树的遍历
二叉树共有3种遍历方式分别为先序遍历、中序遍历、后序遍历接下来会逐个讲解
3.5.1 先序遍历
先序遍历一个树按照根、左子树、右子树的顺序遍历这个树直接看例子 先遍历这个树的根A之后遍历A的左B由于B又是一个子树的根所以要继续遍历B的左B的左为空那就遍历B的右FF是一个子树的根所以要继续遍历F的左DD的左右都为空那么F的左子树全部遍历完毕接着遍历F的右F的右为空那么B的右全部遍历完毕那接着就是A的左全部遍历完毕之后遍历A的右CC又是一个子树的根所以要继续遍历C的左C的左为空那就遍历C的右GG的左右都为空至此A的右也全部遍历完毕那么整个二叉树遍历完毕整个遍历的序列为A B F D C G 3.5.2 中序遍历
先序遍历一个树按照左子树、根、右子树的顺序遍历这个树直接看例子 先遍历A的左由于A的左也是一个子树所以要遍历这个子树的左空这个子树的左遍历完就要遍历这个树的根B之后遍历这个子树的右F D这也是一个子树所以要先遍历这个子树左D然后遍历根F最后是右右为空那么整个二叉树的左遍历完毕接着遍历根A然后遍历右子树C G先遍历这个树的左左为空然后遍历根C最后是右G至此整个二叉树遍历完毕整个遍历的序列为B D F A C G 3.5.3 后序遍历
先序遍历一个树按照左子树、右子树、根的顺序遍历这个树直接看例子 先遍历这个二叉树的左子树B F D这也是一个树所以先遍历这个树的左左为空然后遍历这个树的右子树F D这也是一个树所以要先遍历这个树的左D然后遍历这个树的右右为空最后是根F那么B F D这个子树的右遍历完毕然后遍历B F D这个树的根B至此整个树的左子树遍历完毕然后遍历这个树的右子树C G先遍历这个树的左左为空然后遍历右G再遍历根C最后遍历整个树的根A整个树遍历完毕整个遍历的序列为D F B G C A 3.6 代码实现二叉树的遍历
二叉树的三种遍历需要用递归的思想实现 先序遍历 public void preOrder(TreeNode root) {if (root null) { //如果根为空则直接返回return;}System.out.print(root.val );preOrder(root.left); //以根的左孩子为新的根继续遍历preOrder(root.right); //以根的右孩子为新的根继续遍历}root为null后返回至上一个方法遍历D的右孩子右孩子也为空则以D为根的方法结束返回至上一个方法遍历B的右孩子 右子树也是同样的道理
中序遍历 public void inOrder(TreeNode root) {if (root null) {return;}preOrder(root.left);System.out.print(root.val );preOrder(root.right);}后序遍历 public void postOrder(TreeNode root) {if (root null) {return;}preOrder(root.left);preOrder(root.right);System.out.print(root.val );}
