排序二叉树及其遍历「建议收藏」

排序二叉树及其遍历「建议收藏」  所谓建立排序二叉树就是,就是将各结点数据元素顺序插到一棵二叉树中,在插入的过程中,始终保持二叉树中每个结点的值都大于其左子树上每个结点的值,而小于或等于其右子树上每个结点的值,每个结点信息包括结点数据(结点值)、左子树指针、右子树指针。程序执行的过程中,bt指针始终指向根结点,p指针指向当前已找到的结点,q指针不断向下寻找新的结点。  为实现二叉树的非递归算法,需要设置一个栈来保存指向结点

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

   所谓建立排序二叉树就是,就是将各结点数据元素顺序插到一棵二叉树中,在插入的过程中,始终保持二叉树中每个结点的值都大于其左子树上每个结点的值,而小于或等于其右子树上每个结点的值,每个结点信息包括结点数据(结点值)、左子树指针、右子树指针。

程序执行的过程中,bt指针始终指向根结点,p指针指向当前已找到的结点,q指针不断向下寻找新的结点。

   为实现二叉树的非递归算法,需要设置一个栈来保存指向结点的指针,以便在遍历某结点的左子树后,由这个指针能找到该结点的右子树。栈中的地址是随着结点的遍历次序而动态变化的。

参考程序:

#include <stdio.h>
#define  null 0
#define  max 100
int counter=0;
int stack[max],top=0;

 

typedef struct btreenode
{int data;
 struct btreenode *lchild;
 struct btreenode *rchild;
 }bnode;

 

bnode *creat(int x,bnode *lbt,bnode *rbt)               //建立一个只有根结点的二叉树
{bnode *p;
 p=(bnode*)malloc (sizeof(bnode));
 p->data=x;
 p->lchild=lbt;
 p->rchild=rbt;
 return(p);
 }

 

bnode *inslchild(bnode *p,int x)                                //x作为左孩子插入到二叉树中
{bnode *q;
 if(p==null)
    printf(“Illegal insert.”);
 else
    {q=(bnode*)malloc(sizeof(bnode));
     q->data=x;
     q->lchild=null;
     q->rchild=null;
     if(p->lchild!=null)                                 //
p有左孩子,则将原来的左孩子作为结     x 的右孩子
        q->rchild=p->lchild;             
     p->lchild=q;                                         //x
做为p的左孩子
     }
 }

 

bnode *insrchild(bnode *p,int x)
{bnode *q;
 if(p==null)
    printf(“Illegal insert.”);
 else
    {q=(bnode*)malloc(sizeof(bnode));
     q->data=x;
     q->lchild=null;
     q->rchild=null;
     if(p->rchild!=null)
        q->lchild=p->rchild;             
     p->rchild=q;
     }
 }

 

void prorder(bnode *p)                                //输出二叉树的结构
{if(p==null)
    return;
 printf(“%d/t%u/t%d/t%u/t%u/n”,++counter,p,p->data,p->lchild,p->rchild);
 if(p->lchild!=null)
    prorder(p->lchild);
 if(p->rchild!=null)
    prorder(p->rchild);
}

void print(bnode *p)                             //嵌套括号表示二叉树,输出左子树前打印左括号,
{                                                                //
输出右子树后打印右括号。
  if(p!=null)
  {printf(“%d”,p->data);
   if(p->lchild!=null||p->rchild!=null)
   {printf(“(“);
  print(p->lchild);
  if(p->rchild!=null)
   printf(“,”);
  print(p->rchild);
  printf(“)”);
 }
}
}

 

void preorder(bnode *p)                       //前序遍历
{while(p!=null||top!=0)
{if(p!=null)
{printf(“%d”,p->data);                          //
输出结点值
 push(p);                                                 //
将指针值压入栈中
 p=p->lchild;                                           //
遍历左子树
}
else
{p=(bnode*)pop();
 p=p->rchild;                                            //
遍历右子树
}
}
}

 

void inorder(bnode *p)                         //中序遍历
{while(p!=null||top!=0)             
{while(p!=null)
{push(p);                                                //
将根结点压入栈中
 p=p->lchild;                                           //
遍历左子树
}
p=(bnode*)pop();
printf(“%d”,p->data);                          //
输出当前结点值
p=p->rchild;                                          //
遍历右子树
}
}
 
