本文概述

• C ++
• Java
• Python3
• C#
• C ++
• Java
• python
• C#

给定二叉树。进行修改, 以便在修改后, 仅使用正确的指针就可以对其进行先序遍历。在修改期间, 你可以使用右指针和左指针。
【修改二叉树以仅使用右指针获得先序遍历】例子：

Input :10 /\ 82 / \ 35 Output :10 \ 8 \ 3 \ 5 \ 2 Explanation : The preorder traversal of given binary tree is 10 8 3 5 2.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。 方法1(递归)
需要使根的右指针指向左子树。
如果该节点刚好有左子节点, 则只需将子节点向右移动即可完成该节点的处理。
如果也有合适的孩子, 那么应该
原始左子树最右端的右子级。
代码中使用的上述函数处理一个节点, 然后返回转换后的子树的最右边的节点。
C ++

//C code to modify binary tree for //traversal using only right pointer #include < bits/stdc++.h> using namespace std; //A binary tree node has data, //left child and right child struct Node { int data; struct Node* left; struct Node* right; }; //function that allocates a new node //with the given data and NULL left //and right pointers. struct Node* newNode( int data) { struct Node* node = new struct Node; node-> data = https://www.lsbin.com/data; node-> left = NULL; node-> right = NULL; return (node); }//Function to modify tree struct Node* modifytree( struct Node* root) { struct Node* right = root-> right; struct Node* rightMost = root; //if the left tree exists if (root-> left) {//get the right-most of the //original left subtree rightMost = modifytree(root-> left); //set root right to left subtree root-> right = root-> left; root-> left = NULL; }//if the right subtree does //not exists we are done! if (!right) return rightMost; //set right pointer of right-most //of the original left subtree rightMost-> right = right; //modify the rightsubtree rightMost = modifytree(right); return rightMost; }//printing using right pointer only void printpre( struct Node* root) { while (root != NULL) { cout < < root-> data < <" " ; root = root-> right; } }//Driver program to test above functions int main() { /* Constructed binary tree is 10 /\ 82 /\ 35*/ struct Node* root = newNode(10); root-> left = newNode(8); root-> right = newNode(2); root-> left-> left = newNode(3); root-> left-> right = newNode(5); modifytree(root); printpre(root); return 0; }

Java

//Java code to modify binary tree for //traversal using only right pointer class GFG {//A binary tree node has data, //left child and right child static class Node { int data; Node left; Node right; }; //function that allocates a new node //with the given data and null left //and right pointers. static Node newNode( int data) { Node node = new Node(); node.data = https://www.lsbin.com/data; node.left = null ; node.right = null ; return (node); } //Function to modify tree static Node modifytree( Node root) { Node right = root.right; Node rightMost = root; //if the left tree exists if (root.left != null ) { //get the right-most of the //original left subtree rightMost = modifytree(root.left); //set root right to left subtree root.right = root.left; root.left = null ; } //if the right subtree does //not exists we are done! if (right == null ) return rightMost; //set right pointer of right-most //of the original left subtree rightMost.right = right; //modify the rightsubtree rightMost = modifytree(right); return rightMost; } //printing using right pointer only static void printpre( Node root) { while (root != null ) { System.out.print( root.data +" " ); root = root.right; } } //Driver cde public static void main(String args[]) { /* Constructed binary tree is 10 /\ 8 2 /\ 3 5 */ Node root = newNode( 10 ); root.left = newNode( 8 ); root.right = newNode( 2 ); root.left.left = newNode( 3 ); root.left.right = newNode( 5 ); modifytree(root); printpre(root); } } //This code is contributed by Arnab Kundu

Python3

# Python code to modify binary tree for # traversal using only right pointer class newNode(): def __init__( self , data): self .data = https://www.lsbin.com/data self .left = None self .right = None# Function to modify tree def modifytree(root):right = root.right rightMost = root # if the left tree exists if (root.left):# get the right-most of the # original left subtree rightMost = modifytree(root.left) # set root right to left subtree root.right = root.left root.left = None# if the right subtree does # not exists we are done! if ( not right): return rightMost # set right pointer of right-most # of the original left subtree rightMost.right = right # modify the rightsubtree rightMost = modifytree(right) return rightMost # printing using right pointer only def printpre(root):while (root ! = None ): print (root.data, end =" " ) root = root.right # Driver code if __name__ = = '__main__' : """ Constructed binary tree is 10 /\ 8 2 /\ 3 5""" root = newNode( 10 ) root.left = newNode( 8 ) root.right = newNode( 2 ) root.left.left = newNode( 3 ) root.left.right = newNode( 5 ) modifytree(root) printpre(root)# This code is contributed by SHUBHAMSINGH10

C#

