备战蓝桥杯Day24-二叉树基础
一、二叉树的概念
二叉树是一种数据结构,它由节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。这种结构类似于树的分支,通常用于在计算机科学中表示层次性数据。
树和二叉树详细知识看备战蓝桥杯Day19 - 堆排序基础知识-CSDN博客
二、二叉树的存储方式
学习堆排序的时候主要是用的顺序存储,今天学习的是链式存储,比起顺序存储更加的灵活。
使用链式存储方式手动创建上图中的二叉树,实现搜索功能:
class BiTreeNode:
def __init__(self, data): # 定义节点
self.data = data
self.lchild = None
self.rchild = None
a = BiTreeNode("A") # 创建节点
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a # 手动创建一个树,指定好左孩子和右孩子
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e
print(root.lchild.rchild.data) # 找到树中的某个节点
最后找到的节点为
三、二叉树的遍历
前序遍历
从根节点开始,先遍历左子树,后遍历右子树。使用递归函数不断调用,一直打印出子树的根节点。
遍历思路
代码实现
def pre_order(root):
if root:
print(root.data,end=",")
pre_order(root.lchild)
pre_order(root.rchild)
ps:需要加上前面的创建二叉树的代码才能跑通代码,我只是截取了前序遍历的一段代码。(下同)
最后的遍历结果:
中序遍历
遍历思路
代码实现
def in_order(root):
if root:
in_order(root.lchild)
print(root.data,end=",")
in_order(root.rchild)
遍历结果
后序遍历
遍历思路
代码实现
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data, end=",")
遍历结果
层次遍历
遍历思路
代码实现
from collections import dqueue
def level_order(root):
queue = deque() # 创建 队列
queue.append(root)
while len(queue) > 0: # 保证队不空
node = queue.popleft()
print(node.data, end=",")
# 判断有无左右孩子,分别添加左右孩子
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
运行结果
四、二叉树的还原
知道二叉树的 前序和中序遍历结果 或者是 后序和中序遍历结果,都可以把这个二叉树进行还原。
先根据前序或后序遍历结果找到树的根节点 或者是子树的根节点;
再通过中序遍历结果确定左孩子和右孩子(如果没有是不会写出来的);
不断重复上面两个步骤,直至把二叉树还原出来。
原文地址:https://blog.csdn.net/2301_78820199/article/details/136462952
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!