≡菜单

具有示例C代码的C二叉树(搜索,删除,插入节点)

二进制树是将数据维护到程序存储器中的数据结构。存在许多数据结构,但是根据对数据结构执行的插入/搜索/删除操作所消耗的时间来选择使用它们。

二叉树是其中之一 数据结构 在插入和搜索操作中非常有效。二叉树在O(logN)上进行插入/搜索/删除操作。

二进制树基本上是树,其中每个节点可以有两个子节点,每个子节点本身可以​​是一个小的二进制树。为了理解它,下面是二叉树的示例图。

二叉树的规则是,小于根节点的子节点保留在左侧,大于根节点的子节点保留在右侧。在本身是子树的子节点中也遵循相同的规则。如上图所示,节点(2、4、6)位于根节点(9)的左侧,而节点(12、15、17)位于根节点(9)的右侧。

我们将通过其操作来了解二叉树。我们将介绍以下操作。

  • 创建二叉树
  • 搜索到二叉树
  • 删除二叉树
  • 显示二叉树

创建二叉树

通过插入根节点及其子节点来创建二叉树。我们将使用 C语言 对于所有示例。以下是插入功能的代码段。它将插入节点。

11 void insert(node ** tree, int val) {
12 node *temp = NULL;
13 if(!(*tree)) {
14   温度 = (node *)malloc(sizeof(node));
15   温度->left = 温度->right = NULL;
16   温度->data = val;
17   *tree = 温度;
18   返回;
19 }
20
21 if(val < (*tree)->data) {
22      insert(&(*tree)->left, val);
23   } else if(val> (*tree)->data) {
24     insert(&(*tree)->right, val);
25   }
26 }

该函数将根据要添加的节点的值确定位置,并将新节点添加到二叉树中。功能在下面的步骤中进行说明,代码段行映射到下面给出的说明步骤。

[13-19行]首先检查树是否为空,然后将节点插入为根。

[第21行]检查要插入的节点值是否小于根节点值,然后

  • 一种。 [第22行]当左节点为非NULL时,递归调用insert()函数
  • b。 [13-19行]当到达最左边的节点为NULL时,插入新节点。

[第23行]检查要插入的节点值是否大于根节点值,然后

  • 一种。 [第24行]当存在非NULL的右节点时,递归调用insert()函数
  • b。 [13-19行]当到达最右边的节点为NULL时,插入新节点。

搜索二叉树

根据要搜索的节点的值进行搜索,无论该节点是根节点还是位于左或右子树中。以下是搜索功能的代码段。它将搜索节点到二叉树中。

46 node* search(node ** tree, int val) {
47 if(!(*tree)) {
48   返回 NULL;
49  }
50 if(val == (*tree)->data) {
51   返回 *tree;
52  } else if(val< (*tree)->data) {
53    search(&((*tree)->left), val);
54  } else if(val> (*tree)->data){
55    search(&((*tree)->right), val);
56  }
57 }

无论二叉树中是否已经存在相同值的节点,该搜索功能都会搜索节点的值。如果找到,则返回搜索到的节点,否则返回NULL(即无节点)。功能在下面的步骤中进行说明,代码段行映射到下面给出的说明步骤。

  1. [Lines 47-49] Check first if tree is empty, then 返回 NULL.
  2. [第50-51行]检查要搜索的节点值是否等于根节点值,然后返回节点
  3. [第52-53行]检查要搜索的节点值是否小于根节点值,然后用左节点递归调用search()函数
  4. [第54-55行]检查要搜索的节点值是否大于根节点值,然后使用右节点递归调用search()函数
  5. 对于此搜索功能的每个递归调用,重复步骤2、3、4,直到找到要搜索的节点。

删除二叉树

通过删除其子节点和根节点来删除二叉树。以下是删除二叉树的代码段。

38 void deltree(node * tree) {
39 if (tree) {
40   deltree(tree->left);
41   deltree(tree->right);
42   free(tree);
43  }
44 }

该函数将以以下方式删除二叉树的所有节点–左节点,右节点和根节点。功能在下面的步骤中进行说明,代码段行映射到下面给出的说明步骤。