//C# code to modify binary tree for //traversal using only right pointer using System; class GFG {//A binary tree node has data, //left child and right child public class Node { public int data; public Node left; public Node right; }; //function that allocates a new node //with the given data and null left //and right pointers. static Node newNode( int data) { Node node = new Node(); node.data = https://www.lsbin.com/data; node.left = null ; node.right = null ; return (node); } //Function to modify tree static Node modifytree( Node root) { Node right = root.right; Node rightMost = root; //if the left tree exists if (root.left != null ) { //get the right-most of the //original left subtree rightMost = modifytree(root.left); //set root right to left subtree root.right = root.left; root.left = null ; } //if the right subtree does //not exists we are done! if (right == null ) return rightMost; //set right pointer of right-most //of the original left subtree rightMost.right = right; //modify the rightsubtree rightMost = modifytree(right); return rightMost; } //printing using right pointer only static void printpre( Node root) { while (root != null ) { Console.Write( root.data +" " ); root = root.right; } } //Driver cde public static void Main(String []args) { /* Constructed binary tree is 10 /\ 8 2 /\ 3 5 */ Node root = newNode(10); root.left = newNode(8); root.right = newNode(2); root.left.left = newNode(3); root.left.right = newNode(5); modifytree(root); printpre(root); } }//This code is contributed by 29AjayKumar

输出如下：

10 8 3 5 2

方法2(迭代)
使用迭代的先序遍历可以很容易地做到这一点。看这里。
迭代式遍历
这个想法是要维护一个变量prev, 它保持了先序遍历的前一个节点。每次遇到新节点时, 该节点将其权限设置为上一个节点, 并且上一个节点等于当前节点。最后, 我们将得到一种链表, 其第一个元素是root, 然后是left child, 然后是right, 依此类推。
C ++

//C++ code to modify binary tree for //traversal using only right pointer #include < iostream> #include < stack> #include < stdio.h> #include < stdlib.h> using namespace std; //A binary tree node has data, //left child and right child struct Node { int data; struct Node* left; struct Node* right; }; //Helper function that allocates a new //node with the given data and NULL //left and rightpointers. struct Node* newNode( int data) { struct Node* node = new struct Node; node-> data = https://www.lsbin.com/data; node-> left = NULL; node-> right = NULL; return (node); }//An iterative process to set the right //pointer of Binary tree void modifytree( struct Node* root) { //Base Case if (root == NULL) return ; //Create an empty stack and push root to it stack< Node*> nodeStack; nodeStack.push(root); /* Pop all items one by one. Do following for every popped item a) print it b) push its right child c) push its left child Note that right child is pushed first so that left is processed first */ struct Node* pre = NULL; while (nodeStack.empty() == false ) {//Pop the top item from stack struct Node* node = nodeStack.top(); nodeStack.pop(); //Push right and left children of //the popped node to stack if (node-> right) nodeStack.push(node-> right); if (node-> left) nodeStack.push(node-> left); //check if some previous node exists if (pre != NULL) {//set the right pointer of //previous node to currrent pre-> right = node; }//set previous node as current node pre = node; } }//printing using right pointer only void printpre( struct Node* root) { while (root != NULL) { cout < < root-> data < <" " ; root = root-> right; } }//Driver code int main() { /* Constructed binary tree is 10 /\ 82 / \ 35 */ struct Node* root = newNode(10); root-> left = newNode(8); root-> right = newNode(2); root-> left-> left = newNode(3); root-> left-> right = newNode(5); modifytree(root); printpre(root); return 0; }

Java

//Java code to modify binary tree for //traversal using only right pointer import java.util.*; class GfG {//A binary tree node has data, //left child and right child static class Node { int data; Node left; Node right; }//Helper function that allocates a new //node with the given data and NULL //left and right pointers. static Node newNode( int data) { Node node = new Node(); node.data = https://www.lsbin.com/data; node.left = null ; node.right = null ; return (node); } //An iterative process to set the right //pointer of Binary tree static void modifytree(Node root) { //Base Case if (root == null ) return ; //Create an empty stack and push root to it Stack< Node> nodeStack = new Stack< Node> (); nodeStack.push(root); /* Pop all items one by one. Do following for every popped item a) print it b) push its right child c) push its left child Note that right child is pushed first so that left is processed first */ Node pre = null ; while (nodeStack.isEmpty() == false ) { //Pop the top item from stack Node node = nodeStack.peek(); nodeStack.pop(); //Push right and left children of //the popped node to stack if (node.right != null ) nodeStack.push(node.right); if (node.left != null ) nodeStack.push(node.left); //check if some previous node exists if (pre != null ) { //set the right pointer of //previous node to currrent pre.right = node; } //set previous node as current node pre = node; } } //printing using right pointer only static void printpre(Node root) { while (root != null ) { System.out.print(root.data +" " ); root = root.right; } } //Driver code public static void main(String[] args) { /* Constructed binary tree is 10 /\ 82 /\ 35 */ Node root = newNode( 10 ); root.left = newNode( 8 ); root.right = newNode( 2 ); root.left.left = newNode( 3 ); root.left.right = newNode( 5 ); modifytree(root); printpre(root); } }

python

