Fork me on GitHub

Python数据结构和算法

记录一些常见算法的Python实现

In [ ]:
print("-------------------------------")

变位词问题:

经典的字符串变位词检测问题是比较不同数量级函数算法的一个典型例子。如果一个字符串是 另一个字符串的重新排列组合,那么这两个字符串互为变位词。比如,”heart”与”earth”互为变位 词,”python”与”typhon”也互为变位词。为了简化问题,我们设定问题中的字符串长度相同,都是由 26 个小写字母组成。我们需要编写一个接受两个字符串,返回真假,代表是否是一对变位词的布尔 函数。

解法有:

  • 检查标记
  • 排序比较
  • 暴力匹配
  • 计数比较

检查标记:

就是检查第一个字符串中所有字符是不是都在第二个字符中出现,这样比较的次数是: $$\sum_{i=0}^{n}{i} = \frac{n(n-1)}{2} = \frac{n^2}{2} + \frac{n}{2}$$ 所有其算法复杂度是:$O(n^2)$

计数比较:

对一个字符串中出现的所有字母进行计数,将次数保存在计数器列表中,如果两个计数器列表相同,则这两个字符串是变位词。 此算法复杂度是$O(n)$

In [5]:
# 计数比较法
def anagram_solution4(s1,s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] += 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1
    return c1 == c2 
print(anagram_solution4("apple","pleap"))
True
In [8]:
# Python列表生成式速度比较
import timeit
from timeit import Timer

def test1():
    l = []
    for i in range(1000):
        l = l+[i]

def test2():
    l = []
    for i in range(1000):
        l.append(i)

def test3():
    l = [i for i in range(1000)]
    
def test4():
    l = list(range(1000))
    
t1 = Timer("test1()", "from __main__ import test1")
print("串联 ",t1.timeit(number=1000), "milliseconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "milliseconds")
t3 = Timer("test3()", "from __main__ import test3")
print("列表生成式 ",t3.timeit(number=1000), "milliseconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "milliseconds")
串联  4.34192568063736 milliseconds
append  0.2504177428781986 milliseconds
列表生成式  0.10823162645101547 milliseconds
list range  0.04674295708537102 milliseconds
In [10]:
# 比较字典和列表的效率
# 随机选取一个数字,检查其是否在列表/字典中
import timeit
import random

for i in range(10000,1000001,200000):
    t = timeit.Timer("random.randrange(%d) in x"%i,
                     "from __main__ import random,x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))
10000,     0.241,     0.001
210000,     5.108,     0.001
410000,     9.531,     0.001
610000,    14.172,     0.002
810000,    18.597,     0.001

基本数据类型

栈Stack

方法 功能 参数 返回值
Stack() 创建新的空栈 None 空栈
push(item) 将新项添加到栈顶 item None
pop() 从栈顶删除项目 None 栈顶项目item
peek() 返回栈顶项目 None 栈顶项目
isEmpty() 测试栈是否为空 None 布尔值
size() 返回栈项目数 None 项目整数

队列Queue

方法 功能 参数 返回值
Queue() 创建新的空队列 None 空队列
isEmpty() 是否为空 None 布尔值
enqueue(item) 将项目加到队尾 item None
dequeue() 从队首删除项目 None 队首项目
size() 返回队列项目个数 None 整数

双端队列Deque

方法 功能 参数 返回值
Deque() 创建空的双端队列 None Deque对象
addFront(item) 在队首插入一个元素 item None
addRear(item) 在队尾插入一个元素 item None
removeFront() 在队首移除一个元素 None item
removeRear() 在队尾移除一个元素 None item
isEmpty() 判断双端队列是否为空 None 布尔值
size() 返回双端队列中项目数 None 项目整数

列表List

无序列表UnorderedList

无序列表是一个由各个元素组成的集合,其中每个元素拥有一个不同于其他元素的相对位置。

方法 功能 参数 返回值
list() 创建空的列表 None 空列表
add(item) 将新项添加到列表中 item None
remove(item) 列表中删除元素 item None
search(item) 列表中查找元素 item 布尔值
isEmpty() 判断列表是否为空 None 布尔值
size() 返回双端队列中项目数 None 项目整数
append(item) 列表末端添加新元素 item None
index(item) 返回元素在列表中索引值 item 位置索引值
insert(pos,item) 指定位置插入一个元素 pos,item None
pop() 列表末端移除一个元素 None 末端元素
pop(pos) 指定位置移除列表元素 pos 指定位置元素

有序列表OrderedList

方法 功能 参数 返回值
OrderedList() 创建空的有序列表 None 空有序列表
add(item) 将新项添加到列表中 item None
remove(item) 列表中删除元素 item None
search(item) 列表中查找元素 item 布尔值
isEmpty() 判断列表是否为空 None 布尔值
size() 返回双端队列中项目数 None 项目整数
index(item) 返回元素在列表中索引值 item 位置索引值
pop() 列表末端移除一个元素 None 末端元素
pop(pos) 指定位置移除列表元素 pos 指定位置元素
In [12]:
# 用列表实现一个栈
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)
    
s=Stack()

print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.pop())
print(s.pop())
print(s.size())
True
dog
3
False
8.4
True
2
In [13]:
# 用列表实现队列
class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)
In [14]:
# 用列表实现双端队列
class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)
    
