当前位置：极客教程 > Python 实例 > Python 程序 > 利用Python改变二叉树的根节点的程序

利用Python改变二叉树的根节点的程序

利用Python改变二叉树的根节点的程序

假设我们有一棵二叉树和一个位于二叉树叶子节点上的节点。我们必须将叶子节点变为二叉树的根节点。我们可以按照以下方式操作 −

  • 如果一个节点有左孩子，则它变为右孩子。

  • 一个节点的父节点变为其左孩子。在此过程中，父节点链接到该节点的链接变为null，因此它只有一个孩子。

树的节点结构如下所示 −

TreeNode:
  data: <integer>
  left: <pointer of TreeNode>
  right: <pointer of TreeNode>
  parent: <pointer of TreeNode>
Python

我们必须返回转换后的根节点。

因此，如果输入如下所示

利用Python改变二叉树的根节点的程序

新根为8;则转换后的树的中序表示将为 − 2, 3, 4, 5, 7, 6, 8,

树的新根节点是8。

要解决这个问题，我们将遵循以下步骤−

  • 定义一个函数helper()。这将获取节点和new_par
    • 如果节点与根相同，则
      • 节点的父节点：=new_par

      • 如果节点的左侧与new_par相同，则

      • 节点的左侧：= null

      • 如果节点的右侧与new_par相同，则

      • 节点的右侧：= null

      • 返回根

    • 如果节点的左侧不为null，则

      • 节点的右侧：=节点的左侧
    • 如果节点的父节点的左侧与节点相同，则
      • 节点的父节点的左侧：=null
    • 节点的左侧：= helper(node的父节点，节点)

    • 节点的父节点：=new_par

    • 返回节点

  • 返回helper(叶子，null)

让我们看以下示例以获得更好的理解。

更多Python相关文章，请阅读：Python 教程

例子

import collections
class TreeNode:
   def __init__(self, data, left = None, right = None, parent = None):
      self.data = data
      self.left = left
      self.right = right
      self.parent = parent
   def insert(temp,data):
      que = []
      que.append(temp)
      while (len(que)):
         temp = que[0]
         que.pop(0)
         if (not temp.left):
            if data is not None:
               temp.left = TreeNode(data, parent = temp)
            else:
               temp.left = TreeNode(0, parent = temp)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data, parent = temp)
         else:
            temp.right = TreeNode(0, parent = temp)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
def search_node(root, element):
   if (root == None):
      return None
   if (root.data == element):
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   res2 = search_node(root.right, element)
   return res2
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
def solve(root, leaf):
   def helper(node, new_par):
      if node == root:
         node.parent = new_par
         if node.left == new_par:
            node.left = None
         if node.right == new_par:
            node.right = None
         return root
      if node.left:
         node.right = node.left
      if node.parent.left == node:
         node.parent.left = None
      node.left = helper(node.parent, node)
      node.parent = new_par
      return node
   return helper(leaf, None)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))
print_tree(root)
Python

输入

root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))
Python

输出

2, 3, 4, 5, 7, 6, 8,
Python

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

登录

找回密码？

注册