首页
学习
活动
专区
圈层
工具
发布

【数据结构实战】二叉树——从根节点到叶节点

所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。...// 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int...k); //二叉树高度 int BinaryTreeHeight(BTNode* root); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root,...BTDataType x); 2.3.1 二叉树的结点个数 这里我们依然可以利用递归的想法,结点的个数就等于左边的子节点个数加右边的子节点个数再加上自己的1就可以啦 // 二叉树节点个数...lheight + 1 : rheight + 1; } 2.3.4 二叉树查找值为x的节点 递归思想:找到就返回当前节点,没找到就继续从左子树和右子树开始找,直到根节点变为空结点返回 BTNode

64110
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)

    把它 叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。...节点的度:一个节点含有的子树的个数称为该节点的度; 如下图:A的为6 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点 非终端节点或分支节点:度不为0的节点...若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1. 3....对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2 +1 4....0 : TreeSize(root->left) + TreeSize(root->right) + 1; } 4.6叶节点的个数 int LeafSize(BTNode* root) { if (root

    4.2K10

    完全二叉树的节点个数(二分查找)

    题目 给出一个完全二叉树,求出该树的节点个数。...说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。...若最底层为第 h 层,则该层包含 1~ 2h 个节点。...计算包含当前节点在内的左屋檐和右屋檐高度 相等的话,说明是完全二叉树,直接公式计算 不相等的话,递归调用 class Solution { int h, hL, hR; public: int...计算某节点的左子的左屋檐 ,右子的左屋檐 左边 == 右边,说明左边是完全的,直接公式 左边 > 右边,说明右边是完全的,直接公式 class Solution { int h, hL, hR; public

    93031

    二叉树子节点的最近父节点

    查找二叉树子节点的最近共同父节点 分析 实现 算法复杂度 其他算法 题目升级 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。...分析 对于二叉树来讲,由于左右子树指针的存在,使得正常情况下的自上而下遍历显得比较简单,而下而上的查找并不那么容易,所以一种直观的思维就是从根节点开始遍历,直到找到节点p pp,记录路径数组为p a t...->right; 最后一种情况,要么current就是p或者q节点之一,要么p,q分别在current的左右子树上.也就是要查找的最近父节点。...题目升级 如果题目中的树只是一颗普通的二叉树,那么最近父节点该怎么查找?...left : right; } 同样最坏的情况是,二叉树退化成了一个类似于单链表的结构,p,q两个节点就在表的末端最后两个节点,这样的话,时间复杂度也会变为O ( n ) O(n)O(n);不消耗额外的空间

    3.1K40

    JavaScript快速查找节点

    扩展 在扩展之前,我们需要知道一些关于节点基础的知识:Dom节点中,每个节点都拥有不同的类型      W3C规范中常用的Dom节点的类型有以下几种 节点类型 说明 值 元素节点 每一个HTML标签都是一个元素节点...--comment Text--> 8 文档节点 表示整个文档(Dom树的根节点,即document) 9  关于节点的名称,不同类型的节点对应不同的名称 节点类型 节点名称 元素节点 HTML的名称...(节点值)分别返回节点的类型(比如元素节点返回1,属性节点返回2)、节点名称以及节点值; JS获取兄弟节点的两种方法  方法一:通过父元素的子元素先找到含自己在内的“兄弟元素”,然后在剔除自己 1 function...== elem) a.push(b[i]); 6 } 7 return a; 8 } 方法二:jQuery中实现方法,先通过查找元素的第一个子元素,然后在不断往下找下一个紧邻元素,判断并剔除自己...== elem) { 6 r.push(n); 7 } 8 } 9 return r; 10 } 很显然通过这种方法查找特定节点的兄弟元素

    2.9K110

    Leetcode No.129 求根节点到叶节点数字之和

    一、题目描述 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。...每条从根节点到叶节点的路径都代表一个数字: 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。...<= 9 树的深度不超过 10 二、解题思路 这道题中,二叉树的每条从根节点到叶子节点的路径都代表一个数字。...对每个节点访问一次。 空间复杂度:O(n),其中 n 是二叉树的节点个数。...空间复杂度主要取决于递归调用的栈空间,递归栈的深度等于二叉树的高度,最坏情况下,二叉树的高度等于节点个数,空间复杂度为 O(n)。

    54510

    二叉树:删除节点

    算法: 1.后驱算法: /* 递归解法: 1.找到需要删除的节点 2.删除的节点只有右子树或者左子树,直接将右子树或者左子树的根节点当作这个删除的节点 3.删除的节点左右子树都存在的情况下,左子树的最大节点也叫做前驱当作删除节点..., 或者将右子树的最小节点也就称作后驱当作删除节点。...*/ 2.前驱算法: /* 递归解法: 1.找到需要删除的节点 2.删除的节点只有右子树或者左子树,直接将右子树或者左子树的根节点当作这个删除的节点 3.删除的节点左右子树都存在的情况下,左子树的最大节点也叫做前驱当作删除节点..., 或者将右子树的最小节点也就称作后驱当作删除节点。...2.删除的节点只有右子树或者左子树,直接将右子树或者左子树的根节点当作这个删除的节点 3.删除的节点左右子树都存在的情况下,左子树的最大节点也叫做前驱当作删除节点, 或者将右子树的最小节点也就称作后驱当作删除节点

    1.2K20

    算法:二叉排序树的删除节点策略及其图形化(二叉树查找)

    二叉排序树(BST,Binary Sort Tree)具有这样的性质:对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据成员,且小于右子树所有节点的数据成员。...排序二叉树的中序遍历结果是从小到大排列的。 二叉排序树的查找和插入比较好理解,主要来看一下删除时的情况。...http://download.csdn.net/detail/simba888888/5334093 最后提一下,我们希望构建出来的二叉排序树是比较平衡的,即其深度与完全二叉树相同,那么查找的时间复杂度研究度...O(logn),近似于折半查找, 但如果出现构造的树严重不平衡,如完全是左斜树或者右斜树,那么查找时间复杂度为O(n),近似于顺序查找。...事实上还有一种平衡二叉树(AVL树),也是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。

    1.7K90

    【数据结构与算法】二叉树的深度,节点数,第k层的节点数,遍历,二叉树叶节点的个数

    一.前言 我们需要先构建个二叉树,方便后续对函数的测试; 还有我们在实现二叉树的这些函数时,尽量少用遍历,这里用的比较多的就是递归和分治思想。...二叉树的节点数=左子树的节点数+右子树的节点数; 1.如果root==NULL,则返回0; 2.否则递归调用它的左子树和右子树; 3.然后+1; 详细请看递归调用图: int TreeSize...left + 1 : right + 1; } 三.二叉树第k层的节点数 二叉树第k层的节点数=左子树的第k-1层的节点数+右子树第k-1层的节点数。...因为二叉树没有第0层,是从第一层开始的,所以k==1时,返回1。....二叉树叶节点的个数 叶节点就是没有子节点的节点,我们可以分别记录下当前节点的左节点和右节点,如果都为空,那么叶节点的个数+1。

    79910
    领券