数据结构——树的遍历

雨点打透心脏的1/2处 2022-07-11 13:52 252阅读 0赞

二叉树概念：一棵树拥有一个根结点，且所有结点的子结点都不超过2。

有序树概念：当子结点有特定顺序（左右之分）的树。

前序遍历（Preorder） ：按照 **根结点**，左子树，右子树的顺序输出结点编号。

中序遍历（Inorder） ：按照左子树， **根结点**，右子树的顺序输出结点编号。

后序遍历（Postorder）：按照左子树，右子树， **根结点**的顺序输出结点编号。

**前序遍历**

void preParse(int u)
    {//前序遍历 
    	if(u==NIL)return;
    	printf(" %d",u);
    	preParse(T[u].l);
    	preParse(T[u].r);
    }

**中序遍历**

void inParse(int u)
    {//中序遍历  
    	if(u==NIL)return;
    	inParse(T[u].l);
    	printf(" %d",u);
    	inParse(T[u].r);
    }

**后序遍历**

void postParse(int u)
    {//后序遍历  
    	if(u==NIL)return;
    	postParse(T[u].l);
    	postParse(T[u].r);
    	printf(" %d",u);
    }

**递归求结点的深度：** **左子右兄弟表示法**

（如果当前结点存在右侧兄弟结点，则不改变深度p直接进行递归调用，如果存在最左侧子结点，则先将深度加1再进行递归调用）

setDepth(u,p)
    {
    	D[u]=p;
    	if(T[u].r!=NIL)
    	setDepth(T[u].r,p);
    	if(T[u].left!=NIL)
    	setDepth(T[u].l,p+1);	
    }

**已知深度求结点：**深度为k的二叉树，最多有2^k-1个结点。

**已知结点求深度：**具有n个结点的完全二叉树的深度为\[log2n\]+1.（log2n是以2为底n的对数）

**TOJ 1222/1223/1224 先/中/后序遍历二叉树**

**描述**

给定一颗二叉树，要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

**输入**

输入数据分为多组，第一行是测试数据的组数n，下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数，数据为0代表当前结点为空，数据为-1代表二叉树数据输入结束，-1不作处理。二叉树的构造按照层次顺序（即第1层1个整数，第2层2个，第3层4个，第4层有8个......，如果某个结点不存在以0代替），比如输入：

1 2 0 3 4 -1得到的二叉树如下：

![1222.gif][]

**输出**

输出每棵二叉树的深度以及先序遍历二叉树得到的序列。

**样例输入**

2 1 -1 1 2 0 3 4 -1

**样例输出**

1 1 3 1 2 3 4

#include<stdio.h>
    #include<math.h>
    int a[100],i;
    void first(int n)
    {//前序
    	printf(" %d",a[n]);
    	if(a[2*n+1]!=0)first(2*n+1);
     	if(a[2*n+2]!=0)first(2*n+2);
    }

void first(int n)
    {//中序
     	if(a[2*n+1]!=0)first(2*n+1);
     	printf(" %d",a[n]);
     	if(a[2*n+2]!=0)first(2*n+2);
    }

void first(int n)
    {//后序
     	if(a[2*n+1]!=0)first(2*n+1);
     	if(a[2*n+2]!=0)first(2*n+2);
    	printf(" %d",a[n]);
    }

int main()
    {
    	int t,b,k;
    	scanf("%d",&t);
    	while(t--)
    	{
    		i=0;
    		while(1)
    		{scanf("%d",&b);
    		if(b==-1)break;
    		a[i++]=b;}
    		k=int(log(i)/log(2)+1.1);
    		//强制转换，如果+1的话可能会出错。 
    		printf("%d",k);
    		first(0);
    		puts("");
    	}
    }

然后下面是童冰学姐用指针（队列？）做的..我还没看懂..等我日后厉害了再回头来看..

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    struct towtree
    {
        int n;
        towtree *left,*right;
    }*root;
    int k,m;
    towtree *push()
    {
    	towtree *Q[100];
       	int  front=1,rear=0;  /*队列指针如此设定，便于操作*/
       	int a;
       	towtree *root=NULL,*s;
       	while(scanf("%d",&a),a!=-1)   /* '#'为输入结束标志*/
       	{
       		m++;  
       		if(!a) s=NULL;        /* 输入空格为虚结点*/
     		else
       		{  
       			s=(towtree *)malloc(sizeof(towtree));/*建立新结点*/
         		s->n=a; s->left=NULL; s->right=NULL;
       		}
       		Q[++rear]=s;   /*虚结点指针NULL或新结点地址入队*/    
       		if(rear==1) root=s;    /*第一个结点为根结点*/
       		else
       		{  
       			if(s&&Q[front])  /* 孩子和双亲结点都不是虚结点*/
         		if(rear%2==0) 
            	Q[front]->left=s;/* 新结点为左孩子*/
            	else 
    			Q[front]->right=s;/*新结点为右孩子*/
            	if(rear%2==1) 
    			front++;  /*左右孩子都已处理结点出队*/
      		}
       }
       return root;
    }
    void first(towtree *p)
    {//前序遍历 
        if(p!=NULL)
        {    
            if(p->n!=0)
            printf(" %d",p->n);
            first(p->left);
            first(p->right);
        }
    }
    int main()
    {
        int t,p;
        scanf("%d",&t);
        while(t--)
        {
            m=k=0;
            root=push();
            p=fabs(log(m)/log(2)+1.1);
            printf("%d",p);
            first(root);
            puts("");
        }
    }

[1222.gif]: http://210.33.181.162/acmhome/judge/images/1222.gif