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

luckin

1. // 中序遍历二叉树，非递归
   
2. void InOrderTraverse( BiThrTree T )
   
3. {
   
4.         BiThrTree p;
   
5.         p = T->lchild;
   
6. 
   
7.         while( p != T )
   
8.         {
   
9.                 while( p->ltag == Link )
   
10.                 {
    
11.                         p = p->lchild;
    
12.                 }
    
13.                 visit(p->data);
    
14. 
    
15.                 while( p->rtag == Thread && p->rchild != T )
    
16.                 {
    
17.                         p = p->rchild;
    
18.                         visit(p->data);
    
19.                 }
    
20.                
    
21.                 p = p->rchild;
    
22.         }
    
23. }

复制代码

liu737093270

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

        return;
}

luckin

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

                               
登录/注册后可看大图

void inorder (BiTree &T)
{
        if (T)

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

santaclaus

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

luckin

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

                               
登录/注册后可看大图

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

能给个代码吗思路是这样 代码写不来

Mikel

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

//中序遍历
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

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

                               
登录/注册后可看大图

//中序遍历
void InThreading(BiThrTree T)
{

这不是视频上的吗

1. // 中序遍历二叉树，非递归
   
2. void InOrderTraverse( BiThrTree T )
   
3. {
   
4.         BiThrTree p;
   
5.         p = T->lchild;
   
6. 
   
7.         while( p != T )
   
8.         {
   
9.                 while( p->ltag == Link )
   
10.                 {
    
11.                         p = p->lchild;
    
12.                 }
    
13.                 visit(p->data);
    
14. 
    
15.                 while( p->rtag == Thread && p->rchild != T )
    
16.                 {
    
17.                         p = p->rchild;
    
18.                         visit(p->data);
    
19.                 }
    
20.                
    
21.                 p = p->rchild;
    
22.         }
    
23. }

复制代码

用递归如何实现

Mikel

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

                               
登录/注册后可看大图

这不是视频上的吗用递归如何实现

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

luckin

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

                               
登录/注册后可看大图

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

恩恩
还是谢谢了

风骚居士

1. // 为了不让你误解我给出我自己版本的书阶段的定义
   
2. typedef struct Bitnode
   
3. {
   
4.      char data;      //树结点存储的值暂且设定为字符型
   
5.      struct Bitnode *lchild;
   
6.      struct Bitnode *rchild;
   
7. }Bitnode;
   
8. 
   
9. 
   
10. 
    
11. void qwe(Bitnode *T)   //这里qwe是函数名字你爱什么名就什么名，Bitnode是数结点结构体
    
12. {
    
13.      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: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);
}

风骚居士

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

cable5881

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

黄志伟

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