论坛 › 数据结构与算法 › 用递归中序遍历二叉树该如何实现

luckin 发表于 2014-6-26 20:46:04

用递归中序遍历二叉树该如何实现

// 中序遍历二叉树，非递归
void InOrderTraverse( BiThrTree T )
{
        BiThrTree p;
        p = T->lchild;

        while( p != T )
        {
                while( p->ltag == Link )
                {
                        p = p->lchild;
                }
                visit(p->data);

                while( p->rtag == Thread && p->rchild != T )
                {
                        p = p->rchild;
                        visit(p->data);
                }
               
                p = p->rchild;
        }
}

liu737093270 发表于 2014-6-26 22:24:09

void inorder (BiTree &T)
{
        if (T)
        {
                preorder(T->lchild);
                printf("-%c-", T->data);                preorder(T->rchild);
        }

        return;
}

luckin 发表于 2014-6-27 06:58:15

liu737093270 发表于 2014-6-26 22:24 static/image/common/back.gif
void inorder (BiTree &T)
{
        if (T)


preorder（）函数的实现？
话说你一个是inorder一个是preorder这是递归吗？

santaclaus 发表于 2014-6-27 07:14:18

先访问左子树，再访问结点，最后右子树。

luckin 发表于 2014-6-27 08:13:44

santaclaus 发表于 2014-6-27 07:14 static/image/common/back.gif
先访问左子树，再访问结点，最后右子树。
能给个代码吗思路是这样 代码写不来

Mikel 发表于 2014-6-28 06:35:30

void InOrderTraverse( BiThrTree T)
{
        BiThrTree p;
        p = T->lchild;

        while(p != T )
        {
                while( p->ltag == Link )
                {
                        p = p->lchild;
                }

                visit(p->data);

                while(p->rtag == Thread && p->rchild != T )
                {
                        p = p->rchild;
                        visit(p->data);
                }

                p = p->rchild;//收尾
        }
}

Mikel 发表于 2014-6-28 06:37:55

//中序遍历
void InThreading(BiThrTree T)
{
        if( T )
        {
                InThreading( T->lchild ); //递归左孩子线索化

                if( !T->lchild ) // 如果该节点没有做孩子，设置ltag为Therad,并把lchild指向前驱
                {
                        (*T).ltag = Thread;
                        T->lchild = pre;
                }

               
                if( !pre->rchild )
                {
                        (*T).rtag = Thread;
                        pre->rchild = T;
                }

                pre = T;

                InThreading( T->rchild );//递归右孩子线索化
        }
}

luckin 发表于 2014-6-28 08:35:41

Mikel 发表于 2014-6-28 06:37 static/image/common/back.gif
//中序遍历
void InThreading(BiThrTree T)
{


这不是视频上的吗// 中序遍历二叉树，非递归
void InOrderTraverse( BiThrTree T )
{
        BiThrTree p;
        p = T->lchild;

        while( p != T )
        {
                while( p->ltag == Link )
                {
                        p = p->lchild;
                }
                visit(p->data);

                while( p->rtag == Thread && p->rchild != T )
                {
                        p = p->rchild;
                        visit(p->data);
                }
               
                p = p->rchild;
        }
}用递归如何实现

Mikel 发表于 2014-6-28 12:18:08

luckin 发表于 2014-6-28 08:35 static/image/common/back.gif
这不是视频上的吗用递归如何实现

没仔细看，以为你要递归的呢。

luckin 发表于 2014-6-28 20:12:05

Mikel 发表于 2014-6-28 12:18 static/image/common/back.gif
没仔细看，以为你要递归的呢。

恩恩
还是谢谢了

风骚居士 发表于 2014-8-4 17:00:24

// 为了不让你误解我给出我自己版本的书阶段的定义
typedef struct Bitnode
{
   char data;      //树结点存储的值暂且设定为字符型
   struct Bitnode *lchild;
   struct Bitnode *rchild;
}Bitnode;



void qwe(Bitnode *T)   //这里qwe是函数名字你爱什么名就什么名，Bitnode是数结点结构体
{
   if(NULL != T)    //这里也可以if(T <span style="line-height: 1.5;">!= NULL</span><span style="line-height: 1.5;">)，是一样的作用，只是个小技巧，有时候自己把x == 2写成x=2很麻烦，但是把2 ==x写成2=x编译器会报错。</span>我给个遍历的模板给你

void travese(Bitnode *T)
{
      if(NULL!=T)
      {
             //1，如果这个位置写对结点的访问就是前序遍历
            
            travese(T->lchild);
         
            //2， 如果这个位置对结点访问      就是中序遍历

            travese(T->rchild);


             //3， 如果这个位置对结点访问      就是后序遍历
       }
}

风骚居士 发表于 2014-8-4 17:04:55

风骚居士 发表于 2014-8-4 17:00
我给个遍历的模板给你

void travese(Bitnode *T)


void qwe(Bitnode *T)
{
      if( NULL!=T )
      {         
            qwe(T->lchild);
            visit(T);
            qwe(T->rchild);
       }
}
void visit(Bitnode* T)
{
            printf("%c",T->data);
}

风骚居士 发表于 2014-8-4 17:05:58

第一份回复出了点问题， 我重新打了代码上去， 你凑合着看

cable5881 发表于 2014-8-4 17:48:33

好牛逼的样子{:1_1:}{:1_1:}{:1_1:}

黄志伟 发表于 2014-10-13 12:10:00

谁能告诉我小甲鱼的数据第43讲为什么不能下载

查看完整版本: 用递归中序遍历二叉树该如何实现