算法学习-二叉树基础

本博客在学习北京大学陈斌老师《数据结构与算法》MOOC课程中总结反思形成。

二叉树的鼎鼎大名人尽皆知 它整体的思维逻辑也符合人类整理归纳的习惯 因此在理解概念上的难度并不大。

树作为一种典型的“非线性结构” 具备两个显著的特征

语言体系 它仍然具备唯一性。

树作为一种简洁的表达方式 具备很多术语归纳如下

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]

class BinarryTree:
 def __init__(self,rootObj):
 self.key rootObj
 self.leftChild None
 self.rightChild None
 def insertLeft(self,newNode):
 if self.leftChild None:
 self.leftChild BinarryTree(newNode)
 else:
 t BinarryTree(newNode)
 t.leftChild self.leftChild
 self.leftChild t
 def insertRight(self,newNode):
 if self.rightChild None:
 self.rightChild BinarryTree(newNode)
 else:
 t BinarryTree(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

项目需求
从全括号表达式构建表达式解析树 利用表达式解析树对表达式求值 从表达式解析树恢复原表达式的字符串形式

梳理逻辑
如果当前单词是“ ” 为当前节点添加一个新节点作为其左子节点 当前节点下降为这个新节点
如果当前单词是操作符“ - * /” 将当前节点的值设为此符号 为当前节点添加一个新节点作为其右子节点 当前节点下降为这个新节点
如果当前单词是操作数 将当前节点的值设为此数 当前节点上升到父节点
如果当前单词是“ ” 则当前节点上升到父节点

要点 当前节点的跟踪
基本操作

创建左右子树 调用insertLeft/Right
当前节点设置值 调用setRootval
下降到左右子树 调用getLeft/RightChild
用一个栈 记录跟踪父节点
当前节点下降时 将下降前的节点push入栈;当前节点需要上升到父节点时 上升到pop出栈的节点

from pythonds.basic.stack import Stack
import operator
class BinarryTree:
 def __init__(self, rootObj):
 self.key rootObj
 self.leftChild None
 self.rightChild None
 def look(self):
 print(self.key, self.leftChild, self.rightChild)
 def insertLeft(self, newNode):
 if self.leftChild None:
 self.leftChild BinarryTree(newNode)
 else:
 t BinarryTree(newNode)
 t.leftChild self.leftChild
 self.leftChild t
 def insertRight(self, newNode):
 if self.rightChild None:
 self.rightChild BinarryTree(newNode)
 else:
 t BinarryTree(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