问题:
给定一个二叉树,从左到右,找出第 k 个叶子节点。比如
图中二叉树的第 3 个叶子节点(从左到右)是 11.
分析:
因为顺序是从左往右数,所以,对于一个节点下的两个叶子节点来讲(比如 6 下面有两个叶子节点 5 和 11),我们要确保先遍历最左边一个,然后再遍历右边一个。这样,其实,在中序遍历,前序遍历和后序遍历中,都能保证左边叶子节点比右边叶子节点先被遍历。我们只需要对每一个遍历的节点进行检查,看是否是叶子节点,是,则把个数+1. 代码如下:
public class NthLeaf {
static int k = 0;
// get the nth leaf by using preorder traversal
public void getNthleve(Node root, int n) {
if (root == null) return;
if (root.rightChild == null && root.leftChild == null) {
k++;
if (k == n) {
System.out.print(root.toString());
}
}
getNthleve(root.leftChild, n);
getNthleve(root.rightChild, n);
}
public static void main(String[] args) {
Node a = new Node(2);
Node b = new Node(7);
Node c = new Node(5);
Node d = new Node(2);
Node e = new Node(6);
Node f = new Node(9);
Node g = new Node(5);
Node h = new Node(11);
Node i = new Node(4);
a.leftChild = b;
a.rightChild = c;
b.leftChild = d;
b.rightChild = e;
c.rightChild = f;
e.leftChild = g;
e.rightChild = h;
f.rightChild = i;
new NthLeaf().getNthleve(a, 3);
}
}
class Node {
Node leftChild = null;
Node rightChild = null;
int value;
Node(int value) {
this.value = value;
}
@Override
public String toString() {
return value + "";
}
}
转载请注明出处:http://blog.csdn.net/beiyeqingteng
分享到:
相关推荐
实验报告 采用链式存储结构求任意给出的二叉树的叶子节点个数,过程有详解,包括过程中的错误。
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...
此程序可以建立二叉树并输出此二叉树的叶子节点总数与节点总数
设计算法,将给定二叉树的叶子结点连成一个带头结点的单链表,并要求叶子结点按照从左到右的顺序插入,而排列顺序为从右到左(逆置)的单链表。
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
递归算法计算二叉树中叶子节点的数目
二叉树非递归求叶子节点,以及前序、中序、后序遍历算法
二叉树的各种遍历(前序、中序、后序、层序),以及计算树的叶子树和树的深度
构建二叉树,求解叶子结点。VC6.0调试通过。
Python实现给定一棵二叉树,分别按照二叉树先序,中序和后序打印所有的节点。 给定一棵二叉树,分别按照二叉树先序,中序和后序打印所有的节点。 数据范围:0≤n≤1000,树上每个节点的val值满足 0≤val≤100。 ...
二叉树采用链式存储结构,此算法可以实现计算一颗给定的二叉树中叶子结点的数目
1.创建二叉树的链式存储表示。由二叉树的先序序列和中序序列创建二叉树; 2.按树状打印二叉树; 3.统计二叉树的叶子结点个数; 4.输出二叉树中从根结点到所有叶子结点的路径
输出树的根节点到叶子节点的所有路径,用递归实现
一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点...
1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树; 3) 在二叉树中搜索给定结点的父结点;...两个要求写了一份代码
编写算法判别给定二叉树是否为完全二叉树,用递归实现
二叉树的层序遍历是指从二叉树的第一层开始,从上之下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。 5.4 二叉树存储结构及实现 5.4.1 顺序存储结构 具体步骤: (1)将二叉树按完全二叉树编号。 (2)将...
二叉树的创建、遍历、以及左右子树交换,非递归遍历,叶子节点计算及线索树等完整程序
本程序为C语言实现二叉树的基本操作,包括创建二叉树,求叶子节点个数,画二叉树,中序遍历二叉树
1024,结点编号1~N)的层次遍历序列和中序遍历序列,输出T从左向右叶子结点以及二叉树先序和后序遍历序列。输入格式输入共三行:第一行是整数n,表示二叉树中的结点数目;第二行有n个整数,表示该二叉树的层次遍历...