树和二叉树遍历问题树和二叉树遍历问题

树和二叉树遍历问题 1.树和二叉树与数组(python中的列表)的关系？树和二叉树是一种结构体，而数组(python中的列表)也是一种结构体，并且两者具有相似的地方。树和二叉树在计算机中的存储可以用数组(python中的列表)来进行存储，存储的方式是树和二叉树从上到下、从左到右依次进行存储。
2.树和二叉树的遍历有四种？ (1)可以根据将树和二叉树存入到数组(python中的列表)的原则进行遍历
(2)先序遍历(先根遍历)：顺序是先根，然后是左子树，最后是右子树
(3)中序遍历(中根遍历)：顺序是左子树，然后是根，最后是右子树
(4)后序遍历(后根遍历)：顺序是左子树，然后是右子树，最后是根
遍历算法？ 【树和二叉树遍历问题】树和二叉树的定义是具有递归的韵味在其中，我们可利用递归方法解决树和二叉树的遍历问题
下列方法如图所示可知：

方法1(先序遍历)：

def preorde(a,i): //先序遍历，i表示的是根节点的逻辑位置 if i>len(a)-1: //条件终止是当根节点的逻辑位置大于数组的长度，则说明已经遍历完了树或二叉树 return -1 print(a[i]) //打印根节点的值 preorde(a,2*i+1) //打印左子树的值 preorde(a,2*i+2) //打印右子树的值 a=[] for i in input().split(' '): //输入树或二叉树的的各个节点值存入数组的顺序 a.append(eval(i)) j=0 preorde(a,0)

方法2(中序遍历)：

def inorde(a,i): //中序遍历，i表示的是根节点的逻辑位置 if i>len(a)-1: //条件终止是当根节点的逻辑位置大于数组的长度，则说明已经遍历完了树或二叉树 return -1 inorde(a,2*i+1) //先输出左子树的值 print(a[i])//在输出根节点的值 inorde(a,2*i+2) //最后输出右子树的值 a=[] for i in input().split(' '): a.append(eval(i)) j=0 inorde(a,0)

方法3(后序遍历)：

def outorde(a,i): if i>len(a)-1: return -1 outorde(a,2*i+1) outorde(a,2*i+2) print(a[i]) a=[] for i in input().split(' '): a.append(eval(i)) j=0 outorde(a,0)

重点：上述三种遍历的算法的书写是一模一样，只不过是在递归函数中中的语句先后顺序不同。只要记得其中一种，类外两种都可以写出来