[二叉排序树] 插入相同元素的二叉排序树 | 递归与非递归

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

本文主要是介绍[二叉排序树] 插入相同元素的二叉排序树 | 递归与非递归 | 对结构体中指针的理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

【结构体定义】

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

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

递归方法	非递归方法

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

【结果】

【完整代码】

#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; elsepre->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;
}