# Python code to modify binary tree for # traversal using only right pointer # A binary tree node has data, # left child and right child class newNode(): def __init__( self , data): self .data = https://www.lsbin.com/data self .left = None self .right = None# An iterative process to set the right # pointer of Binary tree def modifytree( root):# Base Case if (root = = None ): return# Create an empty stack and append root to it nodeStack = [] nodeStack.append(root)''' Pop all items one by one. Do following for every popped item a) prit b) append its right child c) append its left child Note that right child is appended first so that left is processed first ''' pre = None while ( len (nodeStack)):# Pop the top item from stack node = nodeStack[ - 1 ] nodeStack.pop() # append right and left children of # the popped node to stack if (node.right): nodeStack.append(node.right) if (node.left): nodeStack.append(node.left) # check if some previous node exists if (pre ! = None ):# set the right pointer of # previous node to currrent pre.right = node # set previous node as current node pre = node # printing using right pointer only def printpre( root): while (root ! = None ): print (root.data, end = " " ) root = root.right # Driver code ''' Constructed binary tree is 10 /\ 82 /\ 35 ''' root = newNode( 10 ) root.left = newNode( 8 ) root.right = newNode( 2 ) root.left.left = newNode( 3 ) root.left.right = newNode( 5 ) modifytree(root) printpre(root) # This code is contributed by SHUBHAMSINGH10

C#

//C# code to modify binary tree for //traversal using only right pointer using System; using System.Collections; class GfG {//A binary tree node has data, //left child and right child public class Node { public int data; public Node left; public Node right; }//Helper function that allocates a new //node with the given data and NULL //left and right pointers. static Node newNode( int data) { Node node = new Node(); node.data = https://www.lsbin.com/data; node.left = null ; node.right = null ; return (node); } //An iterative process to set the right //pointer of Binary tree static void modifytree(Node root) { //Base Case if (root == null ) return ; //Create an empty stack and Push root to it Stack nodeStack = new Stack(); nodeStack.Push(root); /* Pop all items one by one. Do following for every Popped item a) print it b) Push its right child c) Push its left child Note that right child is Pushed first so that left is processed first */ Node pre = null ; while (nodeStack.Count !=0) { //Pop the top item from stack Node node = (Node)nodeStack.Peek(); nodeStack.Pop(); //Push right and left children of //the Popped node to stack if (node.right != null ) nodeStack.Push(node.right); if (node.left != null ) nodeStack.Push(node.left); //check if some previous node exists if (pre != null ) { //set the right pointer of //previous node to currrent pre.right = node; } //set previous node as current node pre = node; } } //printing using right pointer only static void printpre(Node root) { while (root != null ) { Console.Write(root.data +" " ); root = root.right; } } //Driver code public static void Main(String []args) { /* Constructed binary tree is 10 /\ 82 /\ 35 */ Node root = newNode(10); root.left = newNode(8); root.right = newNode(2); root.left.left = newNode(3); root.left.right = newNode(5); modifytree(root); printpre(root); } } //This code is contributed by //Arnab Kundu

输出如下：

10 8 3 5 2

推荐阅读

• 

  苹果手机桌面上小圆圈怎么设置，苹果手机上的小圆点怎么设置出来
• 

  羊肚耳怎么吃 羊耳朵吃法
• 

  在线制作中文LOGO竟如此简单 艺术字logo在线设计
• 

  痛风可以吃什么荤菜和素菜 痛风可以吃什么荤菜
• 

  刀锋下的替身大结局
• 

  分析差动连接作用是什么原因
• 

  东风风神前减震异响 东风风神汽车换个减震器多少钱
• 

  u盘启动盘制作工具哪个好用 2021十大u盘启动盘制作软件排名
• 

  用linux命令访问目录 linux 访问
• 

  腌肉腌制时需要密封吗
• 

  诱惑图片
• 

  CGA火线助手怎么用 CGA火线助手下载安装使用教程首页
• 

  滴滴车主怎么加油
• 

  中国有哪些腿型超好看的明星？
• 

  2023杭州父母有浙江省引进人才居住证还需要申请积分入学吗
• 

  上班族肥胖的四个原因及应对方法
• 

  蚂蚁庄园2月23日答案最新 蚂蚁庄园每日答题答案大全
• 

  Win11输入法切换快捷键怎么设置？Win11输入法切换快捷键设置方法
• 

  不思议迷宫隐藏佐罗怎么获得 不思议迷宫必练的英雄佐罗
• 

  蓝莓冷冻保存可以吗，鲜蓝莓可以冷冻保存吗

• 修改数组以最大化相邻差异的总和
• 算法设计（修改链表的内容）
• 算法设计（模划分详细实现）
• 模幂（模运算中的幂）
• 算法设计（从1到n的模乘逆）
• 循环冗余校验和Modulo-2分区
• 算法题（模数10 ^ 9 + 7（1000000007））
• 自学一年C#(WPF)，第二年自学Android。登录
• Android性能优化系列之渲染优化