go-递归实现二叉树的三种排序方式(前序、中序、后序)【详细】

阳光穿透心脏的1/2处 2022-12-05 12:21 103阅读 0赞

**目录展示：**

1、什么是二叉树？

2、二叉树的遍历

3、二叉树的三种排序方式

1、如何手写一棵二叉树？

2、三种遍历方式（递归实现）

1、先序遍历

2、中序遍历

3、后序遍历

4、文章参考：

5、附上完整代码：

--------------------

# 1、什么是二叉树？ #

*  树有很多种, 每个节点最多只能有两个子节点的叫二叉树
 *  二叉树的子节点分为左节点和右节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70][]

*  如果二叉树的所有叶子节点都在最后一层, 并且结点总数=2^n-1, n为层数, 则我们称之为满二叉数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 1][]

*  如果该二叉树的所有叶子节点(没有子节点的节点)都在最后一层或者倒数第二层, 而且最后一层的叶子节点在左边连续, 倒数第二层的叶子节点在右边连续, 我们称之为完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 2][]

# 2、二叉树的遍历 #

遍历是将二叉树中的结点信息由非线性排列变为某种意义上的线性排列。也就是说，遍历操作使非线性结构线性化。

一棵二叉树由根结点、左子树和右子树三部分组成，若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树，则二叉树的遍历方式有 6 种：DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以，只讨论三种方式：DLR（先序 遍历）、LDR（中序遍历）和 LRD（后序遍历）。

# 3、二叉树的三种排序方式 #

前序、中序和后序三种遍历方式：

*  前序遍历, 先输出父节点, 再遍历左子树和右子树
 *  中序遍历, 先遍历左子树, 再输出父节点, 再遍历右子树
 *  后序遍历, 先遍历左子树, 再遍历右子树, 最后输出父节点

## 1、如何手写一棵二叉树？ ##

1、首先要声明结点TreeNode类，代码如下：

//创建一个结构体
    type treeNode struct {
    	No          int
    	value       string
    	left, right *treeNode
    }

2、再来创建一颗二叉树：(在这里用的是先建左树在建右树的方法)

func main() {
    	//创建一棵树
    	root := treeNode{1, "A", nil, nil}
    	root.left = &treeNode{value: "B", No: 2}
    	root.right = &treeNode{value: "C", No: 3}
    	root.left.left = &treeNode{value: "D", No: 4}
    	root.left.right = &treeNode{value: "F", No: 5}
    	//定义节点两种方式都行
        root.left.right.left = &treeNode{value: "E", No: 8}
    	//root.left.right.left = new(treeNode)
    	//root.left.right.left.value = "E"
        //root.left.right.No = 8
    	root.right.left = &treeNode{value: "G", No: 6}
    	root.right.left.right = &treeNode{value: "H", No: 9}
    	root.right.right = &treeNode{value: "I", No: 7}
        //<--二叉树创建完毕-->
    
        fmt.Println("先序遍历：")
    	traverse(&root)
    	fmt.Println("")
    	fmt.Println("中序遍历：")
    	traverse1(&root)
    	fmt.Println("")
    	fmt.Println("后序遍历：")
    	traverse2(&root)
    }

## 2、三种遍历方式（递归实现） ##

### 1、先序遍历 ###

先序遍历：按照根节点->左子树->右子树的顺序访问二叉树，遵循访问顺序，递归调用

先序遍历结果为：A  BDFE  CGHI

![20200910160822505.png][]

如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 3][]

思维过程：

（1）先访问根节点A，

（2）A分为左右两个子树，因为是递归调用，所以左子树也遵循“先根节点-再左-再右”的顺序，所以访问B节点，

（3）然后访问D节点，

（4）访问F节点的时候有分支，同样遵循“先根节点-再左--再右”的顺序,

(5)访问E节点，此时左边的大的子树已经访问完毕，

(6)然后遵循最后访问右子树的顺序，访问右边大的子树，右边大子树同样先访问根节点C,

(7)访问左子树G,

(8)因为G的左子树没有，所以接下俩访问G的右子树H,

(9)最后访问C的右子树I

代码如下：

//先序遍历
    func traverse(node *treeNode) {
    	if node == nil {
    		return
    	}
    	fmt.Printf("no=%d name=%s\n", node.No, node.value)
    	traverse(node.left)
    	traverse(node.right)
    }

### 2、中序遍历 ###

中序遍历：先访问左节点，再访问根节点，最后访问右节点

