二叉树顺序存储之 前序,中序 ,后序遍历
二叉树遍历的概念:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。 ? 二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历,这三种遍历可以用递归实现前序遍历:根节点->左子树->右子树(根->左->右) 中序遍历:左子树->根节点->右子树(左->根->右) 后序遍历:左子树->右子树->根节点(左->右->根) 前序遍历1)依据上文提到的遍历思路:根结点 ---> 左子树 ---> 右子树,非常easy写出递归版本号: /* 以递归方式 前序遍历二叉树 */
void PreOrderTraverse(BiTree t,int level)
{
if (t)
{
printf("data = %c level = %dn ",t->data,level);
PreOrderTraverse(t->lchild,level + 1);
PreOrderTraverse(t->rchild,level + 1);
}
2)如今讨论非递归的版本号: 依据前序遍历的顺序,优先訪问根结点。然后在訪问左子树和右子树。所以。对于随意结点node。第一部分即直接訪问之,之后在推断左子树是否为空,不为空时即反复上面的步骤,直到其为空。若为空。则须要訪问右子树。注意。在訪问过左孩子之后。须要反过来訪问其右孩子。所以,须要栈这样的数据结构的支持。对于随意一个结点node,详细过程例如以下: a)訪问之,并把结点node入栈。当前结点置为左孩子; b)推断结点node是否为空,若为空。则取出栈顶结点并出栈,将右孩子置为当前结点;否则反复a)步直到当前结点为空或者栈为空(能够发现栈中的结点就是为了訪问右孩子才存储的) 代码例如以下: public void preOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
System.out.print(pNode.val+" ");
stack.push(pNode);
pNode = pNode.left;
} else { //pNode == null && !stack.isEmpty()
TreeNode node = stack.top();
? ? ? ? ? ? ?中序遍历1)依据上文提到的遍历思路:左子树?--->?根结点?---> 右子树,非常easy写出递归版本号: 以递归方式 中序遍历二叉树 if (t == NULL)
{
PreOrderTraverse(t->lchild,level + 1);
printf("data = %c level = %dn ",level);
PreOrderTraverse(t->rchild,level + 1);
}
2)非递归实现,有了上面前序的解释,中序也就比較简单了。同样的道理。仅仅只是訪问的顺序移到出栈时。代码例如以下: inOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = ) {
stack.push(pNode);
pNode = stack.top();
? 后序遍历1)依据上文提到的遍历思路:左子树 ---> 右子树?---> 根结点。非常easy写出递归版本号: 以递归方式 后序遍历二叉树 ) { PreOrderTraverse(t->lchild,level + 1); PreOrderTraverse(t->rchild,1)">); printf("data = %c level = %dn ",t->data,level); 2)后序遍历的非递归实现是三种遍历方式中最难的一种。由于在后序遍历中,要保证左孩子和右孩子都已被訪问而且左孩子在右孩子前訪问才干訪问根结点,这就为流程的控制带来了难题。以下介绍两种思路。 ????? 第一种思路:对于任一结点P,将其入栈,然后沿其左子树一直往下搜索。直到搜索到没有左孩子的结点,此时该结点出在栈顶,可是此时不能将其出栈并訪问,因此其右孩子还未被訪问。 所以接下来依照同样的规则对其右子树进行同样的处理,当訪问完其右孩子时。该结点又出在栈顶,此时能够将其出栈并訪问。这样就保证了正确的訪问顺序。能够看出,在这个过程中,每一个结点都两次出在栈顶,仅仅有在第二次出如今栈顶时,才干訪问它。因此须要多设置一个变量标识该结点是否是第一次出如今栈顶。 void postOrder2(BinTree *root) 非递归后序遍历
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) 沿左子树一直往下搜索。直至出现没有左子树的结点
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) 表示是第一次出如今栈顶
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else 第二次出如今栈顶
{
cout<<temp->btnode->data<<" ;
p=NULL;
}
}
}
}
另外一种思路:要保证根结点在左孩子和右孩子訪问之后才干訪问,因此对于任一结点P。先将其入栈。假设P不存在左孩子和右孩子。则能够直接訪问它;或者P存在左孩子或者右孩子。可是其左孩子和右孩子都已被訪问过了。则相同能够直接訪问该结点。若非上述两种情况。则将P的右孩子和左孩子依次入栈。这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被訪问。左孩子和右孩子都在根结点前面被訪问。 void postOrder3(BinTree *root) {
stack<BinTree*> s;
BinTree *cur; 当前结点
BinTree *pre=NULL; 前一次訪问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<"; 假设当前结点没有孩子结点或者孩子节点都已被訪问过
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
? 三种递归遍历方式对应的代码几乎相同,只是一条语句的位置发生了变化 printf(只看文字和代码来理解遍历的过程是比较困难的,建议读者亲自去遍历,为了理清遍历的过程下面上题
|