void postorder(bnode *p)                //
后序遍历
{unsigned sign;                                 //
设置一个标志,记录结点从栈中弹出的次数
 while(p!=null||top!=0)
 {

  if(p!=null)
 {push(p);                                          //
1次遇到结点p时压入其指针值
  push(1);                                            //
置标志为1
  p=p->lchild;                                     //
遍历结点p的左子树

 }
 else
 while(top!=0)
 {sign=pop();
 p=(bnode*)pop();
 if(sign==1)                                        //sign=1
表示仅走过p的左子树
 {push(p);                                         //
2次压入结点p的指针值
  push(2);                                          //
设置标志为2
  p=p->rchild;                                   //
遍历p的右子树

  break;
 }
 else
  if(sign==2)                                      //sign=2
表示p的左右子树都已走完
  {printf(“%d”,p->data);                //
输出结点p的值
   p=null;
  }
 } //while(top!=0)
 } //while(p!=null||top!=0)
}

 

void translevel(bnode *p)               //层次遍历
{struct node
{bnode *vec[max];
 int front,rear;
}q;
 q.front=q.rear=0;
 if(p!=null)
   printf(“%d”,p->data);
 q.vec[q.rear]=p;                              //
结点指针进入队列
 q.rear=q.rear+1;
 while(q.front<q.rear)                     //
队列不为空
 {p=q.vec[q.front];                        //
队头出队列
  q.front=q.front+1;
  if(p->lchild!=null)                         //
输出左孩子,并入队列
  {printf(“%d”,p->lchild->data);
  q.vec[q.rear]=p->lchild;
  q.rear=q.rear+1;
  }
  if(p->rchild!=null)
  {printf(“%d”,p->rchild->data);
   q.vec[q.rear]=p->rchild;
   q.rear=q.rear+1;
  }
 }
}

 

push(s)
{top++;
 stack[top]=s;
}

 

pop()
{top–;
 return(stack[top+1]);
}

 

main()
{bnode *bt,*p,*q;
 int x, y;
 printf(“Input root:”);
 scanf(“%d”,&x);
 p=creat(x,null,null);
 bt=p;
 printf(“Input other node:”);
 scanf(“%d”,&x);
 while(x!=-1)
   {p=bt;
  q=p;
    while(x!=p->data&&q!=null)
       {p=q;
        if(x<p->data)
           q=p->lchild;
        else
           q=p->rchild;
        }
    if(x==p->data)
      printf(“The node %d  existed already!/n”,x);
    else
       if(x<p->data)
         inslchild(p,x);
       else
   insrchild(p,x);
    scanf(“%d”,&x);
    }
p=bt;
printf(“structure of the binary tree:/n”);
printf(“number/taddress/tdata/tlchild/trchild/n”);
prorder(p);
printf(“/n”);
print(p);
printf(“/t
输出左子树前打印左括号,输出右子树后打印右括号。
/n”);
printf(“———-1
前序遍历二叉树
———- /n”);
printf(“———-2
中序遍历二叉树
———- /n”);
printf(“———-3
后序遍历二叉树
———- /n”);
printf(“———-4
层次遍历二叉树
———- /n”);
loop:printf(“
请选择遍历方式:
“);
scanf(“%d”,&y);
switch(y)
{

    case 1:preorder(p);
        printf(“/n”);
           goto loop;
 case 2:inorder(p);
     printf(“/n”);
        goto loop;
 case 3:postorder(p);
     printf(“/n”);
        goto loop;
    case 4:translevel(p);
     printf(“/n”);
        goto loop;
}
}       

       容易看出,中序遍历二叉树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列,构造树的过程即对无序序列进行排序的过程。不仅如此,从上面的插入过程还可以看到,每次插入的新结点都是二叉排序树的新的叶子结点,在进行插入操作时,不必移动其他结点,仅需改动某个结点的指针,由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。这有类似折半查找的特性,又采用链表作为存储结构,因此是动态查找的一种适宜表示。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/160057.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号