二叉排序树-非递归形式 C语言

布满荆棘的人生 2022-12-17 07:23 158阅读 0赞

![在这里插入图片描述][20201022190842300.png_pic_center]  
完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct BiTNode
    { 
    	int data;//二叉树数据域 
    	struct BiTNode *lchild,*rchild;//二叉树指针域 
    }BiTNode,*BiTree;
    
    void InitTree(BiTree &T)//初始化二叉树 
    { 
    	T = (BiTNode*)malloc(sizeof(BiTNode));//创建一个头结点 
    	T->data = NULL;
    	T->lchild = T->rchild = NULL;//头结点指针域和数据域都NULL 
    }
    
    void CreateTree(BiTree &T)//创建排序二叉树 
    { 
    	int a;
    	printf("请输入数： ") ; 
    	scanf("%d",&a);//输入数据 
    	T->data = a;//类似于链表结点的赋值 
    	BiTree p = T;
    	if(getchar()=='\n')
    		return ;
    	while(1)
    	{ 
    		scanf("%d",&a);//输入要二叉树数据 
    		BiTree s;
    		s = (BiTNode *)malloc(sizeof(BiTNode));//创建一个结点 
    		s->lchild = s->rchild = NULL;//对这个结点进行初始化 
    		s->data = a;
    		while(1)
    		{ 
    			if(s->data > p->data)//判断s中的数据是否大于p中的数据，大于在右，小于在左 
    				if(p->rchild != NULL)//如果p的右孩子不空，p往右孩子转移 
    					p = p->rchild;
    				else//否则p的右孩子接上s 
    				{ 
    					p->rchild = s;
    					break;//死循环终止条件 
    				}	
    			else//大于在右，小于在左
    				if(p->lchild != NULL)//如果p的左孩子不空，p往左孩子转移 
    					p = p->lchild;
    				else
    				{ 
    					p->lchild = s;//否则p的左孩子接上s 
    					break;//死循环终止条件
    				}
    		}
    		p = T;//使p重新返回头结点 
    		if(getchar()=='\n')//死循环结束条件 
    			break;
    	}
    }
    
    void InOrderTraverse(BiTree T)//遍历二叉树，中序遍历 
    { 
    	if(T)
    	{ 
    		InOrderTraverse(T->lchild);
    		printf("%d ",T->data);
    		InOrderTraverse(T->rchild);
    	}
    }
    
    int main()
    { 
    	BiTree T;
    	InitTree(T);//创建并初始化二叉树 
    	CreateTree(T);//创建排序二叉树 
    	printf("排序后的结果为： "); 
    	InOrderTraverse(T);//遍历并打印二叉树 
    	free(T);
    	return 0;
    }

（完）

[20201022190842300.png_pic_center]: /images/20221123/17028ceea1944995aa8db85714a9a379.png