精华内容
下载资源
问答
  • 其必须满足:要么为空或者上任一结点,其值大于等于其左子树上的任意结点值(左子树非空),且小于其右子上任意结点的值(右子非空),其左右子树也满足该定义。 结构体: typedef struct node ...

    定义:

     二叉排序树是一棵特殊的二叉树。其必须满足:要么为空树或者树上任一结点,其值大于等于其左子树上的任意结点值(左子树非空),且小于其右子树上任意结点的值(右子树非空),其左右子树也满足该定义。

    结构体:

    typedef struct node									//二叉树结构体			
    {
    	struct node * lchild;
    	struct node * rchild;
    	int data;
    }Node;
    
    创建二叉排序树:

     创建的过程是先进行查找,然后在合适位置将结点插入,所以结点插入完毕则创建成功。

    int CreateNode(int s,Node * & p)						//创建二叉排序树的结点
    {
    	if (p)
    	{
    		if (s<p->data) return CreateNode(s,p->lchild);	//目标结点在左子树中
    		else if (s==p->data)return 0;					//已存在该结点,无需插入
    		else return CreateNode(s,p->rchild);			//目标结点在右子树中
    	}
    	else												//不存在该结点,则插入
    	{
    		p = (Node *)malloc(sizeof(Node));
    		p->data = s;
    		p->lchild = NULL;
    		p->rchild = NULL;
    		return 1;
    	}
    }
    
    int BuildBST(int input[],int length,Node * & T)			//建立二叉排序树
    {
    	int node_nume =0;									//树中不重复的结点数结点
    	for (int i = 0; i < length; i++)
    		node_nume+=CreateNode(input[i],T);
    	return node_nume;
    }
    删除二叉排序树:

    void DeletTree(Node * p)								//删除树
    {
    	if (p)
    	{
    		DeletTree(p->lchild);
    		DeletTree(p->rchild);
    		free(p);
    	}
    }

    二叉树的递归遍历核心代码:

    void PreOder(Node * p,int &node_num)					//后序遍历
    {
    	if (p)
    	{
    		printf("%d",p->data);
    		PreOder(p->lchild,node_num);
    		PreOder(p->rchild,node_num);
    	}
    }
    
    void InOder(Node * p,int &node_num)						//中序遍历
    {
    	if (p)
    	{
    		InOder(p->lchild,node_num);
    		printf("%d",p->data);
    		InOder(p->rchild,node_num);
    	}
    }
    
    void PostOder(Node * p,int &node_num)					//后序遍历
    {
    	if (p)
    	{
    		PostOder(p->lchild,node_num);
    		PostOder(p->rchild,node_num);
    		printf("%d",p->data);
    	}
    }

    下面是输入n个整数,建立二叉排序树,并输出各项遍历序列的主函数:

    int main()
    {
    	int n;												//输入序列的长度
    	int input[100];										//输入序列
    	int node_num;										//树中不重复结点数
    	Node * Tree =NULL;
    	while (scanf("%d",&n)!=EOF)
    	{
    		for (int i = 0; i < n; i++)
    			scanf("%d",&input[i]);
    		
    		n=BuildBST(input,n,Tree);						//建立排序树
    
    		printf("前序为:");
    		node_num =n;
    		PreOder(Tree,node_num);							//先序遍历
    		printf("中序为:");
    		node_num =n;
    		InOder(Tree,node_num);							//中序遍历
    		printf("后序为:");
    		node_num =n;
    		PostOder(Tree,node_num);						//后序遍历
    
    		DeletTree(Tree);								//删除树
    		
    	}
    	return 0;
    }


    黑框输出运行结果:



    后记:

     遍历运用很复杂,要多看些应用实例


    展开全文
  • 超全C语言二叉树基本操作及讲解

    万次阅读 多人点赞 2018-03-29 17:03:36
    当然,我们也可以为我们的的节点结构体重新定义一下名字,使用C语言中的typedef方法就可以了。   typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } BiNode, *...

    今天刷LeetCode上的题的时候,做到了关于二叉树的题,于是决定把这一块的知识整理一下。

    1、二叉树的定义

    二叉树通常以结构体的形式定义,如下,结构体内容包括三部分:本节点所存储的值、左孩子节点的指针、右孩子节点的指针。这里需要注意,子节点必须使用指针,就像我们定义结构体链表一样,下一个节点必须使用地址的方式存在在结构体当中。

     

    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    };

    当然,我们也可以为我们的的树节点结构体重新定义一下名字,使用C语言中的typedef方法就可以了。

     

    typedef struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    } BiNode, *BiTree;

    在本篇博客中,我们还是使用第一种方法来定义结构体,因为这是LeetCode中定义二叉树的方式,同时也方便下面讲解创建二叉树。

    2、二叉树的创建

     

    二叉树的操作通常使用递归方法,如果递归不太明白,建议去对此进行一下学习和练习。二叉树的操作可以分为两类,一类是需要改变二叉树的结构的,比如二叉树的创建、节点删除等等,这类操作,传入的二叉树的节点参数为二叉树指针的地址,这种参入传入,便于更改二叉树结构体的指针(即地址)。这里稍微有一点点绕,可能需要多思考一下。

    如下是二叉数创建的函数,这里我们规定,节点值必须为大于0的数值,如果不是大于0的数,则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树

    int CreateTree(struct TreeNode** root) {
    
    	int val;
    	scanf_s("%d", &val);
    	if (val <= 0) {
    		*root = NULL;
    		return 0;
    	}
    
    	*root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    	if (!root) {
    		printf("创建失败\n");
    	}
    
    	if (val > 0) {
    		(*root)->val = val;
    		CreateTree(&((*root)->left));
    		CreateTree(&((*root)->right));
    	}
    	return 0;
    }

    因为有小伙伴问了,可否在构建二叉树传入的参数为一级地址。上述的方法是一定要传二级参数的,但是这里给出一个传一级参数的方法,小伙伴也可以通过对比两种方法,对二叉树的构建和传参方式有更深的理解。

    struct TreeNode* Create(){
    	int val;
    	scanf("%d", &val);
    	
    	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
    	if (val <= 0) {
    		return NULL;
    	}
    	
    	if (!root) {
    		printf("创建失败\n");
    	}
     
    	if (val > 0) {
    		root->val = val;
    		root->left = Create();
    		root->right = Create();
    	}
    	 
    	return root;
    }

    3、先、中、后序遍历二叉树

    二叉树示例

    先序、中序和后序,实际上是指的根节点在子节点的先中后。以上图为例,

    先序为:3、2、2、3、8、6、5、4,

    中序为:2、2、3、3、4、5、6、8,

    后序为2、3、2、4、5、6、8、3。

    其实这三种遍历方式,实现过程还是十分相似的,在递归顺序方面有些不同,其他都一样,代码量很少,如下。

    先序:

    void PreOrderTree(struct TreeNode* root) {
    	if (root == NULL) {
    		return;
    	}
    	printf("%d ", root->val);
    	PreOrderTree(root->left);
    	PreOrderTree(root->right);
    }

    中序:

    void InOrderTree(struct TreeNode* root) {
    	if (root == NULL) {
    		return;
    	}
    	InOrderTree(root->left);
    	printf("%d ", root->val);
    	InOrderTree(root->right);
    }

    后序:

    void PostOrderTree(struct TreeNode* root) {
    	if (root == NULL) {
    		return;
    	}
    	PostOrderTree(root->left);
    	PostOrderTree(root->right);
    	printf("%d ", root->val);
    }

    验证程序是否正确的主函数和结果图如下:

    int main()
    {
    	struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*));
    
        //第二种构建方式:
        //root = Create();
    	
    	CreateTree(&(root));
    	printf("先序排列为:");
    	PreOrderTree(root);
    	printf("\n中序排列为:");
    	InOrderTree(root);
    	printf("\n后序排列为:");
    	PostOrderTree(root);
    	return 0;
    }

     

     

     

    4、二叉树的最大深度(LeetCode104)

    int maxDepth(struct TreeNode* root) {
    	if (root == NULL) {
    		return 0;
    	}
    	else {
    		int maxLeft = maxDepth(root->left), maxRight = maxDepth(root->right);
    		if (maxLeft > maxRight) {
    			return 1 + maxLeft;
    		}
    		else {
    			return 1 + maxRight;
    		}
    	}
    }

    这也是LeetCode 104 Maximum Depth of Binary Tree题的答案,在做这道题的时候,一开始我并没有定义maxLeft和maxRight这两个变量,直接在判断处调用函数,这导致整个程序的运行时间过长。这道题的思想很简单,一棵树的最大深度,左子树和右子树的最大深度+1即可,使用递归,截止条件判断好了,很容易就能够做出来。

    5、二叉树叶子节点的数量

    这里我们要提到“度”的定义,简单来说,一个节点的度就是一个节点的分支数,二叉树中的节点按照度来分类的话,分为三类,度分别为0、1、2的节点,我们将其数量表示为n0、n1、n2,且我们将一棵树的总结点数量用N来表示。那么一个数的叶子节点的数量即为n0,且有N=n0+n1+n2。如果我们按照一棵树的子节点数来计算一棵树的总结点数,那么一棵二叉树树的总结点数N=2*n2+n1+1,最后一个1表示树的根节点。我们将关于N的两个等式合并,则有结论:

    n0=n2+1

    上述的结论与我们下面求叶子节点没有什么关系,只是作为一个知识的普及。

    叶子节点计算方法如下:

    int LeafNodeNum(struct TreeNode* root) {
    	if (root == NULL) {
    		return 0;
    	}
    
    	if (root->left == NULL&&root->right == NULL) {
    		return 1;
    	}
    	else {
    		return LeafNodeNum(root->left) + LeafNodeNum(root->right);
    	}
    }

     

    展开全文
  • 功能 二叉树操作: ...二叉搜索树操作: 插入 最值(最大值,最小值) 删除 代码 #include stdio.h> #include stdlib.h> #include stdbool.h> typedef struct _BinNode BinNode; struct _BinN

    功能

    二叉树操作:

    • 创建二叉树
    • 遍历二叉树(前序,中序,后续)
    • 计算高度
    • 计算结点数目
    • 清空二叉树
    • 空树判断

    二叉搜索树操作:

    • 插入
    • 最值(最大值,最小值)
    • 删除

    代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    typedef struct _BinNode BinNode;
    struct _BinNode{
        char ch;
        BinNode * left;
        BinNode * right;
    };
    //创建二叉树  指针的指针
    void CreateNode(BinNode ** binNode){
        char ch;
        scanf("%c",&ch);
        if(ch=='*'){
            *binNode=NULL;
        }
        else{
            *binNode=(BinNode*)malloc(sizeof(BinNode));
            (*binNode)->ch=ch;
            CreateNode(&(*binNode)->left);
            CreateNode(&(*binNode)->right);
        }
    }
    //前序遍历
    void PreShow(BinNode *binNode){
        if(!binNode){
            return;
        }
        else{
            printf("%c",binNode->ch);
            PreShow(binNode->left);
            PreShow(binNode->right);
        }
    }
    //中序遍历
    void MidShow(BinNode *binNode){
        if(!binNode){
            return;
        }
        else{
            MidShow(binNode->left);
            printf("%c",binNode->ch);
            MidShow(binNode->right);
        }
    }
    //后序遍历
    void BackShow(BinNode *binNode){
        if(!binNode){
            return;
        }
        else{
            BackShow(binNode->left);
            BackShow(binNode->right);
            printf("%c",binNode->ch);
        }
    }
    //二叉树高度-最大值函数
    int Max(int a,int b){
        return a>b?a:b;
    }
    //二叉树高度
    int BinHight(BinNode * binNode){
        if(binNode){
            return Max(BinHight(binNode->left),BinHight(binNode->right))+1;
        }
        else{
            return 0;
        }
    }
    //二叉树结点个数
    int NodeNum(BinNode * binNode){
        if(!binNode){
            return 0;
        }
        else{
            return NodeNum(binNode->left)+NodeNum(binNode->right)+1;
        }
    }
    //清空二叉树
    void BinFree(BinNode **pBinNode){
        if(!*pBinNode){
            return;
        }
        else{
            BinFree(&(*pBinNode)->left);
            BinFree(&(*pBinNode)->right);
            free(*pBinNode);
            *pBinNode=NULL;
        }
    }
    //空树判断
    bool BinIsEmpty(BinNode *binNode){
        if(binNode){
            return false;
        }
        else{
            return true;
        }
    
    }
    
    //二叉搜索树搜索
    BinNode* BinSFind(char data,BinNode * binNode){
        if(binNode==NULL){
            return NULL;
        }
        if(data>binNode->ch){
            return BinSFind(data,binNode->right);
        }
        else if(data<binNode->ch){
            return BinSFind(data,binNode->left);
        }
        else{
            return binNode;
        }
    }
    //二叉搜索树最值
    BinNode * BinSMax(BinNode * binNode){
        if(binNode!=NULL)
            while (binNode->right!=NULL)
                binNode=binNode->right;
        return binNode;
    }
    //二叉搜索树最小值
    BinNode * BinSMin(BinNode * binNode){
        if(binNode==NULL)return NULL;
        else if(binNode->left==NULL)return binNode;
        else return BinSMin(binNode->left);
    }
    //二叉搜索树插入算法
    BinNode * BinSInsert(char data,BinNode * binNode){
        if(binNode==NULL){
            binNode=(BinNode*)malloc(sizeof(BinNode));
            if(binNode){
                binNode->ch=data;
                binNode->left=binNode->right=NULL;
            }
            else{
                printf("OUT OF SPACE");
            }
        }
        else if(data>binNode->ch){
            binNode->right=BinSInsert(data,binNode->right);
        }
        else if(data<binNode->ch){
            binNode->left=BinSInsert(data,binNode->left);
        }
        return binNode;
    }
    //二叉搜索树 删除
    BinNode * BinSDelete(char data,BinNode * binNode){
        BinNode * TmpCell;
        if(binNode==NULL){
            printf("NOT FOUND!");
        }
        else if(data<binNode->ch){
            binNode->left=BinSDelete(data,binNode->left);
        }
        else if(data>binNode->ch){
            binNode->right=BinSDelete(data,binNode->right);
        }
        else if(binNode->left&&binNode->right){
            TmpCell=BinSMin(binNode->right);
            binNode->ch=TmpCell->ch;
            binNode->right=BinSDelete(binNode->ch,binNode->right);
        }
        else {
            TmpCell=binNode;
            if(binNode->left==NULL){
                binNode=binNode->right;
            }
            else if(binNode->right==NULL){
                binNode=binNode->left;
            }
            free(TmpCell);
        }
        return binNode;
    }
    
    int main(){
    
        char data='3';
        BinNode * binNode;
        printf("请输入二叉树前序遍历结果:");
        CreateNode(&binNode);
        printf("前序遍历结果:");
        PreShow(binNode);
        printf("\n中序遍历结果:");
        MidShow(binNode);
        printf("\n后序遍历结果:");
        BackShow(binNode);
        printf("\n高度:%d",BinHight(binNode));
        printf("\n结点个数:%d\n",NodeNum(binNode));
    
        //清空二叉树
        //BinFree(&binNode);
        //if(BinIsEmpty(binNode)){printf("\n二叉树已清空");}
    
        //二叉搜索树
        //************************************************************
        //前序遍历输入:531**4**86*7**9**
        setbuf(stdin, NULL);//使stdin输入流由默认缓冲区转为无缓冲区
    
        //查找实现
        printf("\n请输入查找字符:");
        scanf("%c",&data);
        BinNode * get=BinSFind(data,binNode);
        if(get!=NULL){
            printf("找到在%p位置,结果为%c",get,*get);
        }
        else{
            printf("未找到!");
        }
    
        //最值
        printf("\n最大值为:%c",BinSMax(binNode)->ch);
        printf("\n最小值为:%c",BinSMin(binNode)->ch);
    
        //插入
        //BinSInsert('2',binNode);
        //printf("\n插入2后遍历结果:");
        //PreShow(binNode);
    
        BinSDelete('8',binNode);
        printf("\n删除8后前序遍历:");
        PreShow(binNode);
    
        BinSDelete('4',binNode);
        printf("\n删除4后前序遍历:");
        PreShow(binNode);
    
        return 0;
    }

    结果
    这里写图片描述

    参考资料:数据结构预算法-C语言描述(原书第二版)

    展开全文
  • // 二叉搜索上执行二分查找算法 Node* FindBSTree(Tree tree, Item data) { if(NULL == tree) { return NULL; } if(Less(data, tree->data)) { return FindBSTree(tree->left, data); } ...

    0、准备工作

     

    #include <stdlib.h>
    
    typedef int Item;
    int Less(Item left, Item right)
    {
        return (left < right);
    }
    int Greater(Item left, Item right)
    {
        return Less(right, left);
    }
    int Equal(Item left, Item right)
    {
        return !(Less(left, right)) && !Less(right, left);
    }
    
    typedef struct Node Node;
    typedef struct Node *Tree;
    struct Node
    {
        Item data;
        Tree left;
        Tree right;
    };
    
    typedef void(*Visit)(Node*);
    void PrintNode(Node *node)
    {
        printf("%d\n", node->data);
    }
    


    1、构建二叉搜索树

    /* 新建一个节点 */
    Node* NewNode(Item data)
    {
        Node *pNode = (Node*)malloc(sizeof(Node));
        if(NULL == pNode)
        {
            return NULL;
        }
    
        pNode->data = data;
        pNode->left = NULL;
        pNode->right = NULL;
    
        return pNode;
    }
    
    /* 构造二叉搜索树 */
    Tree InsertBSTree(Tree tree, Node *pNode)
    {
        if(NULL == tree)
        {
            return pNode;
        }
    
        if(Less(pNode->data, tree->data))
        {
            tree->left = InsertBSTree(tree->left, pNode);
        }
        else if(Greater(pNode->data, tree->data))
        {
            tree->right = InsertBSTree(tree->right, pNode);
        }
        else
        {
            /* do nothing */
        }
    
        return tree;
    }


    2、遍历二叉树

    /* 中序遍历二叉树 */
    void TraverseInOrder(Tree tree, Visit visit)
    {
        if(NULL == tree)
        {
            return;
        }
    
        TraverseInOrder(tree->left, visit);
        visit(tree);
        TraverseInOrder(tree->right, visit);
    }


    3、二分查找算法

    // 二叉搜索树上执行二分查找算法
    Node* FindBSTree(Tree tree, Item data)
    {
        if(NULL == tree)
        {
            return NULL;
        }
    
        if(Less(data, tree->data))
        {
            return FindBSTree(tree->left, data);
        }
        else if(Greater(data, tree->data))
        {
            return FindBSTree(tree->right, data);
        }
        else
        {
            return tree;
        }
    }
    


     

    展开全文
  • 我们在上一篇博客中讲解了二叉树,这一次我们来实现二叉树的进阶——二叉查找(Binary Search Tree),又称二插排序(Binary Sort Tree)。所以简称为BST。二插查找的定义如下:  1.若左子树不为空,则左子树...
  • C语言--基本操作

    千次阅读 2012-05-30 14:35:40
     if(bt)//不为空,则执行如下操作  {  printf("%d ",bt->nodecontent);  PreOrder(bt->leftchild);  PreOrder(bt->rightchild);  }  return; } void MidOrder(PTREE bt) //中序遍历 ...
  • 数据结构的操作比较全,链表,栈,队列,,图都有,配有几个例子 希望对有帮助的朋友有用...
  • Avl基本操作c语言实现)

    千次阅读 2016-03-17 16:42:19
    printf("| Avl基本操作如下: |\n"); printf("| 0.创建Avl |\n"); printf("| 1.查找 |\n"); printf("| 2.插入 |\n"); printf("| 3.删除 |\n"); printf("| 4.将Avl遍历 |\n"); printf("|******...
  • #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct BTree{ int date; BTree *lchild; BTree *rchild; }BTree; //插入数据 int BSTInsert(BTree *&... if...
  • 二叉查找是一种特殊的二叉树,它不仅是一颗二叉树,还满足如下性质 对于任何非叶子节点,他的左节点都小于它本身,而右节点都大于其本身. 它的左右子树也分别而二叉搜索 一般情况下,在这么一棵中进行查找,...
  • 数据结构的操作比较全,链表,栈,队列,,图都有,而且还有几个系统奉上
  • C语言实现二叉树的基本操作

    万次阅读 多人点赞 2016-03-11 21:45:03
    我在前面的博客中讲解了链表、栈和队列,这些数据结构其实都是线性表,并且给...对于操作,最基本的创建、遍历、求高、节点数等。代码上传至 https://github.com/chenyufeng1991/BinaryTree 。(1)节点的定义t
  • C语言实现图,及用C语言实现最小生成的代码的方法
  • 该源码使用C实现了最二叉查找基本操作,比如删除、查找,插入等。
  • C语言-二叉树基本操作(通俗易懂!) 要构建二叉树首先要知道二叉树的结构,结构体如下 typedef struct node{ char data; //左孩子 struct node *lchild;//指向左右孩子的节点必须为指针形式 //右孩子 struct ...
  • //二叉排序基本运算算法 #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef int KeyType;//关键码类型 typedef char InfoType; typedef struct node//记录类型 { KeyType ...
  • 操作c语言实现

    千次阅读 2018-01-17 19:48:49
    前言  本文包含二叉树、二叉查找、Av等的定义和相关操作,由于...二.BST定义及其基本操作  印象笔记链接 二.AvTree定义及其基本操作 1.简介  AvTree是BST的一种,但是其每个节点的左子树和右子的高度最
  • b的简单实现与基本操作C语言

    千次阅读 2021-04-27 12:10:12
    今天上完数据结构课,想找找事情做,可本人又懒得刷题...就没事找事看看书上的扩展内容,发现这个b挺有难度,要是能实现也成就感满满了呀。那便话不多说,撸起袖子加油干。 b 看了一篇博客,讲的是真滴好,推荐: ...
  • 及其操作C语言版)

    千次阅读 2016-09-23 09:50:34
    及其操作(C语言版)标签(空格分隔): 数据结构 树树定义和性质: 的定义:是n个(n>=0)有限节点组成一个具有层次关系的集合。 根及子树:在任意一个非空中,有且仅有一个...基本操作:InitTree(&T):构造
  • 首先是定义的的数据结构: typedef struct BiTNode { TElemType data; struct BiTNode *lchild;...下面是的一些基本操作,包括,的建立,的深度,的各种遍历的递归和非递归实现; Status InitBiTree(B
  • 二叉树的基本操作 C语言

    万次阅读 多人点赞 2016-11-07 09:11:30
    二叉树的各项基本操作C语言 struct tree_node{ char id; struct tree_node *left; struct tree_node *right; }; typedef struct tree_node TreeNode; typedef struct tree_no
  • C语言

    万次阅读 多人点赞 2019-12-18 23:01:50
    43.C语言允许直接访问物理地址,能进行位操作。 44.C语言是结构化程序设计语言 45.c程序要通过编译,连接才能得到可执行的目标程序 46.用c语言编写程序,可以编写出任何类型的程序 47.C语言允许有空函数 48.C程序...
  • c语言实现二叉树的基本操作

    千次阅读 多人点赞 2016-11-26 22:31:02
    //删除右子 void deleteRightTree(PBTNode root) { if (root == NULL ) return ; clear( & root -> rchild); root -> rchild = NULL ; } //查找结点 PBTNode search(PBTNode root,char ch) { PBTNode...
  • 以小堆为例, 这个的根节点是这个中的最小的元素 对于任意一个子树来说, 子树的根节点, 小于左右孩子节点的值. 4. 以大堆为例, 这个的根节点是这个树种的最大元素 对于任意一个子树来说, 子树的根节点, 大于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,976
精华内容 16,390
关键字:

c语言树的基本操作

c语言 订阅