树木的储存、表达和经历
树木的储存和表现
顺序存储：将数据结构存储在一个固定的数组中，但在遍历速度方面有一定的优势，但由于空间相对较大，它是一种非主流的二叉树。二叉树通常以链式存储。
以0表示某个节点为空。
节点结构：
建立二叉树
classNode(object): """封装二叉树节点""" def__init__(self,element=None,lchild=None,rchild=None): self.element=element self.lchild=lchild self.rchild=rchild classTree(object): """封装二叉树""" def__init__(self,root=None): self.root=root def__add__(self,element): #包装插入节点 node=Node(element) #1.判断是否为空，赋值根结点 ifnotself.root: self.root=node #2.如果有跟结点，将根结点放入队列 else: queue=[] #将根结点放入队列中 queue.append(self.root) #遍历队列中的所有节点 #这里的循环每次都是从根结点向下循环的 whilequeue: #3.弹出队列中的第一个元素(第一次弹出是根节点，然后是根的左节点，根的右节点，依次类推) cur=queue.pop(0) ifnotcur.lchild: cur.lchild=node return elifnotcur.rchild: cur.rchild=node return else: #左右子树存在时，将左右子树添加到队列中。 queue.append(cur.lchild) queue.append(cur.rchild)
二叉树遍历
遍历是指对树中所有结点的信息的访问，即依次访问树中每个结点一次，只访问一次。我们称这种对所有节点的访问为遍历(traversal)
广度优先遍历(层次遍历)
1、2、3、4、5、6
defbreadth_travel(self): """利用队列实现树的层次遍历""" ifself.root==None: return #将二叉树的节点依次放入队列中，以访问队列的形式实现树的遍历 queue=[] queue.append(self.root) whilequeue: node=queue.pop(0) print(node.element,end=',') ifnode.lchild!=None: queue.append(node.lchild) ifnode.rchild!=None: queue.append(node.rchild) print()
深度优先遍历
有三种方法可以优先考虑深度遍历：
先序遍历(根)->左->右）：先访问根结点，再先遍历左子树，再先遍历右子树，
中序遍历(左)->根->右）：先中序遍历左子树，再访问根结点，最后中序遍历右子树，
后序遍历(左)->右->根）：先后顺序遍历左子树，再顺序遍历右子树，最后访问根结点。
先序遍历： 1 2 4 5 3 6 7
中序遍历： 4 2 5 1 6 3 7
后序遍历： 4 5 2 6 7 3 1
递归实现先序遍历
#深度优先遍历：先序遍历-左右根 defpreorder(self,root): """递归实现先序遍历""" ifnotroot: return print(root.element,end=',') self.preorder(root.lchild) self.preorder(root.rchild)
递归实现中序遍历
#深度优先遍历：中序遍历-左右两根 definorder(self,root): """递归实现中序遍历""" ifnotroot: return self.inorder(root.lchild) print(root.element,end=',') self.inorder(root.rchild)
递归实现后序遍历
#深度优先遍历：后序遍历-左右根 defpostorder(self,root): """递归实现后序遍历""" ifnotroot: return self.postorder(root.lchild) self.postorder(root.rchild) print(root.element,end=',')
测试代码：
if__name__='__main__':
binaryTree=Tree()
foriinrange(7):
binaryTree.__add__(i+1)
#广度优先遍历
print("广度优先：")
binaryTree.breadth_travel()
#深度优先，先序遍历
root=binaryTree.root
binaryTree.preorder(root)
print('深度优先-先序遍历')
binaryTree.inorder(root)
print('深度优先-中序遍历#39;)
binaryTree.postorder(root)
print('深度优先-后序遍历#39;)广度优先： 一、二、三、四、五、六、七 1、2、4、5、3、6、7深度优先-先序遍历 4、2、5、1、6、3、7深度优先-中序遍历 4、5、2、6、7、3、1深度优先-后序遍历
和我们预期的结果完全一样。
想了解更多Python，请移动Python视频教程继续学习！！