# 回文字判定
def palchecker(aString):
    chardeque = Deque()

    for ch in aString:
        chardeque.addRear(ch)

    stillEqual = True

    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False

    return stillEqual

print(palchecker("lsdkjfskf"))
print(palchecker("radar"))
False
True
In [15]:
# 使用链表实现无序列表
class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext
        
        
class UnorderedList:

    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None

    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
        
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count
    
    def search(self,item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()

        return found

    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())
In [16]:
# 实现一个有序列表
class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext


class OrderedList:
    def __init__(self):
        self.head = None

    def search(self,item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()

        return found

    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()

        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

    def isEmpty(self):
        return self.head == None

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count


mylist = OrderedList()
mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)

print(mylist.size())
print(mylist.search(93))
print(mylist.search(100))
6
True
False

递归

递归三定律

  • 递归算法必须有基本结束条件
  • 递归算法必须改变自己的状态并向基本结束条件演进
  • 递归算法必须递归的调用自身
In [ ]:
# 图示递归1
import turtle

myTurtle = turtle.Turtle()
myWin = turtle.Screen()

def drawSpiral(myTurtle, lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)
        myTurtle.right(90)
        drawSpiral(myTurtle,lineLen-5)

drawSpiral(myTurtle,100)
myWin.exitonclick()
In [ ]:
# 图示递归2
import turtle

def tree(branchLen,t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20)
        tree(branchLen-15,t)
        t.left(40)
        tree(branchLen-15,t)
        t.right(20)
        t.backward(branchLen)

def main():
    t = turtle.Turtle()
    myWin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    myWin.exitonclick()

main()
In [ ]:
import turtle

def drawTriangle(points,color,myTurtle):
    myTurtle.fillcolor(color)
    myTurtle.up()
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.down()
    myTurtle.begin_fill()
    myTurtle.goto(points[1][0],points[1][1])
    myTurtle.goto(points[2][0],points[2][1])
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.end_fill()

def getMid(p1,p2):
    return ( (p1[0]+p2[0]) / 2, (p1[1] + p2[1]) / 2)

def sierpinski(points,degree,myTurtle):
    colormap = ['blue','red','green','white','yellow',
                'violet','orange']
    drawTriangle(points,colormap[degree],myTurtle)
    if degree > 0:
        sierpinski([points[0],
                        getMid(points[0], points[1]),
                        getMid(points[0], points[2])],
                   degree-1, myTurtle)
        sierpinski([points[1],
                        getMid(points[0], points[1]),
                        getMid(points[1], points[2])],
                   degree-1, myTurtle)
        sierpinski([points[2],
                        getMid(points[2], points[1]),
                        getMid(points[0], points[2])],
                   degree-1, myTurtle)

def main():
   myTurtle = turtle.Turtle()
   myWin = turtle.Screen()
   myPoints = [[-100,-50],[0,100],[100,-50]]
   sierpinski(myPoints,3,myTurtle)
   myWin.exitonclick()

main()

排序和搜索

搜索

顺序搜索

逐个比较,适合无序列表

时间复杂度 $O(n)$

二分法搜索

利用有序列表的优势

时间复杂度$O(\log n)$\ 然而对于较小的n值,排序附加的消耗可能是不值得的,如果排序一次,搜索很多次,排序开销显得不那么显著。 但是对于大列表,哪怕一次排序的消耗也是巨大的,从一开始执行顺序搜索也许时最好的选择。

散列表

时间复杂度$O(1)$

具体散列函数,解决散列冲突和实现散列表的方法,参考文档

排序

冒泡排序

总的比较次数是$$\frac {n^2 - n} {2}$$,时间复杂度是$O(n^2)$

