Data );PreorderTraversal( BT->Left );PreorderTraversal( BT->Right ..._编写一个能遍历二叉树的程序c语言">
当前位置:   article > 正文

二叉树遍历算法c语言,二叉树的遍历(C语言实现)

编写一个能遍历二叉树的程序c语言

1.前序遍历

若树为空,则空操作返回。否则,先访问根节点,然后前序遍历左子树,再前序遍历右子树。

c57266b68e8811fb926e4fe87d122a3c.png

先序遍历的递归实现代码:

void PreorderTraversal( BinTree BT )

{

if( BT ) {

printf("%d ", BT->Data );

PreorderTraversal( BT->Left );

PreorderTraversal( BT->Right );

}

}

前序遍历的非递归实现,用压栈的方式实现:

BinTree PreorderTraversal( BinTree BT )

{

stacks;

BinTree T = BT;

while(T||!s.empty())

{

while(T)

{

Stack S=CreatStack(MaxSize);

s.push(T);

T = T->left;

}

if(!s.empty())

{

T = pop(s);

T = T->right;

}

}

}

2.中序遍历

若树为空,则空操作返回。否则,从根节点开始(注意并不是先访问根节点),中序遍历根节点的左子树,然后是访问根节点,最后中序遍历根节点的右子树。(M)型,(左 中 右)

中序遍历的递归实现代码:

void InorderTraversal( BinTree BT )

{

if( BT ) {

InorderTraversal( BT->Left );

/* 此处假设对BT结点的访问就是打印数据 */

printf("%d ", BT->Data); /* 假设数据为整型 */

InorderTraversal( BT->Right );

}

}

中序遍历的非递归实现:

BinTree InorderTraversal( BinTree BT )

{

Stack S=CreatStack(MaxSize);

BinTree T = BT;

while(T||!s.empty())

{

while(T)

{

s.push(T);

T = T->left;

}

if(!s.empty())

{

T = pop(s);

printf("%5d",T->Data)

T = T->right;

}

}

}

3.后序遍历

若树为空,则空操作返回。否则,从左到右先叶子后节点的方式遍历访问左右子树,最后访问根节点。(左右中)逆时针型 (左 右 中)

后序遍历的递归实现代码:

void PostorderTraversal( BinTree BT )

{

if( BT ) {

PostorderTraversal( BT->Left );

PostorderTraversal( BT->Right );

printf("%d ", BT->Data);

}

}

后序遍历的非递归实现代码:

void postOrder3(BinTree *root) //非递归后序遍历

{

stacks;

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

s.push(cur->rchild);

if(cur->lchild!=NULL)

s.push(cur->lchild);

}

}

}

4.层序遍历

void LevelorderTraversal ( BinTree BT )

{

Queue Q;

BinTree T;

if ( !BT ) return; /* 若是空树则直接返回 */

Q = CreatQueue(); /* 创建空队列Q */

AddQ( Q, BT );

while ( !IsEmpty(Q) ) {

T = DeleteQ( Q );

printf("%d ", T->Data); /* 访问取出队列的结点 */

if ( T->Left ) AddQ( Q, T->Left );

if ( T->Right ) AddQ( Q, T->Right );

}

}

8

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/716040
推荐阅读
相关标签
  

闽ICP备14008679号