数据结构可以说是编程的内功心法，掌握好数据结构真的非常重要。
目前基本上流行的数据结构都是c和c++版本的，
我最近在学习python，尝试着用python实现了二叉树的基本操作。
写下一篇博文，总结一下，希望能够对其他好伙伴带来一点借鉴价值~~
温馨提示：学习算法要先懂思想，后学代码。思想学会才是自己的。背下来代码，容易忘。
代码捉襟见肘，欢迎批评指正 ^.^ 先谈一下二叉树： 二叉树是常用的存储数据的方式。除了根节点之外，每个节点都有一个父节点，最多有两个子节点，左孩子和右孩子
对于二叉树有如下操作： 1 添加节点： 按层次添加，优先选择层次最小的，并且优先靠左添加节点
2 树的遍历： 分为 深度优先 和 广度优先 构造一个二叉树当作例子 根是1 左孩子2 右孩子3 ...... 1
2 3
4 5 6 7 广度优先遍历： 按照层次由低到高，先左后右的顺序 1 2 3 4 5 6 7
编程实现的思想： 开启一个队列 queue（队列是数据结构中先进先出的实现，队列的朋友需要再看一看数据结构链表的知识）
1 把 树根 1 放进队列 队列变成 1
2 重复执行：从队列取一个队头出队一个节点，如果它有左孩子，把左孩子放入队列，如果他有右孩子把右孩子放入队列。输出当前节点的数值
一直到队列空了为止
2.1 从队头取出1 把1输出，把1的左孩子和右孩子添加到队列 队列变成： 2 3
2.2 从对头取出2 把2输出，把2的左孩子和右孩子添加到队列 队列变成： 3 4 5
2.3 从对头取出3 把3输出， 把3的左孩子右孩子添加到队列， 队列变成： 4 5 6 7
2.4 从对头取出4 把4输出，它没有左孩子和右孩子 不用入队列
2.5 从对头取出5 把5输出， 它没有左孩子右孩子 不用入队列
2.6 从对头取出6 把6输出， 它没有左孩子右孩子 不用入队列
2.7 从对头取出7 把7输出， 它没有左孩子右孩子 不用入队列
2.8 队列空了，结束 深度优先遍历：又分为三种：先序 中序 后序 先序遍历（先输出根）： 按照 根 左 右 的顺序 遍历结果：1 2 4 5 3 6 7
1 对于树根1，先输出1，然后再遍历它的左子树和右子树
1.1 对于左子树2是树根先输出2，再遍历它的左子树和右子树
1.1.1 对于左子树4 树根4输出，没有左右子树 不用向下遍历
1.1.2 对于右子树5 树根5输出 没有左右子树 不用向下遍历
1.2 对于右子树3树根3 输出3， 在遍历它的左子树和右子树
1.2.1 对于左子树6 输出根6 没有左右子树 不用向下遍历
1.2.2 对于右子树7 输出根7 没有左右子树 不用向下遍历
总结：先输出根，然后对左子树当成新树遍历，然后对右子树当成新树遍历，循环遍历到没有子树 中序遍历(中间输出根)：按照 左 根 右 的顺序 遍历结果：4 2 5 1 6 3 7
1 对于树1 先对左子树遍历 再输出根 最后对右子树遍历
1.1 对于左子树2 先对左子树遍历 再输出根 最后对右子树遍历
1.1.1 对于左子树4，没有孩子了 输出树根 4
1.1.2 遍历完左子树了 输出根 2 再遍历右子树
1.1.3 对于右子树5，没有孩子了 输出树根 5
1.2 左子树2遍历完了 输出根 1 再遍历右子树 3
1.3 对于右子树3 先对左子树遍历 再输出根 最后对右子树遍历
1.3.1 对左子树6 没有孩子了 输出根6
1.3.2 左子树6遍历完了 输出根 3 再遍历右子树7
1.3.3 对于右子树7 没有孩子 输出根 7 后序遍历(最后输出根)：按照 左 右 根 的顺序 遍历结果：4 5 2 6 7 3 1
1 对于树 先遍历左子树 再遍历右子树 最后输出根
1.1 对于左子树2 先遍历左子树 再遍历右子树 最后输出根
1.1.1对于左子树4 没有孩子了 输出根 4
1.1.2对于右子树5 没有孩子了 输出根 5
1.1.3左子树 右子树遍历完了输出根 2
1.2 对于右子树3 先遍历左子树 再遍历右子树 最后输出根
1.2.1 对于左子树6 没有孩子了 输出根 6
1.2.2 对于右子树7 没有孩子了 输出根 7
1.2.3 左右子树遍历完了 最后输出根 3
1。3 左右子树遍历完了 最后输出根 1 接下来 我们用python来实现一下各种操作！！！
#一个节点的数据类型，包含左子孩子节点指针 右孩子节点指针 和值
class Node(object):
def __init__(self , item):
self.left = None #指向左子节点
self.right = None #指向右子节点
self.item = item #保存值 #树的类
class Tree(object):
def __init__(self):
self.root = None #保存树根所在位置
#添加节点方法，按照层次由低到高，优先靠左的思想添加
def add(self , item ):
node = Node(item) #首先创建一个节点
#如果树还没有树根
if self.root is None:
self.root = node
else :
# 这里需要用到广度优先遍历的思想来找第一个可以添加节点的位置
# 开一个队列用于广度优先搜索 先把树根放进去
queue = [ self.root ]
#循环操作：
# 出队一个节点，如果它没有左海子，为它添加左孩子 退出 否则 左孩子入队列
# 如果他没有右孩子，为它添加右孩子 退出 否则 右孩子如队列
#如果队列里面有元素我们就一直操作。队列空了就退出来（这个只是保险条件，一般队列还没空就找到空位创建节点然后退出了）
while queue :
#取出队节点
temp = queue.pop(0)
#如果没有左孩子 我们 添加左孩子后退出
if temp.left is None:
temp.left = node
return
#如果有左孩子 我们把左孩子入队列
else:
queue.append(temp.left) #如果没有右孩子 我们添加右孩子 然后退出
if temp.right is None:
temp.right = node
return
# 如果有右孩子 我们把右孩子入队列
else :
queue.append( temp.right )
# 广度优先遍历
def breadth_travel(self):
#开启一个队列 把树根放进去
queue=[ self.root ]
#循环操作：从对头取出节点，把值输出后 把他们的左孩子右孩子添加到队列里，一直到队列空了，说明遍历结束
# 只要队列不是空的 我们就一直遍历
while queue :
#从队列头取出一个元素
temp = queue.pop(0)
#输出节点的值
print( temp.item,end=" " )
#如果节点有左孩子 就把左孩子追加到队列
if temp.left is not None:
queue.append( temp.left )
#如果节点有右孩子 就把右孩子追加到队列
if temp.right is not None:
queue.append(temp.right)
#最后来一个换行
print()
#先序遍历 按照 根 左 右 进行遍历
# 把当前子树的树根传进去做参数
def preOder(self , node):
#如果传进来的十个None，说明上一个节点 没有左孩子或者右孩子 传进来一个None 那就不遍历这个节点
if not node:
return
#先把根的值输出来
print(node.item,end=" ")
#然后对左孩子进行遍历
self.preOder( node.left )
#然后对右孩子遍历
self.preOder( node.right )
#中序遍历 按照 左 根 右 的顺序进行遍历
# 传入当前要遍历的子树的根
def inOrder(self, node):
#当传入的子树是None 说明上一个节点没有这个子树 传进来了None 此时不用遍历它了
if not node:
return None
#先对左子树进行遍历
self.inOrder( node.left )
#再输出自己的数值
print( node.item,end=" " )
#最后对右子树进行遍历
self.inOrder(node.right)
#后序遍历 按照 左 右 根 的顺序进行遍历
# 把当前子树的树根传进去做参数
def postOrder(self,node):
#如果传进来一个None 说明上一个节点没有这可子树，这时候不用遍历
if not node :
return
#先对左子树进行遍历
self.postOrder(node.left)
#再对右子树进行遍历
self.postOrder(node.right)
#最后输出自己的值
print( node.item,end=" " ) #我们再封装一下，在外部调用自己的三个深度优先遍历可以不传入自己的根
def preOrder_travel(self):
self.preOder(self.root)
def inOrder_travel(self):
self.inOrder( self.root )
def postOrder_travel(self):
self.postOrder(self.root) if __name__ == '__main__':
tree = Tree()
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.breadth_travel() # 1 2 3 4 5 6 7
tree.preOrder_travel() #1 2 4 5 3 6 7
print()# 回车换行
tree.inOrder_travel() #4 2 5 1 6 3 7
print()# 回车换行
tree.postOrder_travel() #4 5 2 6 7 3 1
java实现：
import java.util.LinkedList;
import java.util.Queue;
//二叉树的实现
class Main {
public static void main(String[] args) {
Tree tree = new Tree();
tree.append(1);
tree.append(2);
tree.append(3);
tree.append(4);
tree.append(5);
tree.append(6);
tree.append(7);
tree.breadth();
tree.preOrder_travel();
tree.inOrder_travel();
tree.postOrder_travel();
} }
//一棵树的叶子节点
class Node{
int value;
Node left = null;
Node right = null;
public Node(int value){
this.value = value;
}
} public class Tree{
private Node root = null;
public Node getRoot(){
return this.root;
}
//添加叶子节点方法
public void append( int value ){
Node node = new Node(value);
//如果根节点是空的，就添加根节点
if( this.root == null ){
this.root = node;
//根节点不是空的 按层次遍历 找到最浅层次最靠左的位置把节点放进去
}else{
Queue<Node> queue = new LinkedList<Node>();
queue.offer(this.root);
while( ! queue.isEmpty() ){
Node cur = queue.poll();
if( cur.left == null ){
cur.left = node;
break;
}else{
queue.add(cur.left);
}
if( cur.right == null ){
cur.right = node;
break;
}else{
queue.add(cur.right);
}
}
}
}
//广度优先遍历
public void breadth( ){
Queue<Node> queue = new LinkedList<Node>();
queue.add(this.root);
while( !queue.isEmpty() ){
Node cur = queue.poll();
System.out.print(cur.value+" ");
if(cur.left!=null){
queue.add(cur.left);
}
if(cur.right!= null){
queue.add(cur.right);
}
}
System.out.println();
}
//深度优先遍历
//先序遍历
public void preOrder_travel(){
preOrder(this.root);
System.out.println();
}
private void preOrder(Node root){
if(root == null){
return;
}
System.out.print( root.value + " " );
preOrder(root.left);
preOrder(root.right);
}
//中序遍历
public void inOrder_travel(){
inOrder(this.root);
System.out.println();
}
private void inOrder(Node root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print( root.value + " " );
inOrder(root.right);
}
//后序遍历
public void postOrder_travel(){
postOrder(this.root);
System.out.println();
}
private void postOrder(Node root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print( root.value + " " );
}
}
对于初学者来说，二叉树的遍历可能有点难，不过没有关系，认真理解算法思想，一点一点来，总会理解的！
对于算法的实现，不同的人实现方式多少有些不一样，如果有好伙伴有更好的方案，也欢迎沟通交流~~