短路冒泡排序

如果整个排序过程中没有交换数据,我们可以断定列表已经拍好,可以提前结束排序。 如果一个列表只需要几次遍历就可以排序好,冒泡排序就占有优势。

选择排序

选择排序提高了冒泡排序的性能,每遍历一次列表,只交换一次数据,完成遍历后把它放到正确的位置。 依次找到最大项,次大项....... 时间复杂度是$O(n^2)$

但是由于减少了交换的次数,比冒泡排序更快。

插入排序

时间复杂度是$O(n^2)$,但是在基准测试中,插入排序有非常好的性能。 它总是保持一个位置靠前的已经排好的子表,然后一个新的数据项被插入到前边的子表中,排好的子表增加一项。 在最好的情况下,每排一个数据只需要进行一次比较,即数据已经排好的情况。 插入排序中进行的是转移,而不是数据交换,数据交换有三次赋值,而转移只有一次赋值操作。

希尔排序

又称缩小间隔排序,以插入排序为基础,将原来要排序的列表划分为一些子列表,再对每一个子列表执行插入排序,从而实现对插入排序性能的改善。 划分子列的特定方法是希尔排序的关键,在我们对子列进行排序后,列表中每个元素更加靠近它最终应该处在的位置。

乍一看,你可能会觉得希尔排序不会比插入排序要好,因为它最后一步执行了一次完整的插 入排序。但事实上,最后的一次排序并不需要很多次的比对和移动,因为正如上面所讨论的,这 个列表已经在之前的对子列的插入排序中实现了部分排序。换句话说,每个步骤使得这个列表与 原来相比更趋于有序状态。这使得最后的排序非常高效。

时间复杂度介于$O(n)$和$O(n^2)$之间。但归并的过程需要额外的存储空间。

归并排序

第一步:拆分

列表被拆分,我们已经 (在二分查找中)计算过,我们能通过logn的数量级的计算将长度为n的列表拆分。

第二步:归并

每个列表中的元素最终将被处理并被放置在排序好的列表中,所以合并操作对一个长 度为n的列表需要n的数量级的操作。因此分析结果就是,拆分需要logn数量级的操作而每次拆分 需要n数量级的操作因此最终操作的复杂度为$n\log n$。归并排序是一种$O(n\log n)$ 的算法。

快速排序

快速排序首先选择一个中值。虽然有很多不同的方法来选择这个数值,我们将会简单地选择 列表里的第一项。中值的作用在于协助拆分这个列表。中值在最后排序好的列表里的实际位置, 我们通常称之为分割点的,是用来把列表变成两个部分来随后分别调用快速排序函数的。

分区过程由设置两个位置标记开始——让我们叫它们左标记和右标记——在列表的第一项和 最后一项。分区过程的目标是把相对于中值在错误的一边的数据放到正确的一边,同时找到分割 点。

我们是这样开始的:我们不断把左标记向右移动直到它指向了一个比中值更大的数字。我们 然后把右标记向左移动直到我们找到一个比中值更小的数字。在这个时候我们就找到了两个相对 于最终的分割点在错误的位置的元素。在我们的例子中,就是93和20。现在我们可以交换这两个 元素,然后重复这个步骤了。

在右标记变得比左标记小的时候,我们停止,此时右标记在的位置就是分割点在的位置。而 中值就可以和分割点的内容互换位置而被放置在正确的位置上了。

另外,每个分割点左边的元素都比中值小,每个右边的都比它大了。这个列表就可以在分割 点被分成两半然后快速排序可以在这两个部分被分别调用了。

快排相比于归并排序,不占用额外的空间,选择的分割点影响时间复杂度,介于$O(n\log n)$和$O(n^2)$之间。

In [ ]:
# 冒泡排序
def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)
In [6]:
# 短路冒泡排序
def shortBubbleSort(alist):
    exchanges = True
    passnum = len(alist)-1
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                exchanges = True
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp
        passnum = passnum-1

alist=[20,30,40,90,50,60,70,80,100,110]
shortBubbleSort(alist)
print(alist)
[20, 30, 40, 50, 60, 70, 80, 90, 100, 110]
In [12]:
def selectionSort(alist):
    for fillslot in range(len(alist)-1,0,-1):    # fillslot是待插入的槽
        positionOfMax=0
        for location in range(1,fillslot+1):
            if alist[location]>alist[positionOfMax]:
                positionOfMax = location

        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp
        

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)
[17, 20, 26, 31, 44, 54, 55, 77, 93]
In [13]:
def insertionSort(alist):
    for index in range(1,len(alist)):
        currentvalue = alist[index]
        position = index
        while position>0 and alist[position-1]>currentvalue:
            alist[position]=alist[position-1]
            position = position-1

        alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)
