BST构建树双指针 [英] BST build tree double pointers
本文介绍了BST构建树双指针的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我不能确定如何设置一个指针的指针构建树。就像有一次我已到达叶和呼叫插入，我应该怎么插入另一个元素调用插入根节点或根指针的地址？我觉得这个功能的问题是名字根在哪里，应该是双指针吧？
的#includebst.h
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;//临时节点的任意列表树节点* new_node，*根* TMP，*父母;
INT elemArray [100]，I1，I2，I0;
INT主（INT ARGC，CHAR *的argv []）{ //投掷的错误是*的argv []是不是整数
//假定它是一个整数
INT CNT =的atoi（ARGV [1]）;
的printf（数量为％d \\ n，CNT）;
//
的printf（请输入％i整型值树的地方：\\ n，CNT）;
为（I1 = 0; I1＆下; CNT ++的i1）{
scanf函数（％d个，＆安培; elemArray [I1]）;
} //首先输出中输入值 的printf（输入值：\\ n）;
为（I2 = 0; I2＆下; CNT ++ I2）{
的printf（％d个\\ N，elemArray [12]）;
}
树节点**根=（树节点*）malloc的（sizeof的（树节点*））; buildTree（根，elemArray，CNT）; 的printf（preorder：\\ n）; //遍历
//树节点* tempN =的malloc（sizeof的（树节点*））;
// tempN-＆GT;数据= 5; 遍历（根，preORDER）; //遍历单个节点
的printf（中序：\\ n）; 的printf（后序：\\ n）;
//构建树的每个元素 返回0;
}
这是.h文件
///树形结构的定义
typedef结构树节点{
int数据; //存储在节点的数据
结构树节点*离开; //节点的左子
结构树节点*权利; //节点的右子
}树节点;///这三个支持遍历
的typedef枚举{
preORDER，//父 - ＆GT;左 - ＆GT;对
序，//左 - ＆GT;父 - ＆GT;对
后序//左 - ＆GT;正确的 - ＆GT;亲
} TraversalType;
和最后横动功能，只要它没有第一测试
无效移动（const的树节点*根，常量TraversalType型）{ 如果（类型== preORDER）{
如果（根！= NULL）
{
的printf（％d个根 - ＆GT;数据）;
遍历（根 - ＆GT;左，preORDER）;
遍历（根 - ＆GT;右，preORDER）;
}
}
}无效build_tree（树节点**根，const int的元素[]，const int的计数）{ 树节点*节点=的malloc（sizeof的（树节点*））;
与于节点GT;左=节点 - ＆GT;右= NULL; *根=节点; 对于（INT I0 = 0;＆I0 LT;计数; ++ I 0）{
树节点*节点=的malloc（sizeof的（树节点*））;
*根=节点;
与于节点GT;数据元素= [CNT]
insertNode（及（*根），放大器;节点）;
}}
为什么insertNode得到错误（多），我不知道哪个是指针，也就是结构。 GUYS任何暗示会有帮助吗？
bst.c：94：20：错误：请求成员的东西'左'不是一个结构或联合
插入（根 - ＆GT;左，new_node）;
无效insertNode（树节点**根，树节点* new_node）{ 如果（new_node-＆GT;数据＆LT;＆安培;根 - ＆GT;数据）{
如果（安培;根 - ＆GT;左== NULL）
＆安培;根 - ＆GT;离开== new_node;
其他
插入（根 - ＆GT;左，new_node）;
} 如果（new_node-＆GT;数据GT＆;＆安培;根 - ＆GT;数据）{
如果（安培;根 - ＆GT;右== NULL）
＆安培;根 - ＆GT;右= new_node;
其他
插入（安培;根 - ＆GT;右，new_node）;
}
}
所以编辑2：我有具有build_Tree的头文件（**根，elems []，sizeofElem []），这意味着我需要一个辅助函数插入。 Yes（是）会更容易通过输入开始添加*。
修改1
的#includebst.h
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;//临时节点的任意列表树节点* new_node，*根* TMP，*父，*电流;
INT elemArray [5]，I1，I2，I0;/ *
通过引用根和使用递归插入一个新的节点到树
* / 树节点* getN（INT dataElem）{
树节点* newNode =的malloc（sizeof的（* newNode））;
如果（newNode！= NULL）
{
newNode-＆GT;数据= dataElem;
newNode-＆GT;左= NULL;
newNode-＆GT;右= NULL;
} 返回newNode;
}/ **此FUNC应该仅仅是树的根在参数，
但我喜欢指针的想法，原因是其有助于创造一个tempory
指针，而不是newNode
** /
树节点* addNodeToTree（树节点*根，int数据）{ 树节点*电流= *根; //当前指针定义为根始终
树节点*父= *根
树节点* newNode = getN（数据）; 如果（*根== NULL）
{
输出（第一个节点）;
*根= newNode;
}
其他
{
而（电流！= NULL）
{
父=电流;
如果（电流 - ＆GT;数据GT＆;数据）
电流=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;数据＆lt;数据）
电流=电流 - ＆GT;的权利;
} 如果（父 - ＆GT;数据GT＆;数据）
父 - ＆GT;左= newNode;
否则，如果（父 - ＆GT;数据＆lt;数据）
父 - ＆GT;右= newNode;
}
}无效build_Tree（树节点**根，const int的元素[]，const int的计数）{ *根=的malloc（sizeof的（树节点））; 对（I0 = 0;＆I0 LT;计数; ++ I 0）{
的printf（％d个\\ N，元素[计数]）;
addNodeToTree（安培;根元素[计数]）;
}}
INT主（INT ARGC，CHAR *的argv []）{ //投掷的错误是*的argv []是不是整数
//假定它是一个整数
INT CNT =的atoi（ARGV [1]）;
的printf（数量为％d \\ n，CNT）;
//
的printf（请输入％i整型值树的地方：\\ n，CNT）;
为（I1 = 0; I1＆下; CNT ++的i1）{
scanf函数（％d个，＆安培; elemArray [I1]）;
}
//首先输出中输入值 的printf（输入值：\\ n）; 为（I2 = 0; I2＆下; CNT ++ I2）{
的printf（％d个\\ N，elemArray [12]）;
的printf（建筑tree0 \\ n）;
} 的printf（建筑树\\ n）;
树节点**根=（树节点**）的malloc（sizeof的（树节点*））;
树节点*根= NULL;
build_Tree（根，elemArray，CNT）;
的printf（preorder：\\ n）; //遍历
//树节点* tempN =的malloc（sizeof的（树节点*））;
// tempN-＆GT;数据= 5; 遍历（*根，preORDER）; //传根指针遍历树 //遍历单个节点
的printf（中序：\\ n）; 的printf（后序：\\ n）;
//构建树的每个元素 返回0;
}无效移动（const的树节点*根，常量TraversalType型）{ 如果（类型== preORDER）{
如果（根！= NULL）
{
的printf（％d个根 - ＆GT;数据）;
遍历（根 - ＆GT;左，preORDER）;
遍历（根 - ＆GT;右，preORDER）;
}
}
}
/ **
无效insertNode（树节点**根，树节点* new_node）{ 如果（new_node-＆GT;数据＆LT; *＆根 - GT;数据）{
如果（*＆根 - GT;左== NULL）
*根 - ＆GT;离开== new_node;
其他
插入（*＆根 - GT;左，new_node）;
} 如果（new_node-＆GT;数据GT＆*＆根 - GT;数据）{
如果（*＆根 - GT;右== NULL）
*根 - ＆GT;右= new_node;
其他
插入（*＆根 - GT;右，new_node）;
}
}
** /
//问题1：什么是
修改2主build_tree
无效build_Tree（树节点**根，const int的元素[]，const int的计数）{ // *根=的malloc（sizeof的（树节点））; 对（I0 = 0;＆I0 LT;计数; I0 ++）{ //创建节点
//
树节点*电流= *根; //当前指针定义为根始终
树节点*父= *根;
//创建不结
int数据=元素[I0]
树节点* newNode = getN（数据）; 如果（*根== NULL）
{
输出（第一个节点％d个\\ N，元素[I0]）;
*根= newNode;
}
其他
{
的printf（下一个节点％d个\\ N，元素[I0]）;
而（电流！= NULL）
{
父=电流;
如果（电流 - ＆GT;数据GT＆;数据）
电流=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;数据＆lt;数据）
电流=电流 - ＆GT;的权利;
} 如果（父 - ＆GT;数据GT＆;数据）
父 - ＆GT;左= newNode;
否则，如果（父 - ＆GT;数据＆lt;数据）
父 - ＆GT;右= newNode;
}
//返回根;
}
} 树节点* getN（INT dataElem）{
树节点* newNode =的malloc（sizeof的（* newNode））;
如果（newNode！= NULL）
{
newNode-＆GT;数据= dataElem;
newNode-＆GT;左= NULL;
newNode-＆GT;右= NULL;
} 返回newNode;
}INT主（INT ARGC，CHAR *的argv []）{ //投掷的错误是*的argv []是不是整数
//假定它是一个整数
INT CNT =的atoi（ARGV [1]）;
的printf（数量为％d \\ n，CNT）;
//
的printf（请输入％i整型值树的地方：\\ n，CNT）;
为（I1 = 0; I1＆下; CNT ++的i1）{
scanf函数（％d个，＆安培; elemArray [I1]）;
}
//首先输出中输入值 的printf（输入值：\\ n）; 为（I2 = 0; I2＆下; CNT ++ I2）{
的printf（％d个\\ N，elemArray [12]）;
的printf（建筑tree0 \\ n）;
} 的printf（建筑树\\ n）;
树节点*根; // =的malloc（sizeof的（树节点*））;
根= NULL;
build_Tree（安培;根，elemArray，CNT）;
的printf（preorder：\\ n）; //遍历
//树节点* tempN =的malloc（sizeof的（树节点*））;
// tempN-＆GT;数据= 5; //移动（*根，preORDER）; //传根指针遍历树 //遍历单个节点
的printf（中序：\\ n）; 的printf（后序：\\ n）;
//构建树的每个元素 返回0;
}
解决方案
假设你创建了一个功能 addNodeToTree（树节点*根，int数据），传根节点，数据将其作为参数。</ p>
现在这个函数里面，只要创建另一个变量说树节点*电流=根这将有助于我们基本上遍历树，并将节点在其各自的位置， 树节点* newNode = NULL （这将成为新的节点，它要插入）。
现在前进，以实际发生的节点之前，我们会先检查，如果根不为空，即树 EMPTY 。为此，我们将测试：
如果（根== NULL）
{
newNode =的malloc（sizeof的（* newNode））; //否则我们可以为这个功能
//啄过。创建一个功能太，
//你看。
根= newNode;
}
如果树不是空缺，即它包含一个节点已经，那么我们将遍历树找到的地方，在那里把新节点。因此，其他部分，将是这样的：
其他
{
父=电流=根;
//这个循环实际上将帮助我们找到`parent`，
//了`newNode`（这是要插入）的
而（电流！= NULL）
{
父=电流;
如果（电流 - ＆GT;数据GT＆;数据）
电流=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;数据＆lt;数据）
电流=电流 - ＆GT;的权利;
}
//现在一次，我们已经发现，该节点，在其下
// newNode将被放置，现在我们要检查一下，是否
// newNode将成为一个'孩子左/右child`
//父。
newNode = getNewNode（数据）;
如果（父 - ＆GT;数据GT＆;数据）
父 - ＆GT;左= newNode;
否则，如果（父 - ＆GT;数据＆lt;数据）
父 - ＆GT;右= newNode;
返回根;
}树节点* getNewNode（int数据）
{
树节点* newNode =的malloc（sizeof的（* newNode））;
如果（newNode！= NULL）
{
newNode-＆GT;数据=数据;
newNode-＆GT;左= NULL;
newNode-＆GT;右= NULL;
} 返回newNode;
}
现在的 newNode 已经插入，你可以简单地遍历以任何顺序看树。
编辑1：
下面是一个工作的例子，只是看看这是有道理的。否则请不要问任何问题，这可能会出现。
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;typedef结构树节点
{
int数据;
结构树节点*离开;
结构树节点*权利;
}树节点;无效的显示（树节点*节点）
{
的printf（********* \\ n）;
的printf（节点地址：％P \\ N，节点）;
的printf（数据：％d个\\ N，及于节点GT;数据）;
的printf（左子：％P \\ N，及于节点GT;左）;
的printf（儿童权利：％P \\ N，及于节点GT;右）;
的printf（********* \\ n）;
}树节点* getNewNode（int数据）
{
树节点* newNode =的malloc（sizeof的（* newNode））;
如果（newNode！= NULL）
{
newNode-＆GT;数据=数据;
newNode-＆GT;左= NULL;
newNode-＆GT;右= NULL;
} 返回newNode;
}INT getIntData（字符*消息）
{
int值= 0;
字符缓冲区[BUFSIZ] = {'\\ 0'};
的fputs（消息，标准输出）;
与fgets（缓冲区，缓冲区尺寸，标准输入）;
sscanf的（缓冲，％D，＆安培;值）; 返回值;
}树节点* addNodeToTree（树节点*根，int数据）
{
树节点*电流=根，*父=根;
树节点* newNode = getNewNode（数据）; 如果（根== NULL）
{
根= newNode;
}
其他
{
而（电流！= NULL）
{
父=电流;
如果（电流 - ＆GT;数据GT＆;数据）
电流=电流 - ＆GT;左;
否则，如果（电流 - ＆GT;数据＆lt;数据）
电流=电流 - ＆GT;的权利;
} 如果（父 - ＆GT;数据GT＆;数据）
父 - ＆GT;左= newNode;
否则，如果（父 - ＆GT;数据＆lt;数据）
父 - ＆GT;右= newNode;
} 返回根;
}无效inOrderTraversal（树节点*根）
{
如果（根！= NULL）
{
inOrderTraversal（根 - ＆GT;左）;
显示器（根）;
inOrderTraversal（根 - ＆GT;右）;
}
}INT主要（无效）
{
树节点*根= NULL;
int数据= 0;
数据= getIntData（输入数据：）;
根= addNodeToTree（根，数据）;
数据= getIntData（输入数据：）;
根= addNodeToTree（根，数据）;
数据= getIntData（输入数据：）;
根= addNodeToTree（根，数据）;
inOrderTraversal（根）; 返回EXIT_SUCCESS;
}
编辑2：
若要 addNodeToTree（...），实施指针的指针，人们只需要改变功能：
无效addNodeToTree（树节点**根，int数据）
{
树节点*电流= *根;
树节点*父= *根;
树节点* newNode = getNewNode（数据）; 如果（*根== NULL）
{
*根= newNode;
}
其他
{
//和以前一样，只是不返回anythingy，从功能。
//由于该函数使用指针的指针，因此任何变化
//完成后，这里将在主要功能自动回报
} //无需返回anythingy
}
和来自呼叫主会是这个样子：
INT主要（无效）
{
树节点*根= NULL;
int数据= 0;
数据= getIntData（输入数据：）;
addNodeToTree（安培;根，数据）;
//只是看到调用addNodeToTree（...），其余的是一样的，前
}
修改3：
为了把元素从一个数组，而不是直接将其添加到树，只是改变了主方法这种形式：
INT主要（无效）
{
树节点*根= NULL;
INT元件[5] = {19，11，5，28，25};
INT大小= sizeof的（元）/ sizeof的（元素[0]）;
INT计数器= 0;
对于（计数器= 0;反＆LT;大小; ++计数器）
{
addNodeToTree（安培;根，元素[计数器]）;
}
inOrderTraversal（根）; 返回EXIT_SUCCESS;
}
I am unsure how to set a pointer to a pointer to build a tree. Like once I have traveled to a leaf and call insert, how should I insert another element calling insert with the root node or the address of the root pointer? I think the problem with this function is the name root where that should be the double pointer right?
#include "bst.h"
#include <stdio.h>
#include <stdlib.h>
//arbitrary list of temp nodes
TreeNode *new_node, *root, *tmp, *parent;
int elemArray[100], i1, i2, i0;
int main( int argc, char *argv[] ) {
//Throw error is *Argv[] is not an integer
//assuming it was an integer
int cnt = atoi( argv[1] );
printf( "number is %d\n", cnt );
//
printf("Enter %i integer values to place in tree:\n", cnt);
for ( i1 = 0; i1 < cnt; ++i1) {
scanf( "%d", &elemArray[i1] );
}
//first ouput "INput Values"
printf( " Input Values:\n " );
for ( i2 = 0; i2 < cnt; ++i2) {
printf( "%d\n", elemArray[i2] );
}
TreeNode** root = (TreeNode*)malloc(sizeof(TreeNode*));
buildTree(root, elemArray, cnt );
printf( "Preorder:\n ");
//traverse
//TreeNode* tempN = malloc(sizeof(TreeNode*));
//tempN->data= 5;
traverse( root, PREORDER);
//traverse a single node
printf( "Inorder:\n ");
printf( "Postorder:\n ");
//Build tree with each element
return 0;
}
This is the .h file
/// The definition of the tree structure
typedef struct TreeNode {
int data ; // the data stored in the node
struct TreeNode* left ; // node's left child
struct TreeNode* right ; // node's right child
} TreeNode;
/// The three supported traversals
typedef enum {
PREORDER, // parent -> left -> right
INORDER, // left -> parent -> right
POSTORDER // left -> right -> parent
} TraversalType;
and lastly the traverse function so far as it failed the first test.
void traverse( const TreeNode* root, const TraversalType type ) {
if ( type == PREORDER) {
if (root != NULL)
{
printf("%d", root->data);
traverse( root->left, PREORDER);
traverse( root-> right, PREORDER);
}
}
}
void build_tree(TreeNode** root, const int elements[], const int count) {
TreeNode* node = malloc(sizeof(TreeNode*));
node->left = node ->right = NULL;
*root = node;
for ( int i0 = 0; i0 < count; ++i0 ){
TreeNode* node = malloc(sizeof(TreeNode*));
*root = node;
node->data = elements[cnt];
insertNode( &(*root), &node );
}
}
Why is the insertNode getting the errors (multiple) and I don't know which is the pointer and which is the struct. GUYS ANY HINT WILL BE HELPFUL PLEASE?
bst.c:94:20: error: request for member 'left' in something not a structure or union
insert(root->left, new_node);
void insertNode(TreeNode** root, TreeNode* new_node) {
if (new_node-> data < &root-> data) {
if (&root-> left == NULL)
&root-> left == new_node;
else
insert(root->left, new_node);
}
if (new_node->data > &root->data) {
if(&root-> right ==NULL)
&root->right = new_node;
else
insert(&root->right, new_node);
}
}
SO for Edit 2: I do have a header file which has a build_Tree(**root, elems[], sizeofElem[]), which means i need a helper function insert. Yes is would be easier to add by input starting*.
Edit 1
#include "bst.h"
#include <stdio.h>
#include <stdlib.h>
//arbitrary list of temp nodes
TreeNode *new_node, *root, *tmp, *parent, *current;
int elemArray[5], i1, i2, i0;
/*
Insert a new node into the tree by referencing the root and using recursion
*/
TreeNode* getN(int dataElem) {
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = dataElem;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
/** This func should just be the root of the tree in the parameter,
but I like the idea of a pointer becuase it helps to create a tempory
pointer rather than newNode
**/
TreeNode* addNodeToTree(TreeNode *root, int data) {
TreeNode *current = *root; //define the current pointer to the root always
TreeNode *parent = *root
TreeNode *newNode = getN(data);
if (*root == NULL)
{
printf("First Node");
*root = newNode;
}
else
{
while(current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
}
}
void build_Tree(TreeNode** root, const int elements[], const int count) {
*root = malloc(sizeof(TreeNode));
for ( i0 = 0; i0 < count; ++i0 ){
printf("%d\n", elements[count]);
addNodeToTree(&root, elements[count]);
}
}
int main( int argc, char *argv[] ) {
//Throw error is *Argv[] is not an integer
//assuming it was an integer
int cnt = atoi( argv[1] );
printf( "number is %d\n", cnt );
//
printf("Enter %i integer values to place in tree:\n", cnt);
for ( i1 = 0; i1 < cnt; ++i1) {
scanf( "%d", &elemArray[i1] );
}
//first ouput "INput Values"
printf( " Input Values:\n " );
for ( i2 = 0; i2 < cnt; ++i2) {
printf( "%d\n", elemArray[i2] );
printf("building tree0\n");
}
printf("building tree\n");
TreeNode** root = (TreeNode**)malloc(sizeof(TreeNode*));
TreeNode *root = NULL;
build_Tree(root, elemArray, cnt );
printf( "Preorder:\n ");
//traverse
//TreeNode* tempN = malloc(sizeof(TreeNode*));
//tempN->data= 5;
traverse( *root, PREORDER); //pass the pointer of root to traverse the tree
//traverse a single node
printf( "Inorder:\n ");
printf( "Postorder:\n ");
//Build tree with each element
return 0;
}
void traverse( const TreeNode* root, const TraversalType type ) {
if ( type == PREORDER) {
if (root != NULL)
{
printf("%d", root->data);
traverse( root->left, PREORDER);
traverse( root-> right, PREORDER);
}
}
}
/**
void insertNode(TreeNode** root, TreeNode* new_node) {
if (new_node-> data < *root-> data) {
if (*root-> left == NULL)
*root-> left == new_node;
else
insert(*root->left, new_node);
}
if (new_node->data > *root->data) {
if(*root-> right ==NULL)
*root->right = new_node;
else
insert(*root->right, new_node);
}
}
**/
//question1: what is the
Edit 2 for main and build_tree
void build_Tree(TreeNode** root, const int elements[], const int count) {
//*root = malloc(sizeof(TreeNode));
for ( i0 = 0; i0 < count; i0++ ){
//create the node
//
TreeNode *current = *root; //define the current pointer to the root always
TreeNode *parent = *root;
//dont create node
int data = elements[i0];
TreeNode *newNode = getN(data);
if (*root == NULL)
{
printf("First Node %d\n", elements[i0]);
*root = newNode;
}
else
{
printf("Next Node %d\n", elements[i0]);
while(current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
}
//return root;
}
}
TreeNode* getN(int dataElem) {
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = dataElem;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
int main( int argc, char *argv[] ) {
//Throw error is *Argv[] is not an integer
//assuming it was an integer
int cnt = atoi( argv[1] );
printf( "number is %d\n", cnt );
//
printf("Enter %i integer values to place in tree:\n", cnt);
for ( i1 = 0; i1 < cnt; ++i1) {
scanf( "%d", &elemArray[i1] );
}
//first ouput "INput Values"
printf( " Input Values:\n " );
for ( i2 = 0; i2 < cnt; ++i2) {
printf( "%d\n", elemArray[i2] );
printf("building tree0\n");
}
printf("building tree\n");
TreeNode* root; //= malloc(sizeof(TreeNode*));
root = NULL;
build_Tree(&root, elemArray, cnt );
printf( "Preorder:\n ");
//traverse
//TreeNode* tempN = malloc(sizeof(TreeNode*));
//tempN->data= 5;
//traverse( *root, PREORDER); //pass the pointer of root to traverse the tree
//traverse a single node
printf( "Inorder:\n ");
printf( "Postorder:\n ");
//Build tree with each element
return 0;
}
解决方案
Say you created a function addNodeToTree(TreeNode *root, int data), pass the root node, and data to it as argument.
Now inside this function, simply create another variable say TreeNode *current = root which will help us basically to traverse the tree and place the node at its respective position, and TreeNode *newNode = NULL(this will become the new node, which is to be inserted).
Now before moving ahead, to actually place the node, we will first check, if the root is not null, i.e. the tree is EMPTY. For that, we will test:
if (root == NULL)
{
newNode = malloc(sizeof(*newNode)); // else we can make a function for this
// thingy too. Creating a function too,
// for you to look at.
root = newNode;
}
If the tree is not EMPTY, i.e. it contains a node already, then we will traverse the tree to find the place, where to put the new node. So the else part, will be like:
else
{
parent = current = root;
// This loop will actually help us, find the `parent`,
// of the `newNode`(which is to be inserted)
while (current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
// Now once, we have found, the node, under which the
// newNode will be placed, now we have to check, whether
// newNode will become a `left child/right child` of the
// parent.
newNode = getNewNode(data);
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
return root;
}
TreeNode * getNewNode(int data)
{
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
Now the newNode has been inserted, and you can simply traverse in any order to see the Tree.
EDIT 1:
Here is one working example, just see if this makes sense. Else please do ask any question, that might may arise.
#include <stdio.h>
#include <stdlib.h>
typedef struct TREENODE
{
int data;
struct TREENODE *left;
struct TREENODE *right;
}TreeNode;
void display(TreeNode *node)
{
printf("*********************************\n");
printf("Address of Node: %p\n", node);
printf("Data: %d\n", node->data);
printf("Left Child: %p\n", node->left);
printf("Right Child: %p\n", node->right);
printf("*********************************\n");
}
TreeNode * getNewNode(int data)
{
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
int getIntData(char *message)
{
int value = 0;
char buffer[BUFSIZ] = {'\0'};
fputs(message, stdout);
fgets(buffer, sizeof(buffer), stdin);
sscanf(buffer, "%d", &value);
return value;
}
TreeNode * addNodeToTree(TreeNode *root, int data)
{
TreeNode *current = root, *parent = root;
TreeNode *newNode = getNewNode(data);
if (root == NULL)
{
root = newNode;
}
else
{
while(current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
}
return root;
}
void inOrderTraversal(TreeNode *root)
{
if (root != NULL)
{
inOrderTraversal(root->left);
display(root);
inOrderTraversal(root->right);
}
}
int main(void)
{
TreeNode *root = NULL;
int data = 0;
data = getIntData("Enter Data: ");
root = addNodeToTree(root, data);
data = getIntData("Enter Data: ");
root = addNodeToTree(root, data);
data = getIntData("Enter Data: ");
root = addNodeToTree(root, data);
inOrderTraversal(root);
return EXIT_SUCCESS;
}
EDIT 2:
To make addNodeToTree(...), implement pointer to a pointer, one simply needs to change the function as:
void addNodeToTree(TreeNode **root, int data)
{
TreeNode *current = *root;
TreeNode *parent = *root;
TreeNode *newNode = getNewNode(data);
if (*root == NULL)
{
*root = newNode;
}
else
{
// same as before, just don't return anythingy, from the function.
// As the function uses pointer to a pointer, hence whatever changes
// are done, here will be reciprocated in the main function automatically
}
// no need to return anythingy
}
And the call from main will now look like:
int main(void)
{
TreeNode *root = NULL;
int data = 0;
data = getIntData("Enter Data: ");
addNodeToTree(&root, data);
// Just see the call to addNodeToTree(...), the rest is same, as before
}
EDIT 3:
In order to take elements from an array instead of adding them directly to tree, just change the main method to this form:
int main(void)
{
TreeNode *root = NULL;
int element[5] = {19, 11, 5, 28, 25};
int size = sizeof(element) / sizeof(element[0]);
int counter = 0;
for (counter = 0; counter < size; ++counter)
{
addNodeToTree(&root, element[counter]);
}
inOrderTraversal(root);
return EXIT_SUCCESS;
}
这篇关于BST构建树双指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