[第39行]首先检查根节点是否为非NULL,然后检查

  • 一种。 [第40行]当左节点为非NULL时,递归调用deltree()函数
  • b。 [第41行]当存在非NULL的右节点时,递归调用deltree()函数
  • C。 [第42行]删除节点。

显示二叉树

二叉树可以三种形式显示-预购,有序和后购。

  • 预购显示根节点,左节点和右节点。
  • 按顺序显示左节点,根节点,然后右节点。
  • 后订单显示左节点,右节点,然后是根节点。

以下是用于显示二叉树的代码段。

28 void print_preorder(node * tree) {
29 if (tree) {
30 printf("%d\n",tree->data);
31 print_preorder(tree->left);
32 print_preorder(tree->right);
33 }
34 }
35 void print_inorder(node * tree) {
36 if (tree) {
37 print_inorder(tree->left);
38 printf("%d\n",tree->data);
39 print_inorder(tree->right);
40 }
41 }
42 void print_postorder(node * tree) {
43 if (tree) {
44 print_postorder(tree->left);
45 print_postorder(tree->right);
46 printf("%d\n",tree->data);
47 }
48 }

这些函数将分别按顺序,顺序和后顺序显示二叉树。功能在下面的步骤中进行说明,代码段行映射到下面给出的说明步骤。

预订显示

  • 一种。 [第30行]显示根节点的值。
  • b。 [第31行]当左节点为非NULL时,递归调用print_preorder()函数
  • C。 [第32行]当右节点为非NULL时,递归调用print_preorder()函数

有序显示

  • 一种。 [第37行]当左节点为非NULL时,递归调用print_inorder()函数
  • b。 [Line38]显示根节点的值。
  • C。 [第39行]当右节点为非NULL时,递归调用print_inorder()函数

订单显示

  • 一种。 [第44行]当左节点为非NULL时,递归调用print_postorder()函数
  • b。 [第45行]当右节点为非NULL时,递归调用print_postorder()函数
  • C。 [Line46]显示根节点的值。

工作程序

注意上面的代码片段是下面的C程序的一部分。下面的程序将是二进制树的工作基本程序。