[17, 20, 26, 31, 44, 54, 55, 77, 93]
In [1]:
# 希尔排序
def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:

        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,sublistcount)

        print("After increments of size",sublistcount,
                                   "The list is",alist)

        sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]
        position = i

        while position>=gap and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position = position-gap

        alist[position]=currentvalue

alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)
After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93]
After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
In [2]:
# 归并排序
def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting  [54, 26, 93, 17]
Splitting  [54, 26]
Splitting  [54]
Merging  [54]
Splitting  [26]
Merging  [26]
Merging  [26, 54]
Splitting  [93, 17]
Splitting  [93]
Merging  [93]
Splitting  [17]
Merging  [17]
Merging  [17, 93]
Merging  [17, 26, 54, 93]
Splitting  [77, 31, 44, 55, 20]
Splitting  [77, 31]
Splitting  [77]
Merging  [77]
Splitting  [31]
Merging  [31]
Merging  [31, 77]
Splitting  [44, 55, 20]
Splitting  [44]
Merging  [44]
Splitting  [55, 20]
Splitting  [55]
Merging  [55]
Splitting  [20]
Merging  [20]
Merging  [20, 55]
Merging  [20, 44, 55]
Merging  [20, 31, 44, 55, 77]
Merging  [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]
In [3]:
# 快速排序
def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
    if first<last:
        splitpoint = partition(alist,first,last)

        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
    pivotvalue = alist[first]

    leftmark = first+1
    rightmark = last

    done = False
    while not done:

        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark = leftmark + 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1

        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp

    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp


    return rightmark

alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
[17, 20, 26, 31, 44, 54, 55, 77, 93]

术语和定义

节点Node

节点(Node)是树的基本构成部分。它可以有其他专属的名称,我们称之为“键(key)”。 一个 节点可能有更多的信息,我们称之为“负载(payload)”。尽管负载信息和树的许多算法并不直接相 关,但是它对于树的应用至关重要。

边Edge

边(Edge)也是另一个树的基本构成部分。边连接两个节点,并表示它们之间存在联系。每个 节点(除了根节点)都有且只有一条与其他节点相连的入边(指向该节点的边),每个节点可能有 许多条出边(从该节点指向其他节点的边)。

根节点Root

根节点是树中唯一一个没有入边的节点。

路径Path

路径是由边连接起来的节点的有序排列。例如:动物界 → 脊索动物门 → 哺乳动物纲 → 食肉 动物目 → 猫科 → 猫属 → 家猫 就是一条路径。

子节点集Children

当一个节点的入边来自另一个节点时,我们称前者是后者的子节点,同一个节点的所有子节点 构成子节点集。

父节点Parent

个节点是它的出边所连接的所有节点的父节点。

兄弟节点Sibling

同一个节点的所有子节点互为兄弟节点,在文件系统树中节点 etc/和节点 usr/是兄弟节点。

子树Subtree

子树是一个父节点的某个子节点的所有边和后代节点所构成的集合。

叶节点Leaf Node

没有子节点的节点成为称为叶节点。

层数(Level)

一个节点的层数是指从根节点到该节点的路径中的边的数目。例如,图 6.1 中“猫属”的层数为 5。定义根节点的层数为 0。

高度Height

树的高度等于所有节点的层数的最大值。

In [4]:
# 用列表嵌套表示树
myTree = ['a',   #root
      ['b',  #left subtree
       ['d', [], []],
       ['e', [], []] ],
      ['c',  #right subtree
       ['f', [], []],
       [] ]
     ]

print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])
['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
left subtree =  ['b', ['d', [], []], ['e', [], []]]
root =  a
right subtree =  ['c', ['f', [], []], []]
In [6]:
def BinaryTree(r):
    return [r, [], []]

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

r = BinaryTree(3)
print(r)
insertLeft(r,4)
print(r)
insertLeft(r,5)
print(r)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))
[3, [], []]
[3, [4, [], []], []]
[3, [5, [4, [], []], []], []]
[5, [4, [], []], []]
[3, [9, [4, [], []], []], [7, [], [6, [], []]]]
[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]
[6, [], []]
In [ ]:
# 节点和引用实现树(链表)
class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t


    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key


r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())

参考:文档

Comments