二叉树学结

今天学习了线索二叉树，刚开始对这些线索该如何创建有些疑惑，后来仔细品读书中的话语，再结合图形，终于理解了。先将心得陈述如下：

首先，必须记住以下两条规则：

1、当某结点的左指针域为空时，令其指向依据某种方式遍历（前序、中序、后序）时所得到的该结点的前驱结点；

2、当某结点的右指针域为空时，令其指向依据某种方式遍历（前序、中序、后序）时所得到的该结点的后继结点。

下面，以一个实例进行详解：

一个中序线索二叉树如下所示：

那么我们怎样得到如图所示的结果呢？

一、得出该二叉树的中序（因为该图式中序线索）遍历结果；

二、根据该遍历结果的顺序，依次针对每个结点进行那两条规则的分析；

三、根据分析的结果画出虚线，即线索。

具体分析如下：

该二叉树的中序遍历结果是：c b d a f h g i e

1）、对结点c，因为其是叶子结点，所以其左、右指针域都为空；由于其左指针域为空，所以，应该指向其序列中的前驱结点，但是因为c结点已经是序列中的第一个结点，所以它没有前驱结点，只能指向null；由于其右指针域为空，所以，应该指向其序列中的后继结点b（如图c指向b的虚线）。

2）、对结点b，因为其左、右指针域均不为空，所以，不会对它画出线索。

3）、对结点d，它的情况和c相同，所以，分别指向该序列中它的前驱结点b和后继结点a。

4）、对结点a，其情况和b相同，所以，没有线索。

5）、对结点f，因为其左指针域为空，所以应该指向序列中它的前驱结点a。

6）、对结点h，其是叶子结点，所以应该指向序列中它的前驱结点f和后继结点g。

7）、对结点g，其情况和b相同，没有线索。

8）、对结点i，其是叶子结点，所以应该指向序列中它的前驱结点g和后继结点e。

9）、对结点e，因为其右指针域为空，所以应该指向序列中它的后继结点，但因为它已经是该序列中的最后一个结点，所以，指向null。

过程结束。就是这样。

二叉树学结 [篇2]

以下是我总结的关于二叉树的前、中、后序以及层次遍历的非递归算法；阐述了基本思想，代码均通过验证。(我去！sina博客有点low啊，我的类型显示不出来，以下stack后面应该是尖括号node*)

//两个栈实现非递归后续遍历树

//算法步骤：

//（1）根节点压入栈1，出栈并压入第二个栈

//（2）将入栈2节点的左节点入栈（假如左节点非空），将其右节点入栈（非空），重复步骤一，直到栈空

//需要注意两个地方，第一：将节点入栈时要判空；第二，因为使用两个栈，本来后续是先左后右，一个栈需

//要按照先右后左的方式入栈，两个栈的话则“负负得正”，先左后右入栈。这与一个栈的顺序是不同的。

void travel_postorder(node* &root)

{

if(root==null)

return;

stacks1;

stacks2;

node*cur=root;

(cur);

while(!y())

{

cur=#url#();

();

(cur);

if(cur->left!=null)

(cur->left);

if(cur->right!=null)

(cur->right);

}

while(!y())

{

cout<<#url#()->data<<' ';

();

}

}

//前序非递归遍历

//解法1：（1）跟节点入栈，出栈并打印；（2）压入出栈节点的右节点（判空），压入出栈节点的左节点（判空），重复直到栈空

void travel_preorder(node* &root)

{

if(root==null)

return;

node*cur=root;

stacks;

(cur);

while(!y())

{

cur=#url#();

();

cout<<cur->data<<' ';

if(cur->right!=null)

(cur->right);

if(cur->left!=null)

(cur->left);

}

}

//解法2：按照定义，先根后左再右；同样用栈实现，遇到根节点直接输出，并入栈保存最后回溯

//（1）跟节点入栈，当跟节点非空时一直找到最左边的'节点后回溯；

//（2）当节点为空时，栈不空时，开始回溯；将回溯节点的右节点入栈，重复过程1，直到栈空为止

void travle_preorder(node* root)

{

if(root==null)

return;

node*cur=root;

stacks;

while(cur!=null || !y())

{

if(cur!=null)

{//一直找到最左边的节点

cout<<cur->data<<' ';

(cur);

cur=cur->left;

}

else

{

//回溯

cur=#url#();

();

cur=cur->right;

}

}

}

//中序非递归遍历

//算法步骤：（1）根节点入栈，一直找到最左边的节点，然后回溯；（2）找到最左边的节点后，开始回溯，取栈顶数据输出，右节点（非空）入栈，重复直到栈空。

void travel_midorder(node* &root)

{

if(root==null)

return;

node*cur=root;

stacks;

while(cur!=null || !y())

{

if(cur!=null)//找到最左边的节点。

{

(cur);

cur=cur->left;

}

else

{//回溯

cur=#url#();

cout<<cur->data<<' ';

();

cur=cur->right;

}

}

}

//层次遍历树：

//利用队列先进先出的概念，先跟节点入队，之后出队；出队节点的左右节点（非空）入队；重复直到队空

void travel_level(node* &root)

{

if(root==null)

return;

dequend;

node*cur=root;

_back(cur);

while(!y())

{

cur=t();

cout<<cur->data<<' ';

_front();//出队

if(cur->left!=null)

_back(cur->left);//入队

if(cur->right!=null)

_back(cur->right);//入队

}

}

//如果要求层次遍历，每行按行输出，有两种常用解法

//1）使用两个队列，队列1存放当前层的节点，队列而存放下一层的节点，然后交替打印

void travel_level_towq(node* &root)

{

if(root==null)

return;

dequend1;

dequend2;

node*cur=root;

_back(cur);

while(!y() || !y() )

{

while(!y())

{

cur=t();

cout<<cur->data<<'';//输出当前队列中的节点

_front();

if(cur->left!=null)

_back(cur->left);

if(cur->right!=null)

_back(cur->right);

}

//此时nd1已经为null，nd2为其下一行应该要打印的节点

cout<<endl;//一层输出完毕，进行换行

while(!y())

{

cur=t();

cout<<cur->data<<'';//输出当前队列中的节点

_front();

if(cur->left!=null)

_back(cur->left);

if(cur->right!=null)

_back(cur->right);

}

cout<<endl;//一层输出完毕，进行换行

}

}

//2）只使用一个队列，需要两个额外的变量，来记录当前层的节点个数和下一层的节点个数。

void travel_level_oneq(node* &root)

{

if(root==null)

return;

dequend;

node*cur=root;

_back(cur);

intcur_num=1;//当前行有多少个节点，初始化为1

intnext_num=0;//下一层有多少个节点，初始为0

while(!y())

{

cur=t();

cout<<cur->data<<' ';

_front();

cur_num--;//当前层输出一个节点，节点数就减少1

if(cur->left!=null)

{

_back(cur->left);

next_num++;

}//出栈节点的左子不为空的话，压入队列，下层的节点数加1

if(cur->right!=null)

{

_back(cur->right);

next_num++;

}//出栈节点的右子不为空的话，压入队列，下层的节点数加1

if(cur_num==0)

{

cout<<endl;//当前层节点全部遍历，输出换行符

cur_num=next_num;//把下一行当做当前行处理

next_num=0;//初始化下一行为0

}

}

}