`
frank-liu
  • 浏览: 1684046 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二叉树分析之一:定义和遍历讨论

 
阅读更多

简介

    二叉树相关的问题和内容一直是一个比较有意思的方面。尤其是结合一些特殊的特性,比如搜索、遍历、高度等,更加让这些问题比想象的复杂。因此,对这些问题的分析也就很有必要。这里先对一些基本定义和操作做一个分析,后续会对一些其他常见的问题进行讨论。对于其中讨论的定义和方法,我们会尽力给出一个比较完备的实现。

二叉树定义

    从字面上来理解二叉树,则比较简单,它主要是由一系列的节点组成。每个节点包含有两个分别指向左右子节点的引用。它有一个唯一的节点,称为根节点,在最上面。它的左右引用分别指向同样类型的节点。通过这样递归的定义,我们可以得到一棵二叉树。最常见的二叉树节点如下图:

    它包含有3个部分,一个数据部分,保存节点的数据内容。两个引用,分别指向左边和右边的子节点。

通过这种形式定义的二叉树则如下图所示:

    从图中我们可以看出,这种二叉树的数据结构定义我们可以将它定义成两个部分,一个是节点(BinaryNode),还有一个就是二叉树(BinaryTree)。

下面是一个相对比较通用一点的节点定义:

class BinaryNode<T>
{
	T element;
	BinaryNode<T> left;
	BinaryNode<T> right;

	BinaryNode(T element)
	{
		this.element = element;
		left = right = null;
	}
}

    这里,我们将节点定义成一个单独的类。在实际实现的时候,我们也可以根据需要将其定义成一个内部类。这主要取决于我们需要使用节点的范围。

    有了节点之后,我们要定义一棵二叉树就很简单了,我们需要的是一个指向BinaryNode的节点,作为树的根节点:

 

public class BinaryTree<T>
{
    private BinaryNode<T> root;

    public BinaryTree()
    { root = null; }

    //...
}

    这里是对树的一个简略的定义,具体的方法这里先省略。

    在有的情况下,我们需要引入一个指向父节点的引用。那么在这种情况下,节点的形式就变换成如下的样子:

    对应的二叉树则转变成如下:

 

    这部分带来的变动在节点和树的定义上影响比较小,加入了父节点会在后续的插入元素和删除元素的时候影响比较大。这里,节点对应的定义代码为:

class BinaryNode<T>
{
	T element;
	BinaryNode<T> left;
	BinaryNode<T> right;
	BinaryNode<T> parent;

	BinaryNode(T element)
	{
		this.element = element;
		left = right = parent = null;
	}
}

遍历方法

    前面对于树的定义部分讲了很多,其本身的定义其实很简单。这里重点讨论二叉树的遍历。其中前序、中序和后序遍历的过程可以说本身是递归的。他们的这种本身的递归特性使得具体的实现采用递归的方式非常有效。

前序

    前序遍历指的是从一个树的根节点开始,首先处理当前节点,然后处理该节点的左子节点,再处理它的右子节点。也就是“根节点-左孩子-右孩子”这样的顺序。

递归实现

    递归实现的方法非常简单:

private void preOrderTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		System.out.print(t.element + " ");
		preOrderTraverse(t.left);
		preOrderTraverse(t.right);
	}	
}

    这里,我们按照递归的定义,首先访问当前节点,这里我们用一个简单的打印信息语句来代替。然后递归的处理当前节点的左子节点,再处理右子节点。

非递归实现

    递归实现的时候是每次访问当前节点,再接着访问它的左子节点,再访问右子节点。而用非递归的方式来实现时,我们不可避免的要使用到栈。因为我们访问完了某个节点和它的左子节点后还要返回来访问它的右子节点。这样,我们就有两种具体实现方式。

    1. 既然我们访问每个节点的时候,首先要针对这个节点进行处理,然后再处理它的左右子节点。而且是先处理左子节点再处理右子节点。我们可以在处理节点后将该节点入栈,但是出栈的时候这个节点已经被处理过了,只需要接着去处理它的右子节点就可以了。我们在碰到的节点不为空的情况下,都是执行处理该节点,然后将节点入栈的操作。一直到节点为空了,则退栈,退到前一个处理过的节点,再将该节点指向右子节点。

private void preOrderIterTraverse2(BinaryNode<T> t)
{
	if(t != null)
	{
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		while(t != null || !stack.empty())
		{
			if(t != null)
			{
				System.out.print(t.element + " ");
				stack.push(t);
				t = t.left;
			}
			else
			{
				t = stack.pop();
				t = t.right;
			}
		}
	}
}

    这里的一个重点是需要判断循环的退出条件,必须是stack为空和t也为空的时候,表示树已经遍历完了。

    2. 还有一种前序遍历的方式,和前面的方式有点细微的差别。既然我们每次访问都是当前节点,然后是左子节点,再就是右子节点。那么既然左子节点先处理,在栈里头,它们应该被后压入到栈中,而右子节点应该先被加入到栈中。我们每次遍历的时候只要把当前栈顶的元素弹出来,处理完之后再先后把它的右子节点、左子节点压栈。

private void preOrderIterTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		stack.push(t);
		while(!stack.empty())
		{
			BinaryNode<T> node = stack.pop();
			System.out.print(node.element + " ");
			if(node.right != null) stack.push(node.right);
			if(node.left != null) stack.push(node.left);
		}
	}	
}

 

中序

    中序的遍历过程比较类似,就是“左子节点-当前节点-右子节点” 。

递归实现

    有了前面的讨论,相对代码就很简单直接了:

private void inOrderTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		inOrderTraverse(t.left);
		System.out.print(t.element + " ");
		inOrderTraverse(t.right);
	}
}

 

非递归实现

    非递归的顺序来中序遍历树的时候,我们要考虑到。它每次访问的时候都是要访问左子节点。那么按照递归的定义,最开始被访问处理的一定是最左下的子节点。当这个这个节点的左子节点肯定已经为空了。同时,我们也可以把它当成一个左子节点为空的根节点。那么访问完它之后我们需要再到它的右子节点继续前面的那个一路向左的过程。每次到最左边没有其他左子节点了,我们再弹栈,处理最上面这个节点。

 

private void inOrderIterTraverse(BinaryNode<T> t) {
	if(t != null) {
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		BinaryNode<T> p = t;
		while(p != null || !stack.empty()) {
			if(p != null) {
				stack.push(p);
				p = p.left;
			} else {
				p = stack.pop();
				System.out.print(p.element + " ");
				p = p.right;
			}
		}
	}
}

    和前面的问题类似,我们的循环终止条件是p和栈为空。

 

后序

     后续的遍历则是“左子节点-右子节点-当前节点”。

递归实现

    递归实现和前面的代码类似,毫无难度:

private void postOrderTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		postOrderTraverse(t.left);
		postOrderTraverse(t.right);
		System.out.print(t.element + " ");
	}
}

    看代码,不解释。

 

非递归实现

    后序遍历的非递归实现可以说是这几种里面最难的。这里面的解决办法也不是我最初想到的,在参考了后续的实现之后才分析出来。问题的解决思路如下:对于任意一个节点,我们需要访问了它的左右子节点之后才能访问它。所以,我们可以这样来考虑,对于一个节点,先将它入栈,如果它的左右子节点为空,则可以直接访问它。另外,如果它的左右子节点都被访问过了,也可以访问它。如果不是以上的这两种情况,则先后将它的右子节点和左子节点入栈。这样保证了每次先访问左子节点,再访问右子节点。

    还有一个问题就是,在前面判断是否能访问该节点时,我们怎么知道它的左右子节点已经被访问了呢?这里用一个比较巧妙的手法,用了一个额外的引用pre。它指向当前访问节点的前一个节点。如果它的前一个节点是当前节点的左右子节点,则表示子节点已经访问完了。对于判断它的前一个节点是当前节点的左子节点这一种情况有点让人困惑。因为按照前面的遍历顺序,走了左子节点要走右子节点,如果有右子节点的话,这种条件不成立,如果没有右子节点,就会出现这种情况。

 

private void postOrderIterTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		Stack<BinaryNode<T>> stack = new Stack<BinaryNode<T>>();
		BinaryNode<T> cur, pre = null;
		stack.push(t);
		while(!stack.empty())
		{
			cur = stack.peek();
			if((cur.left == null && cur.right == null) ||
				(pre != null && (pre == cur.left || pre == cur.right)))
			{
				System.out.print(cur.element + " ");
				stack.pop();
				pre = cur;
			}
			else
			{
				if(cur.right != null)
					stack.push(cur.right);
				if(cur.left != null)
					stack.push(cur.left);
			}
		}
	}
}

    这部分的代码的难点在于要判断需要访问的节点符合的条件。

逐层遍历

    逐层遍历的过程就是一个广度优先遍历树的过程。树的结构是一层一层的。这个遍历的顺序就是从最上层开始一层一层的按照从左到右的顺序输出。这个问题看似比较困难,实际上只要把队列这个数据结构搬出来,就已经解决一大半了。

    它的过程无非就是碰到一个节点,先处理它,再分别将它的左右子节点加入到队列。这样一直从队列头取,一边从队列尾加,一直到队列为空。代码如下:

private void hierarchyTraverse(BinaryNode<T> t)
{
	if(t != null)
	{
		Queue<BinaryNode<T>> queue = new LinkedList<BinaryNode<T>>();
		queue.add(t);
		while(queue.size() > 0)
		{
			BinaryNode<T> node = queue.remove();
			System.out.print(node.element + " ");
			if(node.left != null) queue.add(node.left);
			if(node.right != null) queue.add(node.right);
		}
	}
}

 

总结

    二叉树的定义虽然大体上是要求任何一个节点包含分别指向左右子节点的引用(指针) ,但是根据一些特殊的需要,它的实现会有所调整。比如增加指向父节点的引用或者指向兄弟节点的引用。在一些问题比如求父节点或者前一个/后一个节点的情况下,这些新增加的部分能够对问题解决带来极大的便利。

    围绕二叉树的常用几种遍历形式涌现出很多有意思的问题。这里主要针对递归和非递归的实现做了一个总结。某些问题,比如说根据某两种遍历的序列来构造树、遍历结果序列和树的关系、节点的共同父节点等会在后续的文章里进一步分析。

参考资料

http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html 

http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?s=books&ie=UTF8&qid=1363617759&sr=1-1&keywords=introduction+to+algorithms

http://www.amazon.com/Data-Structures-Problem-Solving-Using/dp/0321541405/ref=sr_1_1?s=books&ie=UTF8&qid=1363617891&sr=1-1&keywords=data+structures+%26+problem+solving+using+java

  • 大小: 2.7 KB
  • 大小: 8.7 KB
  • 大小: 3.4 KB
  • 大小: 13.4 KB
分享到:
评论

相关推荐

    非线性数据结构:二叉树的遍历算法详解

    最后,讨论了二叉树遍历在查找元素、复制二叉树和层次遍历等方面的应用,并对其时间复杂度和空间复杂度进行了分析。 适合人群:具备一定编程基础,正在学习或从事数据结构相关工作的研发人员。 使用场景及目标:① ...

    二叉树的中序线索化和遍历

    我们定义了一个结构体BiThrNode来表示二叉树的每个节点,该结构体包含一个数据元素和两个指针,分别指向其左子节点和右子节点。 在CreateBiTree函数中,我们使用递归的方式来创建一个二叉树。我们首先读取用户输入...

    建一棵二叉树,并分别用先序和中序遍历二叉树

    1. **定义节点结构**:在编程中,我们需要定义一个结构来表示二叉树的节点,通常包括数据部分(例如整数)和两个指针,分别指向左子节点和右子节点。例如,在Python中,可以定义如下: ```python class TreeNode: ...

    数据结构课程设计:二叉树的存储和遍历、排序

    本课程设计主要讨论了二叉树的存储和遍历、排序等内容。二叉树是一种特殊的树结构,每个结点最多有两个子树,通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找...

    二叉树的先序中序后序遍历

    这里我们将详细讨论三种主要的遍历方法:先序遍历、中序遍历和后序遍历,以及如何使用递归和非递归方法实现它们。 **先序遍历** 是一种访问二叉树节点的方法,其顺序为:根节点 -&gt; 左子树 -&gt; 右子树。递归实现先序...

    二叉树建立以及递归、非递归遍历

    在计算机科学中,二叉树是一种基础的数据结构,它的每个节点最多有两个子节点,通常分为左子节点和右子节点。二叉树广泛应用于搜索、排序、表达式求解等多种场景。本主题将深入探讨如何在C语言中构建二叉树以及如何...

    二叉树建立遍历

    二叉树的建立通常有两种方式:一种是通过序列化数据(如字符串或数组)来构建,另一种是动态创建。例如,给定一个序列化的二叉树表示,如“4,2,5,1,3”,我们可以通过这个序列来构建一棵二叉树,其中4是根节点,2和5...

    二叉树的建立与遍历

    对于递归建立二叉树,我们可以定义一个函数,该函数接收一个元素和两个子集(通常是元素的子序列),然后创建一个新节点,并分别对子集递归调用该函数来建立左右子树。 ```python class Node: def __init__(self, ...

    数据结构层序中序遍历构建二叉树

    本篇内容主要讨论如何通过给定的中序遍历序列和层序遍历序列来构建一颗二叉树,并提供了具体的实现代码。 #### 二、二叉树的遍历方法简介 在讨论具体问题之前,先简单回顾一下二叉树的几种基本遍历方式: 1. **...

    二叉树的建立遍历以及线索化二叉树

    今天,我们将讨论二叉树的建立、遍历和线索化。 二叉树的建立 在建立二叉树之前,我们需要定义二叉树结点类型。典型的二叉树结点类型包括数据域、左孩子、右孩子、左线索和右线索。我们使用结构体来定义二叉树结点...

    树/二叉树 各种遍历源代码(C++)

    **迭代器遍历**是面向对象编程中常用的一种方式,通过定义迭代器类,使得遍历操作更加灵活和易用。在C++中,可以实现一个自定义迭代器,支持begin()和end()方法,以及++操作,以符合STL的迭代器接口,从而实现对树或...

    二叉树_二叉树遍历_二叉树_

    二叉树的遍历是其核心操作之一,主要包括前序遍历、中序遍历和后序遍历。 1. 前序遍历(根-左-右):首先访问根节点,然后递归地遍历左子树,最后遍历右子树。这种遍历顺序常用于复制二叉树。 2. 中序遍历(左-根-...

    按前序遍历创建二叉树

    例如,在Python中,你可以定义一个二叉树节点类,包含节点值、左子节点和右子节点属性,然后编写一个函数接收前序遍历序列并返回构建好的二叉树根节点。此外,还可以编写另一个函数进行中序遍历,验证结果的正确性。...

    数据结构二叉树遍历.doc

    遍历二叉树的规则可以有 NLR、LNR、LRN 三种遍历和 NRL、RNL、RLN 三种逆遍历方式,但通常限定先左后右,仅讨论前三种遍历,分别称之为前序遍历、 中序遍历和后序遍历。 前序遍历 前序遍历是指最先访问根结点,然后...

    二叉树的二叉链实现及遍历

    每个节点(通常称为Node)包含三个字段:一个用于存储数据,两个指针分别指向左子节点和右子节点。如果某子树为空,对应的指针值为null。 在`Node.java`文件中,我们可以预见到如下类定义: ```java class Node { ...

    求二叉树的深度(后序遍历)

    二叉树是计算机科学中数据结构的一种重要类型,它由节点构成,每个节点最多有两个子节点,分别称为左子节点和右子节点。在解决“求二叉树的深度”这个...同时,这也是一个很好的练习,帮助你提升分析和解决问题的能力。

    二叉树创建及遍历

    二叉树是一种重要的数据结构,它由节点组成,每个节点有两个子节点,分别称为左子节点和右子节点。在计算机科学中,二叉树常用于实现搜索、排序和其他算法,因为它们允许快速访问和操作数据。在这个项目中,我们将...

    二叉树的创建和各种遍历递归和非递归

    二叉树是计算机科学中一种重要的数据结构,它由节点(也称为结点)组成,每个节点最多有两个子节点,通常分别称为左子节点和右子节点。在本主题中,我们将深入探讨如何使用C语言实现二叉树的创建、不同类型的遍历...

    利用两种遍历结果恢复二叉树并打印

    通过以上分析,我们可以看出,这个项目涵盖了数据结构中的核心知识点,包括二叉树的遍历方法(前序、中序、后序)以及层次遍历(广度优先搜索),同时结合了实际问题的解决,提升了编程技能和算法理解。对于学习和...

    二叉树的遍历及线索化

    在提供的文件中,`Tree.cpp`可能包含了二叉树遍历和线索化的C++实现,而`Tree.dsw`和`Tree.h`则可能是项目工程文件和头文件,其中可能包含了二叉树结构的定义和相关函数声明。通过阅读这些代码,可以更深入地理解...

Global site tag (gtag.js) - Google Analytics