二叉树学结
今天学习了线索二叉树，刚开始对这些线索该如何创建有些疑惑，后来仔细品读书中的话语，再结合图形，终于理解了。先将心得陈述如下：
首先，必须记住以下两条规则：
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;
s1.push(cur);
while(!s1.empty())
{
cur=#url#();
s1.pop();
s2.push(cur);
if(cur->left!=null)
s1.push(cur->left);
if(cur->right!=null)
s1.push(cur->right);
}
while(!s2.empty())
{
cout<<#url#()->data<<' ';
s2.pop();
}
}
//前序非递归遍历
//解法1：（1）跟节点入栈，出栈并打印；（2）压入出栈节点的右节点（判空），压入出栈节点的左节点（判空），重复直到栈空
void travel_preorder(node* &root)
{
if(root==null)
return;
node*cur=root;
stacks;
s.push(cur);
while(!s.empty())
{
cur=#url#();
s.pop();
cout<<cur->data<<' ';
if(cur->right!=null)
s.push(cur->right);
if(cur->left!=null)
s.push(cur->left);
}
}
//解法2：按照定义，先根后左再右；同样用栈实现，遇到根节点直接输出，并入栈保存最后回溯
//（1）跟节点入栈，当跟节点非空时一直找到最左边的节点后回溯；
//（2）当节点为空时，栈不空时，开始回溯；将回溯节点的右节点入栈，重复过程1，直到栈空为止
void travle_preorder(node* root)
{
if(root==null)
return;
node*cur=root;
stacks;
while(cur!=null || !s.empty())
{
if(cur!=null)
{//一直找到最左边的节点
cout<<cur->data<<' ';
s.push(cur);
cur=cur->left;
}
else
{
//回溯
cur=#url#();
s.pop();
cur=cur->right;
}
}
}
//中序非递归遍历
//算法步骤：（1）根节点入栈，一直找到最左边的节点，然后回溯；（2）找到最左边的节点后，开始回溯，取栈顶数据输出，右节点（非空）入栈，重复直到栈空。
void travel_midorder(node* &root)
{
if(root==null)
return;
node*cur=root;
stacks;
while(cur!=null || !s.empty())
{
if(cur!=null)//找到最左边的节点。
{
s.push(cur);
cur=cur->left;
}
else
{//回溯
cur=#url#();
cout<<cur->data<<' ';
s.pop();
cur=cur->right;
}
}
}
//层次遍历树：
//利用队列先进先出的'概念，先跟节点入队，之后出队；出队节点的左右节点（非空）入队；重复直到队空
void travel_level(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
nd.push_back(cur);
while(!nd.empty())
{
cur=nd.front();
cout<<cur->data<<' ';
nd.pop_front();//出队
if(cur->left!=null)
nd.push_back(cur->left);//入队
if(cur->right!=null)
nd.push_back(cur->right);//入队
}
}
//如果要求层次遍历，每行按行输出，有两种常用解法
//1）使用两个队列，队列1存放当前层的节点，队列而存放下一层的节点，然后交替打印
void travel_level_towq(node* &root)
{
if(root==null)
return;
dequend1;
dequend2;
node*cur=root;
nd1.push_back(cur);
while(!nd1.empty() || !nd2.empty() )
{
while(!nd1.empty())
{
cur=nd1.front();
cout<<cur->data<<'';//输出当前队列中的节点
nd1.pop_front();
if(cur->left!=null)
nd2.push_back(cur->left);
if(cur->right!=null)
nd2.push_back(cur->right);
}
//此时nd1已经为null，nd2为其下一行应该要打印的节点
cout<<endl;//一层输出完毕，进行换行
while(!nd2.empty())
{
cur=nd2.front();
cout<<cur->data<<'';//输出当前队列中的节点
nd2.pop_front();
if(cur->left!=null)
nd1.push_back(cur->left);
if(cur->right!=null)
nd1.push_back(cur->right);
}
cout<<endl;//一层输出完毕，进行换行
}
}
//2）只使用一个队列，需要两个额外的变量，来记录当前层的节点个数和下一层的节点个数。
void travel_level_oneq(node* &root)
{
if(root==null)
return;
dequend;
node*cur=root;
nd.push_back(cur);
intcur_num=1;//当前行有多少个节点，初始化为1
intnext_num=0;//下一层有多少个节点，初始为0
while(!nd.empty())
{
cur=nd.front();
cout<<cur->data<<' ';
nd.pop_front();
cur_num--;//当前层输出一个节点，节点数就减少1
if(cur->left!=null)
{
nd.push_back(cur->left);
next_num++;
}//出栈节点的左子不为空的话，压入队列，下层的节点数加1
if(cur->right!=null)
{
nd.push_back(cur->right);
next_num++;
}//出栈节点的右子不为空的话，压入队列，下层的节点数加1
if(cur_num==0)
{
cout<<endl;//当前层节点全部遍历，输出换行符
cur_num=next_num;//把下一行当做当前行处理
next_num=0;//初始化下一行为0
}
}
}
【二叉树学结】相关文章：
对学结06-03
远程学结06-13
对标学结06-03
对excel的学结06-03
蹲点学结06-03
俄语学结06-03
法规学结06-03
法语学结06-03
翻译学结06-03