二叉树基础

实现一颗二叉树二叉树遍历递归遍历先序遍历中序遍历后序遍历迭代遍历先序遍历后序遍历中序遍历层次遍历

实现一颗二叉树

节点定义
class TreeNode:
		def __init__(self, val, left, right):
				self.val = val
				self.left = left
				self.right = right
树定义 初始化一个根节点 + 节点方法
class BinaryTree():
    def __init__(self, rootObj):
        self.key = rootObj
        self.left = None
        self.right = None

		def insertRight(self, newnode):
        if self.right == None:
            self.right = BinaryTree(newnode)
        else:
            t = BinaryTree(newnode)
            t.right = self.right
            self.right = t
    
    def insertleft(self, newnode):
        if self.left == None:
            self.left = BinaryTree(newnode)
        else:
            t = BinaryTree(newnode)
            t.left = self.left
            self.left = t

    def getRightChild(self):
        return self.right

    def getLeftChild(self):
        return self.left
将数组转为二叉树
def list2tree(nums):

二叉树遍历

递归遍历

def f(node):
		if node is None:
				return
		# 1
		f(node.left)
		# 2
		f(node.right)
		# 3
分析上述代码，可见对于每一个节点，都有三次访问的机会：
notion imagenotion image
  1. 第一次是从父节点进来的
  1. 第二次是访问完左子树之后返回来的
  1. 第三次是访问完右子树之后返回来的
即任何节点都有机会去他的左子树转一圈回来，再去右子树转一圈回来。最后把信息整合。
对一棵树，不管是先序、中序还是后序，遍历走的路径是一样的，且对每个节点均三次碰面的机会，区别就在于访问节点的时机不一样

先序遍历

def PreOrderTraversal(T):
    if T is None:
			return
		else:
        print(T.key)
        PreOrderTraversal(T.left)
        PreOrderTraversal(T.right)

中序遍历

def PreOrderTraversal(T):
    if T is None:
				return
    else:
        PreOrderTraversal(T.left)
				print(T.val)
        PreOrderTraversal(T.right)

后序遍历

def PreOrderTraversal(T):
    if T is None:
				return
    else:
        PreOrderTraversal(T.left)
        PreOrderTraversal(T.right)
				print(T.val)

迭代遍历

任何递归都可以用循环迭代来实现
只需要手动操作入栈出栈即可。

先序遍历

  1. 弹出栈再打印
  1. 将右左入栈
先将某节点弹出栈再打印实现了前序遍历的前。先右后左入栈，意味着先处理左节点后处理右节点，实现了前序遍历中的左右。
# 前序遍历 模板1
def preOrder(T):
		stack = []
		stack.append(T)
		while stack:
				node = stack.pop()
				print(node.val)
				if node.right:
						stack.append(node.right)
				if node.left:
						stack.append(node.left)

# 先序遍历 模板2;从中序遍历改的
def cenOrder(T):
    stack = []
    cur = T
    while len(stack) > 0 or cur is not None:
        if cur:
						print(cur.key)
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            cur = cur.right

后序遍历

先序遍历的顺序为 前左右， 那么如果在先序遍历的时候先压左边的入栈，再压右边的入栈，那么得到的顺序为 前右左 ，可以发现，这正是后续遍历的倒序。看到倒序是不是就想到了栈。所以有了如下思路：按照先序遍历的思路来遍历二叉树，只不过压入栈的时候先压左边再压右边，然后出栈的时候，不去打印，而是压入一个辅助栈s2中，最后对s2出栈实现倒序。
def postOrder(node):
		if node is None:
				return
		stack = []
		stack.append(node)
		s2 = []   # 辅助队列，
		while(stack):
				n = stack.pop()
				s2.append(n.val)
				# 入栈时，先入左，再入右
				if n.left:
						stack.append(n.left)
				if n.right:
						stack.append(n.right)
	while s2: # 出栈，实现倒序
			print(s2.pop())

中序遍历

遍历过程：
  1. 先将左侧节点都压入栈
  1. 不满足1了，即再也没有左侧节点了，弹出栈顶节点，打印完，之后再以该节点的右节点为起点开始执行1
理解：整棵树都是可以完全被左边界分解掉的，如下图：
notion imagenotion image
压栈的时候，将每颗树的左边界都先压进去，这样到底之后，先弹出一个且打印，实现了中序遍历的左。然后开始对其右子树如法炮制。如果右子树也完了，那么再从栈中弹出一个节点。此时，已经上升到更高的一层了。再开始对其右子树的左边界入栈。
入栈的过程是向下深入的过程，出栈的过程是向上一层的过程。
def cenOrder(T):
    stack = []
    cur = T
    while len(stack) > 0 or cur is not None:
        if cur:
            stack.append(cur)
            cur = cur.left
        else :
            temp = stack.pop()
            print(temp.key)
            cur = temp.right

层次遍历

层析遍历，借助队列，一边进一边出
def levelOrder(T):
    queue = []
    queue.append(T)
    while len(queue) != 0:
        temp = queue.pop(0)
        print(temp.key)
        if temp.left is not None:
            queue.append(temp.left)
        if temp.right is not None:
            queue.append(temp.right)