二叉树的基本操作（节点创建、二叉树的创建、遍历、叶子结点的数量、二叉搜索树的插入、二叉搜索树的检索）

桃扇骨 2023-03-02 05:15 14阅读 0赞

**二叉树的基本操作（节点创建、二叉树的创建、遍历、叶子结点的数量、二叉搜索树的插入、二叉搜索树的检索）**

*  **节点创建**

//节点定义
    typedef struct BTreeNode
    { 
    	int data; 
    	struct BTreeNode* lchild;
    	struct BTreeNode* rchild;
    }BTreeNode;
    
    typedef BTreeNode* btreenode;
    
    //创建节点
    BTreeNode* CreateNode(int val)
    { 
    	BTreeNode* p = (BTreeNode*)malloc(sizeof(btreenode));
    	p->data = val;
    	p->lchild = p->rchild = NULL;
    	return p;
    }

*  **二叉树的创建**

//二叉树的创建
    struct BTreeNode* Create()
    { 
    	int val;
    	scanf("%d",&val);
    	struct BTreeNode* root = (struct BTreeNode*)malloc(sizeof(struct BTreeNode*));
    
    	if (val < 0)
    	{ 
    		return NULL;
    	}
    
    	if (!root)
    	{ 
    		printf("创建失败\n");
    	}
    
    	if (val > 0)
    	{ 
    		root->data = val;
    		root->lchild = Create();
    		root->rchild = Create();
    	}
    
    	return root;
    }

**二叉树的遍历（前序、中序、后序）**

//前序遍历
    void FronTraval(btreenode root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    	printf("%d",root->data);
    	FronTraval(root->lchild);
    	FronTraval(root->rchild);
    }
    
    //中序遍历
    void Midtraval(btreenode root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    	FronTraval(root->lchild);
    	printf("%d", root->data);
    	FronTraval(root->rchild);
    }
    
    
    //后序遍历
    void Midtraval(btreenode root)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    	FronTraval(root->lchild);
    	FronTraval(root->rchild);
    	printf("%d", root->data);
    }

*  **叶子节点的数量**

//二叉树的叶子节点的数量
    int LeafNode(btreenode root)
    { 
    	if (root == NULL)
    	{ 
    		return 0;
    	}
    	if (root->lchild == NULL && root->rchild == NULL)
    	{ 
    		return 1;
    	}
    	else
    	{ 
    		return LeafNode(root->lchild) + LeafNode(root->rchild);
    	}
    }

**- 二叉搜索树的插入**

//二叉搜索树的插入
    void InsertNode(btreenode root, int val)
    { 
    	if (root == NULL)
    	{ 
    		return;
    	}
    	
    	int rootData = root->data;
    
    	//根据值得大小创建相应的节点（左节点）
    	if (root->lchild == NULL && val < rootData)
    	{ 
    		root->lchild = CreateNode(val);
    		return;
    	}
    
    	//根据值得大小创建相应的节点（右节点）
    	if (root->rchild == NULL && val > rootData)
    	{ 
    		root->rchild = CreateNode(val);
    		return;
    	}
    
    	//将值放入相应的节点
    	if (val > rootData)
    	{ 
    		InsertNode(root->rchild, val);
    	}
    	else if (val < rootData)
    	{ 
    		InsertNode(root->lchild, val);
    	}
    }

*  **二叉树的检索**

//二叉搜索树的检索(递归实现)
    void SearchData(int val, btreenode root)
    { 
    	if (root != NULL)
    	{ 
    		if (root->data == val)
    		{ 
    			printf("%d\n",root->data);
    		}
    		else if (val > root->data)
    		{ 
    			SearchData(val,root->lchild);
    		}
    		else if (val < root->data)
    		{ 
    			SearchData(val,root->rchild);
    		}
    	}
    }