python 平衡二叉樹實(shí)現(xiàn)代碼示例
更新時(shí)間：2018年07月07日 11:54:20 作者：7749ha
這篇文章主要介紹了python 平衡二叉樹實(shí)現(xiàn)代碼示例，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
平衡二叉樹：
在上一節(jié)二叉樹的基礎(chǔ)上我們實(shí)現(xiàn)，如何將生成平衡的二叉樹
所謂平衡二叉樹：
我自己定義就是：任何一個(gè)節(jié)點(diǎn)的左高度和右高度的差的絕對(duì)值都小于2
如圖所示，此時(shí)a的左高度等于3，有高度等于1，差值為2，屬于不平衡中的左偏
此時(shí)的處理辦法就是：
將不平衡的元素的左枝的最右節(jié)點(diǎn)變?yōu)楫?dāng)前節(jié)點(diǎn)，
此時(shí)分兩種情況：
一、左枝有最右節(jié)點(diǎn)
將最右節(jié)點(diǎn)的左枝賦予其父節(jié)點(diǎn)的右枝
二、左枝沒有最右節(jié)點(diǎn)，
直接將左枝節(jié)點(diǎn)做父級(jí)節(jié)點(diǎn)，父級(jí)節(jié)點(diǎn)做其右枝
如圖所示，圖更清楚些。
可能會(huì)有疑問，為什么這樣變換？
假定a左偏，就需要一個(gè)比a小的最少一個(gè)值d(因?yàn)閐唯一 一個(gè)是比a小，而且比a的左枝所有數(shù)都大的值)做父集結(jié)點(diǎn)，a做d的右枝，這樣在最上面的d節(jié)點(diǎn)就平衡了。
我們可以反證一下：
如果不是d是另一個(gè)數(shù)假設(shè)為h，此時(shí)h做父節(jié)點(diǎn)，a做父節(jié)點(diǎn)的右節(jié)點(diǎn)
因?yàn)閍在h右邊，所以 a > h
因?yàn)閎,e,d,f都是h的左枝，所以 h>d>b>e>f
所以 a>h>d>b>e>f
所以在不加入新節(jié)點(diǎn)的情況下，就只能是d
左偏和右偏是一樣的，可以完全鏡像過來就ok了
處理了所有節(jié)點(diǎn) 的左偏和右偏使整個(gè)二叉樹平衡，這就是平衡二叉樹的基本思想
代碼實(shí)現(xiàn)：
# -*- coding:utf-8 -*-
# 日期：2018/6/12 8:37
# Author:小鼠標(biāo)
# 節(jié)點(diǎn)對(duì)象
class Node:
def __init__(self):
self.left_children = None
self.left_height = 0
self.right_children = None
self.right_height = 0
self.value = None
# 二叉樹對(duì)象
class tree:
def __init__(self):
self.root = False
self.front_list = []
self.middle_list = []
self.after_list = []
# 生成二叉樹
def create_tree(self,n=0,l=[]):
if l == []:
print("傳入的列表為空")
return
if n > len(l)-1:
print("二叉樹生成")
return
node = Node()
node.value = l[n]
if not self.root:
self.root = node
self.list = l
else:
self.add(self.root,node)
self.create_tree(n+1,l)
# 添加節(jié)點(diǎn)
def add(self,parent,new_node):
if new_node.value > parent.value:
# 插入值比父親值大，所以在父節(jié)點(diǎn)右邊
if parent.right_children == None:
parent.right_children = new_node
# 新插入節(jié)點(diǎn)的父親節(jié)點(diǎn)的高度值為1，也就是子高度值0+1
parent.right_height = 1
# 插入值后 從下到上更新節(jié)點(diǎn)的height
else:
self.add(parent.right_children,new_node)
# 父親節(jié)點(diǎn)的右高度等于右孩子，左右高度中較大的值 + 1
parent.right_height = max(parent.right_children.right_height, parent.right_children.left_height) + 1
# ======= 此處開始判斷平衡二叉樹=======
# 右邊高度大于左邊高度 屬于右偏
if parent.right_height - parent.left_height >= 2:
self.right_avertence(parent)
else:
# 插入值比父親值小，所以在父節(jié)點(diǎn)左邊
if parent.left_children == None:
parent.left_children = new_node
parent.left_height = 1
else:
self.add(parent.left_children,new_node)
parent.left_height = max(parent.left_children.right_height, parent.left_children.left_height) + 1
# ======= 此處開始判斷平衡二叉樹=======
# 左邊高度大于右邊高度 屬于左偏
if parent.left_height - parent.right_height >= 2:
self.left_avertence(parent)
# 更新當(dāng)前節(jié)點(diǎn)下的所有節(jié)點(diǎn)的高度
def update_height(self,node):
# 初始化節(jié)點(diǎn)高度值為0
node.left_height = 0
node.right_height = 0
# 是否到最底層的一個(gè)
if node.left_children == None and node.right_children == None:
return
else:
if node.left_children:
self.update_height(node.left_children)
# 當(dāng)前節(jié)點(diǎn)的高度等于左右子節(jié)點(diǎn)高度的較大值 + 1
node.left_height = max(node.left_children.left_height,node.left_children.right_height) + 1
if node.right_children:
self.update_height(node.right_children)
# 當(dāng)前節(jié)點(diǎn)的高度等于左右子節(jié)點(diǎn)高度的較大值 + 1
node.right_height = max(node.right_children.left_height, node.right_children.right_height) + 1
# 檢查是否仍有不平衡
if node.left_height - node.right_height >= 2:
self.left_avertence(node)
elif node.left_height - node.right_height <= -2:
self.right_avertence(node)
def right_avertence(self,node):
# 右偏 就將當(dāng)前節(jié)點(diǎn)的最左節(jié)點(diǎn)做父親
new_code = Node()
new_code.value = node.value
new_code.left_children = node.left_children
best_left = self.best_left_right(node.right_children)
v = node.value
# 返回的對(duì)象本身,
if best_left == node.right_children and best_left.left_children == None:
# 說明當(dāng)前節(jié)點(diǎn)沒有有節(jié)點(diǎn)
node.value = best_left.value
node.right_children = best_left.right_children
else:
node.value = best_left.left_children.value
best_left.left_children = best_left.left_children.right_children
node.left_children = new_code
self.update_height(node)
# 處理左偏情況
def left_avertence(self,node):
new_code = Node()
new_code.value = node.value
new_code.right_children = node.right_children
best_right = self.best_left_right(node.left_children,1)
v = node.value
# 返回的對(duì)象本身,
if best_right == node.left_children and best_right.right_children == None:
# 說明當(dāng)前節(jié)點(diǎn)沒有有節(jié)點(diǎn)
node.value = best_right.value
node.left_children = best_right.left_children
else:
node.value = best_right.right_children.value
best_right.right_children = best_right.right_children.left_children
node.right_children = new_code
self.update_height(node)
# 返回node節(jié)點(diǎn)最左（右）子孫的父級(jí)
def best_left_right(self,node,type=0):
# type=0 默認(rèn)找最左子孫
if type == 0:
if node.left_children == None:
return node
elif node.left_children.left_children == None:
return node
else:
return self.best_left_right(node.left_children,type)
else:
if node.right_children == None:
return node
elif node.right_children.right_children == None:
return node
else:
return self.best_left_right(node.right_children,type)
# 前序(先中再左最后右)
def front(self,node=None):
if node == None:
self.front_list = []
node = self.root
# 輸出當(dāng)前節(jié)點(diǎn)
self.front_list.append(node.value)
# 先判斷左枝
if not node.left_children == None:
self.front(node.left_children)
# 再判斷右枝
if not node.right_children == None:
self.front(node.right_children)
# 返回最終結(jié)果
return self.front_list
# 中序(先左再中最后右)
def middle(self,node=None):
if node == None:
node = self.root
# 先判斷左枝
if not node.left_children == None:
self.middle(node.left_children)
# 輸出當(dāng)前節(jié)點(diǎn)
self.middle_list.append(node.value)
# 再判斷右枝
if not node.right_children == None:
self.middle(node.right_children)
return self.middle_list
# 后序(先左再右最后中)
def after(self,node=None):
if node == None:
node = self.root
# 先判斷左枝
if not node.left_children == None:
self.after(node.left_children)
# 再判斷右枝
if not node.right_children == None:
self.after(node.right_children)
self.after_list.append(node.value)
return self.after_list
# 節(jié)點(diǎn)刪除
def del_node(self,v,node=None):
if node == None:
node = self.root
# 刪除根節(jié)點(diǎn)
if node.value == v:
self.del_root(self.root)
return
# 刪除當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
if node.left_children:
if node.left_children.value == v:
self.del_left(node)
return
# 刪除當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
if node.right_children:
if node.right_children.value == v:
self.del_right(node)
return
if v > node.value:
if node.right_children:
self.del_node(v, node.right_children)
else:
print("刪除的元素不存在")
else:
if node.left_children:
self.del_node(v, node.left_children)
else:
print("刪除的元素不存在")
#刪除當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
def del_right(self,node):
# 情況1 刪除節(jié)點(diǎn)沒有右枝
if node.right_children.right_children == None:
node.right_children = node.right_children.left_children
else:
best_left = self.best_left_right(node.right_children.right_children)
# 表示右枝最左孫就是右枝本身
if best_left == node.right_children.right_children and best_left.left_children == None:
node.right_children.value = best_left.value
node.right_children.right_children = best_left.right_children
else:
node.right_children.value = best_left.left_children.value
best_left.left_children = best_left.left_children.right_children
# 刪除當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
def del_left(self,node):
# 情況1 刪除節(jié)點(diǎn)沒有右枝
if node.left_children.right_children == None:
node.left_children = node.left_children.left_children
else:
best_left = self.best_left_right(node.left_children.right_children)
# 表示右枝最左子孫就是右枝本身
if best_left == node.left_children.right_children and best_left.left_children == None:
node.left_children.value = best_left.value
node.left_children.right_children = best_left.right_children
else:
node.left_children.value = best_left.left_children.value
best_left.left_children = best_left.left_children.right_children
# 刪除根節(jié)點(diǎn)
def del_root(self,node):
if node.right_children == None:
if node.left_children == None:
node.value = None
else:
self.root = node.left_children
else:
best_left = self.best_left_right(node.right_children)
# 表示右枝最左子孫就是右枝本身
if best_left == node.right_children and best_left.left_children == None:
node.value = best_left.value
node.right_children = best_left.right_children
else:
node.value = best_left.left_children.value
best_left.left_children = best_left.left_children.right_children
# 搜索
def search(self,v,node=None):
if node == None:
node = self.root
if node.value == v:
return True
if v > node.value:
if not node.right_children == None:
return self.search(v, node.right_children)
else:
if not node.left_children == None:
return self.search(v, node.left_children)
return False
if __name__ == '__main__':
# 需要建立二叉樹的列表
list = [4, 6, 3, 1, 7, 9, 8, 5, 2]
t = tree()
t.create_tree(0,list)
res = t.front()
print('前序', res)
執(zhí)行結(jié)果：
前序 [4, 2, 1, 3, 7, 6, 5, 9, 8]
通過前序可以畫出二叉樹
完美，哈哈。
這是我鉆了兩天才寫出的代碼，哈哈，努力還是有回報(bào)的，加油。
下一步就是代碼優(yōu)化了
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
本文給大家分享python四種常見排序方法，每種方法通過實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友參考下吧2021-07-07
大家平時(shí)在工作與學(xué)習(xí)中都會(huì)操作到Excel文件格式，特別是很多數(shù)據(jù)的時(shí)候，靠人力去識(shí)別操作非常容易出錯(cuò)。今天就帶大家用Python來處理Excel文件，讓你成為一個(gè)別人眼中的秀兒2022-05-05
Scrapy是一個(gè)使用Python編寫的，輕量級(jí)的，簡(jiǎn)單輕巧，并且使用起來非常的方便。使用Scrapy可以很方便的完成網(wǎng)上數(shù)據(jù)的采集工作，它為我們完成了大量的工作，而不需要自己費(fèi)大力氣去開發(fā)。本文介紹了使用Python的Scrapy框架十分鐘爬取美女圖,需要的朋友可以參考下2016-12-12
OpenCV-Python實(shí)現(xiàn)輪廓的特征值
輪廓自身的一些屬性特征及輪廓所包圍對(duì)象的特征對(duì)于描述圖像具有重要意義。本篇博文將介紹幾個(gè)輪廓自身的屬性特征及輪廓包圍對(duì)象的特征，感興趣的可以了解一下2021-06-06
這篇文章主要介紹了Python獲取B站粉絲數(shù)的示例代碼,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-03-03
python3.7+selenium模擬淘寶登錄功能的實(shí)現(xiàn)
這篇文章主要介紹了python3.7+selenium模擬登錄淘寶功能，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-05-05
基于python list對(duì)象中嵌套元組使用sort時(shí)的排序方法
下面小編就為大家分享一篇基于python list對(duì)象中嵌套元組使用sort時(shí)的排序方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-04-04
Python3開發(fā)環(huán)境搭建詳細(xì)教程
這篇文章主要介紹了Python3開發(fā)環(huán)境搭建詳細(xì)教程，本文通過圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-06-06
Python批量發(fā)送post請(qǐng)求的實(shí)現(xiàn)代碼
昨天學(xué)了一天的Python（我的生產(chǎn)語言是java，也可以寫一些shell腳本，算有一點(diǎn)點(diǎn)基礎(chǔ)），今天有一個(gè)應(yīng)用場(chǎng)景，就正好練手了2018-05-05
python中使用paramiko模塊并實(shí)現(xiàn)遠(yuǎn)程連接服務(wù)器執(zhí)行上傳下載功能
paramiko是用python語言寫的一個(gè)模塊，遵循SSH2協(xié)議，支持以加密和認(rèn)證的方式，進(jìn)行遠(yuǎn)程服務(wù)器的連接。這篇文章主要介紹了python中使用paramiko模塊并實(shí)現(xiàn)遠(yuǎn)程連接服務(wù)器執(zhí)行上傳下載功能,需要的朋友可以參考下2020-02-02