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

大家好，又见面了，我是你们的朋友全栈君。

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

程序执行的过程中，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; } }

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

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/160057.html原文链接：https://javaforall.cn