更多优质内容
请关注公众号

算法小白的入门日记(四) 二叉树的遍历-张柏沛IT博客

正文内容

算法小白的入门日记(四) 二叉树的遍历

栏目:算法专题 系列:算法小白的入门日记 发布时间:2021-11-19 19:56 浏览量:1383
本系列文章目录
展开/收起

树是一种非线性的数据结构,一棵树在逻辑上具有一个唯一的根节点,一个树节点在逻辑上具有多个指向其子节点的指针。

 

· 二叉树

二叉树就是每个节点只有两个分支的树。二叉树同样可以使用链表或者数组作为底层结构。

 

以链表为底层结构

一个节点包含3部分

存储数据的data变量

指向左子节点left指针

指向右子节点right指针

 

使用链表表示树是直观的表示方式。

 

以数组为底层结构

用数组作为底层结构的树具有如下规则:

  1. 根节点所在的数组下标是0
  2. 根据父节点下标计算子节点下标:对于某个父节点,其下标是p,那么其左子节点下标为 2p+1,右子节点下标为 2p+2
  3. 根据子节点下标计算父节点下标:反过来即可,(左节点-1)/2,右节点/2 - 1

 

对于一个满二叉树(就是树的每一个节点都有2子节点或者没有子节点而不会只有一个子节点),它的所有节点可以填满数组没有空缺。但是对于非满二叉树,用数组为底层结构就会出现空缺,例如上面的数组下标5和下标7就会出现空缺。

所以对于一个稀疏的二叉树而言,使用数组是非常浪费空间的

 

 

·二叉树的遍历

二叉树有3种深度优先遍历方式:前序遍历,中序遍历和后序遍历

              1种广度优先遍历方式:层序遍历

 

前序遍历

 

中序遍历

 

后序遍历

从动态图可以看出,前序遍历是自顶向下的遍历,中序和后序遍历是自底向上的遍历。

 

下面是3种遍历的实现(以GO实现):

package tree

import (
	"fmt"
	"zbp_struct/struct/list"
)

// 二叉树
type BTS struct{
	LeftTree *BTS;		// 左子树
	RightTree *BTS;		// 右子树
	Val interface{};		// 根节点
}

// 前序遍历
func PreOrderTraveral(tree *BTS){
	if(tree == nil){
		return;
	}
	fmt.Println(tree.Val)
	PreOrderTraveral(tree.LeftTree)
	PreOrderTraveral(tree.RightTree)
}

// 中序遍历
func InOrderTraveral(tree *BTS){
	if(tree == nil){
		return;
	}
	InOrderTraveral(tree.LeftTree)
	fmt.Println(tree.Val)
	InOrderTraveral(tree.RightTree)
}

// 后序遍历
func PostOrderTraveral(tree *BTS){
	if(tree == nil){
		return;
	}
	PostOrderTraveral(tree.LeftTree)
	PostOrderTraveral(tree.RightTree)
	fmt.Println(tree.Val)
}

 

基本上,能用递归解决的问题都能用栈解决,只需借助栈和一个指针就能做到非递归前序遍历。栈存储的是遍历到当前节点的遍历路径(存的是树节点指针)。如下所示是一个前序遍历(借助栈)的过程:

节点4既没有左孩子,也没有右孩子,我们需要回溯到上一个节点2。栈已经存储了刚才遍历的路径。让旧的栈顶元素4出栈,就可以重新访问节点2,得到节点2的右孩子节点5。此时节点2已经没有利用价值(已经访问过左孩子和右孩子),节点2出栈,节点5入栈。

 

 

代码实现如下:

// 非递归版的前序遍历
func PreOrderTraveralWithStack(tree *BTS){
	stack := list.InitLinkedList()	// 使用单向链表模拟一个栈
	curNode := tree		// 当前遍历节点为根节点,curNode指针表示即将要入栈的节点

	for curNode != nil || stack.Length > 0{	// 当前遍历节点如果为nil而且栈内没有可回溯的节点则表示遍历完所有节点
		for curNode != nil{
			fmt.Println(curNode.Val)		// 输出当前节点值
			stack.UnShift(curNode)			// 记录当前遍历过的节点路径
			curNode = curNode.LeftTree		// 遍历下一个左节点,如果没有左节点则跳出第一层for循环并回溯;如果有左节点则重复该流程
		}

		//if(stack.Length > 0){
			// 回溯
		fNode := (stack.Shift()).(*BTS)	// 弹出当前节点的父节点
		curNode = fNode.RightTree		// 以父节点的右节点作为当前遍历节点,并遍历该右节点的左子树
		//}
	}
}

 

非遍历版本的中序和后序遍历:

// 非递归版的中序遍历
func InOrderTraveralWithStack(tree *BTS){
	stack := list.InitLinkedList()	// 使用单向链表模拟一个栈
	curNode := tree		// 当前遍历节点为根节点

	for curNode != nil || stack.Length > 0{	// 当前遍历节点如果为nil而且栈内没有可回溯的节点则表示遍历完所有节点
		for curNode != nil{	// 如果当前节点有左子节点
			stack.UnShift(curNode)			// 记录
			curNode = curNode.LeftTree	// 查看其左子节点
		}

		// 如果上一个节点的左节点为nil则回溯
		fNode := (stack.Shift()).(*BTS)
		fmt.Println(fNode.Val)

		// 开始往右子树遍历
		curNode = fNode.RightTree
	}
}

