数据结构-二叉树遍历

发表于 2019-03-05 分类于计算机基础，数据结构阅读次数： Disqus：本文字数： 4.7k 阅读时长 ≈ 4 分钟

数据结构-二叉树遍历部分,包括 python 源代码
参考资料
https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
<维基等>
更新
1
19.03.05 初始

导语

贪心法涉及到的图论部分,头大,计算下工作量,基本等于数据结构部分重新刷完了.
直接开始数据结构部分,图论等按顺序来.
下一篇是排序.

二叉树基础

二叉树（英语：Binary tree）是每个节点最多只有两个分支的树结构。通常分支被称作“左子树”或“右子树”.
满二叉树/完全二叉树
- 深度为 $k$ 的二叉树最多拥有 $2^{k+1}-1$ 个节点.(根节点的深度定义为 $k_0 = 0$ )
- 深度为 $k$ 拥有 $2^{k+1}-1$ 个节点的二叉树称为满二叉树(每一层都满员)
- 而深度为 $k$ 有 $n$ 个节点的二叉树,当且仅当每个节点都与深度为 $k$ 的满二叉树序号由1到n一一对应时,称为完全二叉树.(前k-1层,满员,第k层,叶子节点聚集在左侧,可能满也可能不满.)
二叉树存储
- 数组
  - 第k个节点,对应左子树为2k,右子树为2k+1.第0个节点置空.(随意)
  - 非常方便寻址,且块存储,不易碎片化.
  - 对于非满/完全二叉树,有可能存在空间浪费.
- 二叉链表
  - 仿照二叉树结构,在数据结构中加入左子树/右子树地址.
  - 节约空间,易碎片化,寻址等稍繁琐.
- 数据结构中可能会用到两种,这里随机生成一个数组,且在数据结构定义中加入左/右子树地址,并链接.
- 数据值域因为python为动态语言,这里限定仅为 int 和 str 类型.

源码:

#!/usr/bin/python3
import random
import copy
import string


class BtNode(object):
    def __init__(self, value=0, leftBt=None, rightBt=None):
        self.value = value
        self.lchild = leftBt
        self.rchild = rightBt

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self, values):
        if not (isinstance(values, int) or isinstance(values, str)):
            raise ValueError('value must be an int or str!')
        self._value = values

    @property
    def lchild(self):
        return self._lchild

    @lchild.setter
    def lchild(self, leftBt):
        if not (isinstance(leftBt, BtNode) or (leftBt is None)):
            raise ValueError('leftBt must be BtNode')
        self._lchild = leftBt

    @property
    def rchild(self):
        return self._rchild

    @rchild.setter
    def rchild(self, rightBt):
        if not (isinstance(rightBt, BtNode) or (rightBt is None)):
            raise ValueError('rightBt must be BtNode')
        self._rchild = rightBt


class Btree(object):
    def __init__(self, len=50):
        self.__len = len
        self.__arr = [BtNode() for i in range(self.__len)]
        self.__link()

    def Cr_int(self):
        self.__arr = list(map(self.__randomint, self.__arr))
        return copy.deepcopy(self.__arr)

    def Cr_str(self, len=50):
        self.__arr = list(map(self.__randomstr, self.__arr))
        return copy.deepcopy(self.__arr)

    def __link(self):
        for i in range(self.__len - 1, 1, -1):
            if (i % 2) == 1:
                self.__arr[i // 2].rchild = self.__arr[i]
            else:
                self.__arr[i // 2].lchild = self.__arr[i]

    def __randomint(self, btNode):
        btNode.value = random.randint(0, 100)
        return btNode

    def __randomstr(self, btNode):
        btNode.value = ''.join(random.choices(string.ascii_lowercase, k=1))
        return btNode

    @classmethod
    def visit(self, node):
        return print(node.value, end=' ')

测试代码

#!/usr/bin/python3
import unittest
from bt_base import BtNode, Btree


class test_bt(unittest.TestCase):
    def test_BtNode(self):
        tmp = BtNode()
        self.assertEqual(tmp.value, 0)
        self.assertEqual(tmp.lchild, None)
        self.assertEqual(tmp.rchild, None)
        with self.assertRaises(ValueError):
            tmp.value = 1.3
        with self.assertRaises(ValueError):
            tmp.lchild = 1.3
        with self.assertRaises(ValueError):
            tmp.rchild = 1.3

    def test_Btree(self):
        bt = Btree()
        tmp = bt.Cr_int()
        for node in tmp:
            self.assertTrue(isinstance(node, BtNode))
            self.assertTrue(isinstance(node.value, int))
            self.assertTrue(isinstance(node.lchild, (BtNode, type(None))))
            self.assertTrue(isinstance(node.rchild, (BtNode, type(None))))
        tmp = bt.Cr_str()
        for node in tmp:
            self.assertTrue(isinstance(node, BtNode))
            self.assertTrue(isinstance(node.value, str))
            self.assertTrue(isinstance(node.lchild, (BtNode, type(None))))
            self.assertTrue(isinstance(node.rchild, (BtNode, type(None))))

二叉树遍历

二叉树遍历按遍历方式分为3种,每种又有递归和循环两种写法.
- 先序遍历: 节点值->左子树->右子树
- 中序遍历: 左子树->节点值->右子树
- 后序遍历: 左子树->右子树->节点值
代码比较简单,配合python与伪代码相差不大,没写注释.🧐

代码

递归

@classmethod
def Pre_Order_Re(self, root):
    if root:
        Btree.visit(root)
    if root.lchild:
        self.Pre_Order_Re(root.lchild)
    if root.rchild:
        self.Pre_Order_Re(root.rchild)

@classmethod
def In_Order_Re(self, root):
    if root.lchild:
        self.In_Order_Re(root.lchild)
    if root:
        Btree.visit(root)
    if root.rchild:
        self.In_Order_Re(root.rchild)

@classmethod
def Post_Order_Re(self, root):
    if root.lchild:
        self.Post_Order_Re(root.lchild)
    if root.rchild:
        self.Post_Order_Re(root.rchild)
    if root:
        Btree.visit(root)

循环

    @classmethod
def Pre_Order_loop(self, root):
    stack = []
    stack.append(root)
    while stack:
        p = stack.pop()
        Btree.visit(p)
        if p.rchild:
            stack.append(p.rchild)
        if p.lchild:
            stack.append(p.lchild)

@classmethod
def In_Order_loop(self, root):
    stack = []
    p = root
    while stack or p:
        while p:
            stack.append(p)
            p = p.lchild
        if stack:
            p = stack.pop()
            Btree.visit(p)
            p = p.rchild

@classmethod
def Post_Order_loop(self, root):
    stack = []
    stackb = []
    stack.append(root)
    while stack:
        p = stack.pop()
        stackb.append(p)
        if p.lchild:
            stack.append(p.lchild)
        if p.rchild:
            stack.append(p.rchild)
    while stackb:
        Btree.visit(stackb.pop())

说明:
- 递归代码非常明了,但没有尾递归优化的语言,可能存在堆栈溢出.
- 先序遍历循环写法,利用了一个堆栈来实现,受益于python,与伪代码非常接近.
- 中序遍历循环写法,与先序遍历循环相似,特殊一点的时,在遍历完根节点的左子树时,堆栈为空,但p不为空,循环条件判断时,针对这种情况要做相应处理.
- 后序遍历循环写法,可以实现的方式不唯一,这里是更改先序遍历,将顺序更改为后序遍历的逆过程,不断将结果压入另一个堆栈,最后从这个堆栈中释放,得到后序遍历的正确顺序.