思维过程：与前序同理，就不一一讲述

中序遍历结果为：DBEF    A    GHCI

![20200910161344223.png][]

如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 4][]

代码如下：

//中序遍历
    func traverse1(node *treeNode) {
    	if node == nil {
    		return
    	}
    	traverse1(node.left)
    	fmt.Printf("no=%d name=%s\n", node.No, node.value)
    	traverse1(node.right)
    }

### 3、后序遍历 ###

后序遍历：先访问左节点，再访问右节点，最后访问根节点

后序遍历的结果：DEFB  HGIC   A

小结：三种方法遍历过程中经过节点的路线一样；只是访问各个节点的时机不同。

![20200910161511298.png][]

如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 5][]

代码如下：

//后序遍历
    func traverse2(node *treeNode) {
    	if node == nil {
    		return
    	}
    	traverse2(node.left)
    	traverse2(node.right)
    	fmt.Printf("no=%d name=%s\n", node.No, node.value)
    }

--------------------

# 4、文章参考： #

1.  [二叉树的四种遍历方式][Link 1]
2.  [Go语言\_数据结构\_二叉树的三种遍历方式（前序，中序，后序）][Go]
3.  [go实现“二叉树遍历”][go]
4.  [什么是二叉树?][Link 2]
5.  [二叉树的四种遍历方式][Link 1]

--------------------

# 5、附上完整代码： #

package main
    
    import "fmt"
    
    //创建一个结构体
    type treeNode struct {
    	No          int
    	value       string
    	left, right *treeNode
    }
    
    func main() {
    	//创建一棵树
    	root := treeNode{1, "A", nil, nil}
    	root.left = &treeNode{value: "B", No: 2}
    	root.right = &treeNode{value: "C", No: 3}
    	root.left.left = &treeNode{value: "D", No: 4}
    	root.left.right = &treeNode{value: "F", No: 5}
    	root.left.right.left = &treeNode{value: "E", No: 8}
    	//root.left.right.left = new(treeNode)
    	//root.left.right.left.value = "E"
    	//root.left.right.No = 8
    	root.right.left = &treeNode{value: "G", No: 6}
    	root.right.left.right = &treeNode{value: "H", No: 9}
    	root.right.right = &treeNode{value: "I", No: 7}
    	fmt.Println("先序遍历：")
    	traverse(&root)
    	fmt.Println("")
    	fmt.Println("中序遍历：")
    	traverse1(&root)
    	fmt.Println("")
    	fmt.Println("后序遍历：")
    	traverse2(&root)
    
    }
    
    //先序遍历
    func traverse(node *treeNode) {
    	if node == nil {
    		return
    	}
    	fmt.Printf("no=%d name=%s\n", node.No, node.value)
    	traverse(node.left)
    	traverse(node.right)
    }
    
    //中序遍历
    func traverse1(node *treeNode) {
    	if node == nil {
    		return
    	}
    	traverse1(node.left)
    	fmt.Printf("no=%d name=%s\n", node.No, node.value)
    	traverse1(node.right)
    }
    
    //后序遍历
    func traverse2(node *treeNode) {
    	if node == nil {
    		return
    	}
    	traverse2(node.left)
    	traverse2(node.right)
    	fmt.Printf("no=%d name=%s\n", node.No, node.value)
    }

--------------------

> ❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ 
> 
> ❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
> 
> ❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
> 
> ❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/bb1c2af6d7934bf391d646201e3d5e5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 1]: /images/20221123/1e619fb3e68d40f38617d7fd9ddec4e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 2]: /images/20221123/49eeea8664c04da8a39226c5f826df3b.png
[20200910160822505.png]: /images/20221123/048b713b218a499c83fb63bb65e92b54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 3]: /images/20221123/2aba712e45cd43d7b8a6544553f2bdde.png
[20200910161344223.png]: /images/20221123/3a9860d6ad814552a516b2129af8ed7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 4]: /images/20221123/e273a81cf0154ae8875bb9f01b3b1489.png
[20200910161511298.png]: /images/20221123/50ec32521a19409b8737b8b271e269bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70 5]: /images/20221123/35bdf387ab3143049f24f58a53340c99.png
[Link 1]: https://www.cnblogs.com/du001011/p/11229170.html
[Go]: https://blog.csdn.net/cui_yonghua/article/details/95612113
[go]: https://blog.csdn.net/weixin_42178081/article/details/82155914
[Link 2]: https://www.jianshu.com/p/8619a89077a8