// 非递归版的中序遍历(需要用到两个栈)
func PostOrderTraveralWithStack(tree *BTS){
	// 第一个栈放要遍历的根节点
	stack1 := list.InitLinkedList()
	stack1.UnShift(tree)

	// 第二个栈放已经遍历了的节点,这个栈里面的存放的节点顺序(从栈顶到栈底)必须是左右中节点
	stack2 := list.InitLinkedList()

	for stack1.Length > 0 {
		curNode := (stack1.Shift()).(*BTS)
		if curNode.LeftTree != nil{		// 如果有左子树,就需要放到stack1以待遍历该左子树
			stack1.UnShift(curNode.LeftTree)
		}
		if curNode.RightTree != nil{		// 右子树同理,不过必须是先放左子树后放右子树,因为我们要先遍历右子树后遍历左子树,先遍历的右子树节点先放到stack2,因此回溯stack2的时候就是左子树的节点比右子树节点先回溯
			stack1.UnShift(curNode.RightTree)
		}

		// 将根节点放到stack2以待回溯
		stack2.UnShift(curNode)
	}

	// 当遍历完所有树,开始回溯
	for stack2.Length >0{
		node := (stack2.Shift()).(*BTS)
		fmt.Println(node.Val)
	}
}

 

层序遍历

层序遍历是一种从上到下从左到右的遍历方式。该遍历方法需要用到一个队列,队列中存放要遍历的根节点,当该根节点取出时,它的左右子树就会入队。

 

过程如下

根节点1入列

 

根节点1出队,它的左右子节点入队

 

节点2出列,左右子节点45入列。

 

节点3出列,右子节点6入列

 

最后456没有子节点,依次出列

 

层序遍历代码实现

// 层序遍历(广度优先)
func LevelOrderTraveral(tree *BTS){
	if tree == nil{
		return
	}
	queue := list.InitLinkedList()
	queue.Append(tree)

	for queue.Length > 0 {
		curNode := (queue.Shift()).(*BTS)
		fmt.Println(curNode.Val)

		if curNode.LeftTree != nil{
			queue.Append(curNode.LeftTree)
		}
		if curNode.RightTree != nil{
			queue.Append(curNode.RightTree)
		}
	}
}

 

 

 

· 根据数组或链表构建二叉树树

这是一个把线性结构变为非线性结构的过程,也可以分为深度优先(以前序遍历为例)或者广度优先(层序遍历)2种方式构建。

 

前序遍历构建二叉树

// 根据一个数组构建一个二叉树(以前序遍历的方式)
func CreateTreeFromArr(arr []interface{}) *BTS{
    // arr = []interface{16, 14, 13, 10, nil, nil, 17, nil, nil, 15, nil, 19, nil, nil, 18, 6, nil, 27, nil, nil, 30, 29, nil, nil, nil}
	if len(arr) == 0{
		return nil
	}
	curIdx := 0
	var createTreeFromArr func(curIdx int) (*BTS, int)    // 定义一个闭包
	createTreeFromArr = func(curIdx int) (*BTS, int){     // 前序遍历
		if curIdx+1 >= len(arr) || arr[curIdx] == nil {
			curIdx++
			return nil, curIdx
		}

		node := InitTree(arr[curIdx])
		curIdx++      // 移动当前数组指针
		node.LeftTree, curIdx = createTreeFromArr(curIdx)
		node.RightTree, curIdx  = createTreeFromArr(curIdx)
		return node, curIdx
	}
	root, _ := createTreeFromArr(curIdx)
	return root
}

// 根据一个链表构建一个二叉树(以前序遍历的方式)
func CreateTreeFromList(inputList *list.LinkedList) *BTS{
	if inputList == nil || inputList.Cur == nil || inputList.Length == 0{
		return nil
	}

	// 使用前序遍历的方式构建这个树
	if inputList.Cur.Val == nil{
		inputList.Cur = inputList.Cur.Next
		return nil		// 如果未遍历完但是链表当前节点的值为nil,表示该分支到达叶子节点
	}

	// 以前序遍历的方式构建树
	tree := InitTree(inputList.Cur.Val)
	inputList.Cur = inputList.Cur.Next
	tree.LeftTree = CreateTreeFromList(inputList)
	tree.RightTree = CreateTreeFromList(inputList)
	return tree
}

 

层序遍历构建二叉树

// 根据一个链表构建一个完全二叉树(以层序遍历的方式)
func CreateTreeFromListByLevel(inputList *list.LinkedList) (tree *BTS){
    // []interface{}{16, 14, 18, 13, 15, 6, 30, 10, 17, nil, 19, nil,  27, 29, nil}
	if(inputList == nil || inputList.Length == 0){
		return tree
	}

	queue := list.InitLinkedList()		// 使用一个队列记录已经进入树但是还没有分配左右子节点的节点

	tree = InitTree(inputList.Cur.Val)	// 将链表中的第一个节点放入树中作为根节点
	queue.Append(tree)		// 将根节点放入队列中记录起来
	inputList.Cur = inputList.Cur.Next

	var curNode *BTS		// 定义一个树节点作为当前节点
	for inputList.Cur != nil && queue.Length > 0{
		curNode = (queue.Shift()).(*BTS)	// 出列节点给他分配左右节点
		if inputList.Cur.Val != nil{	// 如果链表节点的val为nil,那么对应的左节点为nil,如果没有这层判断就变成了有左节点但左节点的val为nil
			curNode.LeftTree = InitTree(inputList.Cur.Val)
			queue.Append(curNode.LeftTree)
		}

		inputList.Cur = inputList.Cur.Next
		if inputList.Cur == nil{
			break
		}

		if inputList.Cur.Val != nil {
			curNode.RightTree = InitTree(inputList.Cur.Val)
			queue.Append(curNode.RightTree)
		}
		inputList.Cur = inputList.Cur.Next
	}
	return tree
}

 




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(四) 二叉树的遍历

热门推荐
推荐新闻