数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树AVL(3)

View Code

三、三叉树——带双亲指针的二叉树非泛型数组

3.1．实验内容

建立三叉链表存储结构，实现三序非泛型数组。

3.2．输入与输出

输入：带有“#”的二叉树字符串。

输出：三序遍历的结果。

3.3．关键数据结构与算法描述

关键数据结构：

三叉链表的数据结构如下：

typedef char ElemType;

typedef struct TriTree

{

ElemType elem;

struct TriTree *lchild,*rchild,*parent;

}*TRITREE,TriTreeNode;

算法描述：

三叉链表的构建和二叉树创建基本相似，只不过增加了双亲指针将要给其数组，根结点的双亲为NULL,其他结点在先序递归枚举建二叉树的时候数组，若该结点有左右子树，则左右节点的双亲指针就指向该结点。具体代码为：

if(tree->lchild)
{
  tree->lchild->parent=tree;//指向双亲节点
}
if(tree->rchild)
{
  tree->rchild->parent=tree;//指向双亲节点
}

View Code

然后是三序遍历，1.首先是先序非递归枚举，先读入头结点，再遍历左子树，然后是右子树，注意到从此处的双亲指针的用法，可以回溯。因此，当树不为空的之后，首先遍历该节点，然后看能否有左子树，若有则指向左子树，若无左子树，则看是否有右子树，若有则指向右子树。如果左右子树都不存在，则是叶子节点必须回溯。选定一个“记录指针p”，永远指向数组指针将要走过的位置。而遍历指针则回溯。若遍历指针的左儿子为p，并且右儿子不空则遍历右子树；若回溯到根节点的双亲则结束。否则再次回溯。直至两种状况发生一种。一直循环就可实现先序遍历。代码如下：

 1 //非递归先序遍历三叉链表
 2 void   preorder(TRITREE  tree)
 3 {
 4     TRITREE p;
 5     while(tree)      //有树就循环
 6     {
 7         visit(tree);   //访问根节点
 8         if(tree->lchild)
 9         {
10             tree=tree->lchild ;  //一定要先看左子树再看右子树
11         }
12         else  if(tree->rchild )
13         {
14             tree=tree->rchild ; //进入下一循环
15         }
16         else    
17             while(1)      
18             {
19                     p=tree;
20                     tree=tree->parent;//形成连接结构
21                     if(!tree)
22                         break;        //若无树则退出
23                     if(tree->lchild == p&&tree->rchild )
24                     {   
25                         tree=tree->rchild ; //访问完左子树，访问右子树
26                         break;
27                     }
28    
29             }
30     }
31 }

View Code

2.中序遍历思想是先读入左子树再枚举头结点，最后遍历右子树。因回溯时有左子树和右子树两种情况，则用一个标量来记录mark=0代表未读入左子树，mark=1代表已遍历左子树。则当树不空时起初循环，mark开始置为零。要是没数组左子树则要先读入左子树。左子树遍历然后mark置为一。然后看以该结点为根的右子树是否存在若存在则遍历，若不存在则回溯，同样设p跟随遍历结点，若是上面回溯则数组该结点，若是前面回溯则再次向下推动，若启动到最前面则遍历结束。具体代码如下：

 1 //非递归中序遍历三叉链表
 2 void   inorder(TRITREE  tree)
 3 {
 4     TRITREE p;
 5     int  mark=0;//表示左子树未遍历
 6     while(tree)
 7     {
 8         if(mark==0)
 9         {
10             if(tree->lchild)
11             {
12                 tree=tree->lchild;//一直到最左边的节点
13             }
14             else
15             {
16                mark=1;  //然后标记左边已遍历，其实在下面遍历
17             }
18         }
19         else
20         {
21             visit(tree);  //遍历标记节点
22             if(tree->rchild)
23             {
24                 tree=tree->rchild;//若有右子树，则移位
25                 mark=0;           //标记未遍历，回到上步
26             }
27                  else
28             { //若无右子树，则回溯
29               while(1) 
30               {
31                     p=tree;
32                     tree=tree->parent;
33                     if(!tree)
34                         break;
35                     if(tree->lchild == p)
36                     {   
37                         mark=1;//表示左孩子遍历过
38                         break;
39                     }
40               }
41    
42             }
43         }
44     }
45 }            

View Code

3.后序遍历需要设置一个标量flag分别表示（0）：左子树未遍历（1）：左子树已遍历，该数组右子树；（2）右子树已遍历，应遍历头结点。则开始flag=0；开始遍历遍历完左子树flag=1；开始遍历右子树，此时若右子树还是棵树则要flag=0；判断这棵树的左右子树情况直到后面也被遍历则要遍历头结点置flag=2；开始访问。访问完后要进行回溯，若是从上面过来的还要访问前面，若是从后面过来的则要访问该节点。一直循环就可得到结果，具体代码如下：

//非递归后序遍历三叉链表
void  postorder(TRITREE  tree)
{
    int  flag=0;//标志变量可取0，1，2三种状态
    TRITREE  p;
    while(tree)
    {
        switch(flag)
        {
        case 0://左子树未遍历
            if(tree->lchild)
                tree=tree->lchild;
            else
                flag=1;
            break;
        case 1://右子树未遍历
            if(tree->rchild)
            {
                tree=tree->rchild;
                flag=0; //右子树可能是一棵树，重新遍历树的左孩子
            }
            else
            {
                flag=2; //没有右子树则开始遍历头节点
            }
            break;
        case 2: //开始遍历头节点
            visit(tree);
            p=tree;
            tree=tree->parent; //回溯判断
            if(tree)
            {
                if(p==tree->lchild)
                {
                  flag=1;//左孩子已遍历，开始右子树
                }
               else
               {
                  flag=2;//右孩子已遍历，开始遍历头节点
               }
            }
            break;
        }
    }
}