#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        温度 = (node *)malloc(sizeof(node));
        温度->left = 温度->right = NULL;
        温度->data = val;
        *tree = 温度;
        返回;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    否则if(val> (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        返回 NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    否则if(val> (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    否则if(val== (*tree)->data)
    {
        返回 *tree;
    }
}

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    /* Search node into tree */
    tmp =搜索(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
}

程序输出:

注意,可以在程序的输出和二进制树的显示顺序,顺序和后序形式下引用本文顶部使用的二进制树图。

$ ./a.out
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
Searched node=4

如果您喜欢这篇文章,您可能还会喜欢..

  1. 50个Linux Sysadmin教程
  2. 50个最常用的Linux命令(包括示例)
  3. 排名前25位的最佳Linux性能监视和调试工具
  4. 妈妈,我找到了! – 15个实用的Linux Find命令示例
  5. Linux 101 Hacks第二版电子书 Linux 101黑客手册

Bash 101 Hacks书 Sed和Awk 101黑客手册 Nagios Core 3书 Vim 101黑客手册

{ 34 评论… 加一 }

  • 鲍勃 2013年2月27日,上午9:45

    凉。感谢您的解释。
    使用C ++ STL库,我们可以’不必写这个,但是了解基础知识是件好事。
    如果有时间,最好通过C ++ STL库并给出示例代码来执行此操作,以及其他示例代码(例如,地图,矢量)以示使用

  • 马西奥 2013年2月27日,上午10:18

    当您说O(log N)时:N是节点数还是树的高度?

  • 布普什 2013年2月27日,下午12:36

    很好的解释。但是二叉树没有’关于节点的键值没有任何规则。它’的二叉搜索树。

  • 高朗S 2013年2月27日,下午1:41

    你好,

    好文章!
    1.我认为所提到的解释和算法是二进制搜索树(BST)
    2.同样对于二叉搜索树,最坏情况下的插入/删除/搜索将是O(N),其中N是元素数。当元素按升序或降序排列时,最差的插入情况将发生,其中节点将继续分别追加到右侧或左侧。

  • 乔治·K 2013年3月1日,上午2:22

    有一个简单的C实现很高兴—许多嵌入式micros根本没有C ++,也没有STL。
    对我来说search()没有’t find the ‘4’元素,因此我添加了以下内容:
    node * search2(node * tree,int val){
    if( ! tree ) 返回 NULL;
    if(val 数据) {
    返回 search2(tree->left, val);
    } else if(val> tree->data) {
    返回 search2(tree->right, val);
    }
    返回 tree;
    }

  • 杜斯科科西卡 2013年3月4日,上午2:43

    很好,但是在某些情况下,二叉树还不够好,是的,您可以使用臀部。
    但是,我想了解的是可以包含许多子树的树。
    就像多路树。
    那将是不错的文章…

  • 罗伯特·尼克斯 2013年3月27日,下午1:07

    您的程序和描述中缺少的功能正在平衡二叉树…

    对于您的实现,您可以向程序提供的最坏的数据将是一个预排序列表,因为所有值都将沿树的右侧向下层叠,根本不使用左侧的节点。实际上,这将只是一个链表,其中包含左节点地址的许多无用比较。

    添加插入后要调用的树平衡例程可以解决此问题。

  • Payal 2013年4月7日,上午4:46

    搜索不是’t working:(

  • 2013年5月6日,下午5:36

    您能指出我将其应用于字符串而不是整数的方向吗?说用H,G,A等建树…

  • 罗伯特·尼克斯 2013年5月7日,下午6:45

    由于它’只是比较,该代码对于数字或字母应同样有效。只需更改使用的变量类型。

  • 杜斯科科西卡 2013年5月8日,上午7:08

    现在听起来可能很有趣,但是如果您想将char和int或float结合起来,以及其他一些东西,则可以使用并集,结构等等。…

  • 维斯努萨克蒂 2013年5月27日,下午6:46

    坦克’s。但功能搜索无效,请在功能中插入“temp” that never used

  • 黛比·徐 2013年6月19日,下午12:26

    “tmp = search(&root, 4);” could be “tmp = search(root,4)”,当然您需要将搜索原型更改为“node *搜索(node * tree,int val)”并在内部执行。

    无论哪种方式,我都遇到了搜索问题:实际上,代码找到了搜索到的节点,’只是“tmp=xxx” doesn’工作。我先打印出search()返回的值,然后再将其分配给search()结果的tmp,’t match !!! can’找出原因。所以我在search()中添加了第三个参数,以得到如下结果:

    节点*搜索(节点*树,整数,节点**已找到)
    {
    * found = NULL;

    if(!(树))
    {
    返回 NULL;
    }

    if(val 数据)
    {
    搜索(((树)->left), val, found);
    }
    否则if(val> (tree)->data)
    {
    搜索(((树)->right), val, found);
    }
    否则if(val ==(tree)->data)
    {
    *发现=树;
    返回 tree;
    }
    }

    然后像这样在main中调用它:

    tmp1 =搜索(root,15,&tmp2);

    现在,tmp2指向右节点,但是tmp1指向一些垃圾。

    任何人都可以弄清楚为什么原始的search()结果可以’不能正确分配?我在Linux 2.6.25上使用了gcc。

  • 黛比 2013年6月19日,下午1:15

    弄清楚了,递归调用没有’t 返回 the value. should be like this:

    if(val 数据)
    {
    返回 搜索(((树)->left), val, found);
    }
    否则if(val> (tree)->data)
    {
    返回 搜索(((树)->right), val, found);
    }

    并无需在搜索中添加第三个参数,而无需这样做。

  • 哈比卜·贝多恩 2013年9月26日,上午2:48

    通过添加来修复搜索功能“return”在两个递归搜索调用之前,例如,
    返回 search(&((*tree)->left), val);

    函数搜索实际上并不需要第一个参数中的指针(指针就足够了),因为调用者不使用该值,并且已经有返回值。

  • 安德鲁 2013年11月2日,下午12:06

    你好它 ’很好地解释了BST。但是我对您的deltree函数有疑问。
    C语言是始终通过值传递函数参数的语言。
    在此函数中,您将根指针作为节点* root传递。 free()函数如何删除其值并释放内存?

  • 哈纳菲 2014年1月30日,上午12:16

    非常感谢。它的工作非常出色。

  • 阿鲁尔 2014年4月15日,上午7:54

    很棒的例子

  • 拉古 2014年4月28日,上午3:16

    嗨..我只是澄清一下…请有人帮我…
    调用插入函数时,需要通过root传递什么‘&’而不是仅仅根除并重新定义它?

    我们可以通过仅传递root并使用单个* De-referencing?来实现。

  • NB·高里 2014年7月31日,上午8:11

    但是tis是用于二叉搜索树的程序,而不是用于二叉树的程序。

  • 尼拉夫 2014年8月6日,上午9:40

    这是二进制搜索树,而不是二进制树。

  • 斯里纳德 2014年11月5日,晚上10:39

    删除功能无法正常工作

  • 阿努帕姆 2014年11月6日,上午10:58

    void deltree(node * tree)应该采用指向指针的指针,即void deltree(node ** tree)

  • 莫希特(Mohit Awasthi) 2014年11月15日,上午7:44

    你好!!我需要一些帮助。
    我正在尝试编写一个程序来从二进制搜索树中删除项目。
    我成功了,但是当我尝试删除根项目时发现了一些问题,所以如果有人可以帮助我,我将非常感激。

    提前致谢。

  • 普拉卡什 2015年5月17日,上午8:45

    太棒了,谢谢

  • 凯坦·哈塔尔 2015年10月23日,上午2:27

    该程序输出是自动的,但如何由用户运行

  • 维品 2015年12月30日,上午8:51

    This is not binary tree , it i的二叉搜索树。

    二叉树:每个节点最多有两片叶子的树

    1
    / \
    2 3

    二进制搜索树:用于搜索。二叉树,其中左子节点仅包含值小于父节点的节点,而右子节点仅包含值大于或等于父节点的节点。

    2
    / \
    1 3

  • 若昂·安东尼奥·卡多佐 2016年3月14日,下午4:09

    Gcc警告搜索功能,因为它到达终点而没有返回任何内容,因此我通过以下方式对其进行了修复:

    node_t *搜索(node_t * tree,int i)
    {
    if(!tree) 返回 NULL;
    否则如果== (*tree).data) 返回 tree;
    否则如果< (*tree).data) 返回 search((*tree).left, i);
    else 返回 search((*tree).right, i);
    }

  • 维拉·雷迪 2016年5月20日,晚上8:33

    关于数据结构的内容非常好

  • yipkit 2016年6月1日,上午5:17
    node delet(ElementType x, node t)
    {
    	node 温度;
    	
    	if(t==NULL)
    		printf("\n Element not found");
    	else
    	{
    		if(xelement)
    			t->left=delet(x,t->left);
    		else if(x> t->element)
    			t->right=delet(x,t->right);
    		else
    		{
    			if(t->left && t->right)
    			{
    				temp=findmin(t->right);
    				t->element=temp->element;
    				t->right=delet(t->element,t->right);
    			}
    			else if(t->left==NULL)
    			{
    				temp=t;
    				t=t->right;
    				free(temp);
    			}
    			else
    			{
    			temp=t;
    			t=t->left;
    			free(temp);
    			}
    		}
    	}
    	return t;
    }
    

    抱歉,此功能可以’跑。如何更正此功能?

  • 乌拜德·拉希德(Ubaid Rasheed) 2017年3月17日,下午1:40

    非常感谢你,我很清楚现在非常感谢你

  • 亚纳尼 2017年4月13日,晚上10:45

    我讨厌你的程序

  • 定时 2017年4月24日,上午7:15

    搜索不需要采用指向指针的指针,因为它不会修改树。它只会增加复杂性。

    node *搜索(node * tree,int val)
    {
        if(!tree)
        {
            返回 NULL;
        }
    
        if(val 数据)
        {
            search(tree->left, val);
        }
        否则if(val> tree->data)
        {
            search(tree->right, val);
        }
        否则if(val== tree->data)
        {
            返回 tree;
        }
    }
    

    这样称呼它
    tmp =搜索(root, 4);

  • 阿迪尔 2017年5月25日,晚上11:59

    这是怎么了?

    void insert(int key, Node root) {
    		if (root == null) {
    			root = new Node(key);
    		} else {
    			if (key > root.val) {
    				insert(key, root.right);
    			}
    			if (key < root.val) {
    				insert(key, root.left);
    			}
    		}
    	}
    

发表评论