编程题：二叉树的下一个结点

- 日理万妓 2022-05-20 00:44 177阅读 0赞

## 题目描述 ##

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

### 思路： ###

1. 如果此节点有右子树，下一个节点为右子节点的最左边的节点。

2.如果此节点没有右子树，并且如果此节点是其父节点的左子节点，则下一个节点为父节点。

3.如果此节点没有右子树，并且如果此节点是其父节点的右子节点，则一直向上找，直到找到第一个是其父节点左节点的节点，下一个节点就为此节点。

### 代码： ###

package com.example.shirodemo;
    
    import java.util.*;
    
    /**
     * Created by ASUS on 2018/7/2
     *
     * @Authod Grey Wolf
     */
    public class Practice {
    
        public static void main(String[] args) {
            Practice practice = new Practice();
            practice.sys();
        }
    
        private void sys() {
    
            TreeLinkNode treeLinkNode=new TreeLinkNode(1);
            treeLinkNode.left=new TreeLinkNode(2);
            treeLinkNode.right=new TreeLinkNode(3);
            treeLinkNode.left.left=new TreeLinkNode(4);
            System.out.println("树的中序遍历：");
            medicSort(treeLinkNode);
            TreeLinkNode nextNode=getNext(treeLinkNode);
            System.out.println();
            if (nextNode!=null) {
                System.out.println(treeLinkNode.val+"下一个结点-->" + nextNode.val);
            }else{
                System.out.println("该结点没有下一个结点");
            }
    
        }
    
        /**
         * 树的中序遍历
         * @param treeLinkNode
         */
        private void medicSort(TreeLinkNode treeLinkNode) {
            if (treeLinkNode!=null){
                medicSort(treeLinkNode.left);
                System.out.print(treeLinkNode.val+" ");
                medicSort(treeLinkNode.right);
            }
        }
    
        /**
         * 获取下一个结点
         * @param pNode
         * @return
         */
        public TreeLinkNode getNext(TreeLinkNode pNode)
        {
            if(pNode == null) {
                return null;
            }
            TreeLinkNode pNext = null;
            if(pNode.right!=null){
                TreeLinkNode temp = pNode.right;
                while(temp.left!=null){
                    temp = temp.left;
                }
                pNext = temp;
            }else{
                TreeLinkNode pParent = pNode.next;
                TreeLinkNode current = pNode;
                while(pParent!=null && pNode == pParent.right){
                    pNode = pParent;
                    pParent = pParent.next;
                }
                pNext = pParent;
            }
            return pNext;
    
        }
    
    
    }
    
    class TreeLinkNode{
        int val;
        TreeLinkNode left=null;
        TreeLinkNode right=null;
        TreeLinkNode next=null;
    
        TreeLinkNode(int val){
            this.val=val;
        }
    }

### 效果： ###

树的中序遍历：  
4 2 1 3  
1下一个结点-->3  
  
我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。