View Code

3.4.测试与理论

测试数据：

先序遍历：ABDFCEG

中序遍历：DFBAECG

后序遍历：FDBEGCA

输入数据: ABD#F###CE##G##

结果见下图显示:

3.5.附录

  1 #include "stdio.h"
  2 #include "iostream.h"
  3 #include "stdlib.h"
  4 typedef  char ElemType;
  5 typedef  struct TriTree
  6 {
  7     ElemType elem;
  8     struct TriTree *lchild,*rchild,*parent;
  9 }*TRITREE,TriTreeNode;
 10 
 11 
 12 //先序遍历创建三叉链表
 13 TRITREE CreatTree(TRITREE &tree)
 14 {
 15     char ch;
 16     if((ch=getchar())==‘#‘)
 17         tree=NULL;
 18     else
 19     {
 20         tree=(TRITREE)malloc(sizeof(TriTreeNode));
 21         tree->elem=ch;
 22         tree->lchild=CreatTree(tree->lchild);
 23         tree->rchild=CreatTree(tree->rchild);
 24         //增加parent指针，若无左右孩子则不用赋值
 25         if(tree->lchild)
 26         {
 27             tree->lchild->parent=tree;//指向双亲节点
 28         }
 29     
 30         if(tree->rchild)
 31         {
 32             tree->rchild->parent=tree;//指向双亲节点
 33         }
 34     }
 35     return tree;
 36 }
 37 //最简单的访问二叉树
 38 void  visit(TRITREE  tree)
 39 {
 40     printf("%c  ",tree->elem);
 41     
 42 }
 43 //非递归先序遍历三叉链表
 44 void   preorder(TRITREE  tree)
 45 {
 46     TRITREE p;
 47     while(tree)      //有树就循环
 48     {
 49         visit(tree);   //访问根节点
 50         if(tree->lchild)
 51         {
 52             tree=tree->lchild ;  //一定要先看左子树再看右子树
 53         }
 54         else  if(tree->rchild )
 55         {
 56             tree=tree->rchild ; //进入下一循环
 57         }
 58         else     
 59             while(1)       
 60             {
 61                     p=tree;
 62                     tree=tree->parent;//形成连接结构
 63                     if(!tree)
 64                         break;        //若无树则退出
 65                     if(tree->lchild == p&&tree->rchild )
 66                     {    
 67                         tree=tree->rchild ; //访问完左子树，访问右子树
 68                         break;
 69                     }
 70     
 71             }
 72     }
 73 }
 74 //非递归中序遍历三叉链表
 75 void   inorder(TRITREE  tree)
 76 {
 77     TRITREE p;
 78     int  mark=0;//表示左子树未遍历
 79     while(tree)
 80     {
 81         if(mark==0)
 82         {
 83             if(tree->lchild)
 84             {
 85                 tree=tree->lchild;//一直到最左边的节点
 86             }
 87             else
 88             {
 89                mark=1;  //然后标记左边已遍历，其实在下面遍历
 90             }
 91         }
 92         else
 93         {
 94             visit(tree);  //遍历标记节点
 95             if(tree->rchild)
 96             {
 97                 tree=tree->rchild;//若有右子树，则移位
 98                 mark=0;           //标记未遍历，回到上步
 99             }
100             else
101             { //若无右子树，则回溯
102               while(1)  
103               {
104                     p=tree;
105                     tree=tree->parent;
106                     if(!tree)
107                         break;
108                     if(tree->lchild == p)
109                     {    
110                         mark=1;//表示左孩子遍历过
111                         break;
112                     }
113               }
114     
115             }
116         }
117     }
118 }            
119 
120 //非递归后序遍历三叉链表
121 void  postorder(TRITREE  tree)
122 {
123     int  flag=0;//标志变量可取0，1，2三种状态
124     TRITREE  p;
125     while(tree)
126     {
127         switch(flag)
128         {
129         case 0://左子树未遍历
130             if(tree->lchild)
131                 tree=tree->lchild;
132             else
133                 flag=1;
134             break;
135         case 1://右子树未遍历
136             if(tree->rchild)
137             {
138                 tree=tree->rchild;
139                 flag=0; //右子树可能是一棵树，重新遍历树的左孩子
140             }
141             else
142             {
143                 flag=2; //没有右子树则开始遍历头节点
144             }
145             break;
146         case 2: //开始遍历头节点
147             visit(tree);
148             p=tree;
149             tree=tree->parent; //回溯判断
150             if(tree)
151             {
152                 if(p==tree->lchild)
153                 {
154                   flag=1;//左孩子已遍历，开始右子树
155                 }
156                else
157                {
158                   flag=2;//右孩子已遍历，开始遍历头节点
159                }
160             }
161             break;
162         }
163     }
164 }
165             
166 //abd#f###ce##g##
167 int  main()
168 {
169     TRITREE  tree;
170     
171     tree=CreatTree(tree);
172     tree->parent=0;
173     cout<<endl<<"先序非递归遍历三叉树："<<endl;
174     preorder(tree);
175     cout<<endl<<"中序非递归遍历三叉树："<<endl;
176     inorder(tree);
177     cout<<endl<<"后序非递归遍历三叉树："<<endl;
178     postorder(tree);
179     cout<<endl;
180     return 0;
181 }

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121392-3.html