C# · 12月 20, 2021

二叉树-C++ | 递归实现二叉树(插入、搜索)

递归实现二叉树(插入、搜索)

// Binary Search Tree – Implemenation in C++

// Simple program to create a BST of integers and search an element in it

#include

using namespace std;

//DeFinition of Node for Binary search tree

struct BstNode {

int data;

BstNode* left;

BstNode* right;

};

// Function to create a new Node in heap

BstNode* GetNewNode(int data) {

BstNode* newNode = new BstNode();

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

}

// To insert data in BST,returns address of root node

BstNode* Insert(BstNode* root,int data) {

if(root == NULL) { // empty tree

root = GetNewNode(data);

}

// if data to be inserted is lesser,insert in left subtree.

else if(data data) {

root->left = Insert(root->left,data);

}

// else,insert in right subtree.

else {

root->right = Insert(root->right,data);

}

return root;

}

//To search an element in BST,returns true if element is found

bool Search(BstNode* root,int data) {

if(root == NULL) {

return false;

}

else if(root->data == data) {

return true;

}

else if(data data) {

return Search(root->left,data);

}

else {

return Search(root->right,data);

}

}

int main() {

BstNode* root = NULL; // Creating an empty tree

/*Code to test the logic*/

root = Insert(root,15);

root = Insert(root,10);

root = Insert(root,20);

root = Insert(root,25);

root = Insert(root,8);

root = Insert(root,12);

// Ask user to enter a number.

int number;

cout<<"Enter number be searchedn";

cin>>number;

//If number is found,print “FOUND”

if(Search(root,number) == true) cout<<"Foundn";

else cout<<"Not Foundn";

}

编程中最没用的东西是源代码,最有用的东西是算法和数据结构。