给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
/* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */ public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { } }
写一个函数返回中序下的下一个结点。
思路:
//当前结点为根结点时:
//1)若根结点无右子树,返回NULL
/2)若根结点有右子树,返回右子树中最左端的结点
//当前结点为左叶子结点:
//直接返回其父结点
//当前结点为右叶子结点
//1)若其祖父结点存在且其父结点是其祖父结点的左结点,返回其祖父结点
//2)否则,返回NULL
//当前结点为非叶子结点
//1)若无右子树,返回其父结点
//2)若有右子树,返回其右子树中最左端的结点
public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode==null) return null; TreeLinkNode temp; //当前结点为根结点 if(pNode.next==null){ //无右子树 if(pNode.right==null){ return null; }else { temp=pNode.right; while(temp.left!=null){ temp=temp.left; } return temp; } } //当前结点为左叶子结点 if((pNode.left==null&&pNode.right==null)&&(pNode.next.left==pNode)){ //无右子树 if(pNode.right==null){ return pNode.next; }else{ //找到右子树的最左子叶子结点 temp=pNode.right; while(temp.left!=null){ temp=temp.left; } return temp; } } //当前结点为右叶子结点 if((pNode.left==null&&pNode.right==null)&&(pNode.next.right==pNode)){ //当祖父结点是否存在 if(pNode.next.next!=null&&pNode.next.next.left==pNode.next){ return pNode.next.next; }else{ return null; } } if(pNode.right!=null){ temp=pNode.right; while(temp.left!=null){ temp=temp.left; } return temp; }else{ return pNode.next; } } }
相关推荐
编写一个将二叉树中每个结点的左右孩子交换的算法。
采用先序法建立一棵二叉树,设计输出某结点数据为x的双亲结点的数据的程序,二叉树的数据域类型为字符型, 扩展二叉树的叶子结点用‘#’表示,要求可以求一棵二叉树中多个结点的双亲。
二叉树部分关于结点的问题有点难,这是个简单易懂的
//该程序用于在二叉树中寻找是否有元素X的结点,若找到返回结点地址,否则返回空指针(假设二叉树中至多有一个结点的元素为X)
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_...
编写算法交换二叉树中所有结点的左右子树.doc
输入的数据只有一组,是一棵二叉树的先序遍历序列,结点的值为一个小写字母,#号表示空结点,如输入:a b d e # # f # # # c # #,数据之间空一个格,得到的二叉树如下。( 图暂时不能上传,请同学们自己画出图) ...
笔者使用二叉链表作为二叉树的存储结构,利用递归的思想,实现了统计二叉树中元素为x的结点数目的算法。二叉链表的应用是《数据结构与算法》课程中的重点内容之一,值得收藏学习。
二叉树叶子结点个数计算.doc
在利用栈建立一个二叉树的基础上,我们可以通过递归来实现二叉树中两个结点的最近公共祖先结点。递归是一种非常强大的算法技巧,它可以通过反复调用自身来解决问题。在这个特定的问题中,我们可以利用递归来查找两个...
7.3如果已知一棵二叉树有20个叶子结点,有10个结点仅有左孩子,15个结点仅有右 孩子,求出该二叉树的结点数目。 7.4已知某完全二叉树有100个结点,试用三种不同的方法求出该二叉树的叶子结点数 。 7.5如果已知完全...
信息。。。。。。。。。。。。。。。。。。。。。。。。。
0. 建立二叉树(方法0) 1. 建立二叉树(方法1) 2. 统计叶子结点个数 3. 求二叉树的树深
编写递归算法,计算二叉树中叶子结点的数目
设有一棵二叉树,其结点值为字符型并假设各值互不相等,采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列,要求建立该二叉树,并求其度为2的结点个数。
编写递归算法,计算二叉树中叶子结点的数目
剑指Offer - 57 - 二叉树的下一个结点题目链接题目给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。//觉得改成parent更好
题目:编写递归算法,将二叉树中所有结点的左右子树相互交换 - READ.doc
求二叉树上结点的路径 (树的后序遍历) 在采用链式存储结构的二叉树上,以bt指向根结点,p指向作任一给定的结点,求出从根结点到给定结点之间的路径。 不用调试,可直接运行。
利用二叉树的二叉链表存储结构求解二叉树的深度和双分支结点的个数;利用二叉树的二叉链表存储结构实现二叉排序树建树和删除操作。...设计并实现如下算法:求一棵二叉树的深度和双分支结点的个数。