[二叉排序树] 插入相同元素的二叉排序树 | 递归与非递归 | 对结构体中指针的理解

朴灿烈づ我的快乐病毒、 2023-06-12 09:16 47阅读 0赞

> 【题目】 设在一棵二叉排序树的每个结点中，含有关键字值key域和统计相同关键字值结点个数的count域  
> 当向该树插入一个元素时  
> 若树中已存在该元素的关键字值相同的结点，则使该结点的count域增1  
> 否则就由该元素生成一个新结点并插入到树中，使其count域+1  
> 【实质】 实现一个可以插入相同元素的二叉排序树-递归与非递归  
> 【讨论】 递归与非递归中指针引用的问题

【结构体定义】

typedef struct BiTNode{ 
    	int key;
    	int count; //保存元素的个数
    	struct BiTNode *lchild;
    	struct BiTNode *rchild;
    }BiTNode, *BiTree;

【对结构体中指针的理解】两种方法中：①递归方法的插入有效；②非递归方法的插入无效，主函数的T还是为NULL。这是为什么？

<table> 
 <thead> 
  <tr> 
   <th>递归方法</th> 
   <th>非递归方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><img src="https://img-blog.csdnimg.cn/20191111211230762.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70" alt=""><br><img src="https://img-blog.csdnimg.cn/20191111213134509.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
   <td><img src="https://img-blog.csdnimg.cn/20191111211336730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"><br><img src="https://img-blog.csdnimg.cn/20191111213148374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
  </tr> 
 </tbody> 
</table>

【问题】非递归能不能像递归那样取到rchild的位置？

【结果】  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

【完整代码】

#include<stdio.h>
    #include<malloc.h>
    
    typedef struct BiTNode{ 
    	int key;
    	int count;
    	struct BiTNode *lchild;
    	struct BiTNode *rchild;
    }BiTNode, *BiTree;
    
    void insert(BiTNode *&T, int key) { 
    	if (!T) { 
    		T = (BiTNode *)malloc(sizeof(BiTNode));
    		T->key = key;
    		T->count = 1;
    		T->lchild=T->rchild=NULL;
    	} else { 
    		if (T->key == key) ++T->count;
    		else if (T->key < key) insert(T->rchild, key);
    		else insert(T->lchild, key);
    	}
    }
    
    void insert_norecursion(BiTNode *&T,int key) { 
    	// 二叉排序树不需要开辟栈，不需要保存所有路径
    	BiTNode *p = T; //当前指针
    	BiTNode *pre = NULL; //p的父亲
    
    	// 开始往下搜索
    	while (p) { 
    		if (p->key == key) {  //找到
    			++p->count; //自增
    			return ;
    		} else {  //没有找到，往下查找
    			pre = p; //保留p的父亲
    			if (p->key < key) p=p->rchild;
    			else p=p->lchild;
    		}
    	}
    	// p==NULL表示找到了新元素插入的位置，即为p的位置
    
    	/* 但直接插入到p无效 p = (BiTNode *)malloc(sizeof(BiTNode)); p->key = key; p->count = 1; p->lchild=p->rchild=NULL; */
    
    	// 插入到p的父亲pre的下面
    	BiTNode *s = (BiTNode *)malloc(sizeof(BiTNode));
    	s->count=1;s->key=key;s->lchild=s->rchild=NULL;
    	if (pre==NULL) //T为空树 
    		T=s; 
    	else if (key < pre->key) //挂在pre的左树上
    		pre->lchild = s; 
    	else
    		pre->rchild = s;
    }
    
    // 按树状打印二叉树：https://geodoer.blog.csdn.net/article/details/82938306
    void PrintAsTree(BiTree T, int i) {  //i代表所在层次
    	int j;
    	if (T) { 
    		PrintAsTree(T->rchild, i+1); //访问右子树
    
    		for (j=0; j<i-1; ++j) printf("\t");
    		printf("%d(%d)\n",	T->key, T->count);
    
    		PrintAsTree(T->lchild, i+1); //访问左子树
    	}
    }
    
    
    /* 测试数据 13 5 4 3 8 5 9 4 7 8 10 9 6 10 */
    int main() { 
    	int n;
    	int key;
    	BiTree T = NULL;
    
    	// 递归
    	scanf("%d", &n);
    	while (n--) { 
    		scanf("%d", &key);
    		insert(T, key);
    	}
    
    	PrintAsTree(T, 1);
    
    	BiTree T2 = NULL;
    	scanf("%d", &n);
    	while (n--) { 
    		scanf("%d", &key);
    		insert_norecursion(T2, key);
    	}
    	PrintAsTree(T2, 1);
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191111210121653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70