Scribd
Upload
27 views4 pages

Binary Tree

The document defines functions for operations on binary search trees (BSTs) including insertion, traversal, searching, removal, and checking if a tree is a valid BST. It defines a NODE struct with left/right pointers and a key. Functions are provided to create nodes, insert values, traverse in different orders, get the tree height, count nodes, sum nodes, search, remove nodes, create a tree from an array, remove an entire tree, and check if a tree maintains the BST property. Main tests the functions by building a tree from input and printing the traversal and BST check result.

Uploaded by

TÍN TRẦN TRUNG
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
27 views4 pages

Binary Tree

The document defines functions for operations on binary search trees (BSTs) including insertion, traversal, searching, removal, and checking if a tree is a valid BST. It defines a NODE struct with left/right pointers and a key. Functions are provided to create nodes, insert values, traverse in different orders, get the tree height, count nodes, sum nodes, search, remove nodes, create a tree from an array, remove an entire tree, and check if a tree maintains the BST property. Main tests the functions by building a tree from input and printing the traversal and BST check result.

Uploaded by

TÍN TRẦN TRUNG
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 4

#include<iostream>

#include<cmath>
using namespace std;
struct NODE
{
int key;
NODE* pLeft;
NODE* pRight;
};
NODE* createNode(int x)
{
NODE* p = new NODE;
if (p)
{
p->key = x;
p->pRight = NULL;
p->pLeft = NULL;
}
return p;
}
void Insert(NODE*& pRoot, int x)
{
if (pRoot == NULL)
{
pRoot = createNode(x);
}
else
{
if (pRoot->key > x)
{
Insert(pRoot->pLeft, x);
}
else Insert(pRoot->pRight, x);
}
}
void LNR(NODE* pRoot)
{
if (pRoot)
{
LNR(pRoot->pLeft);
cout << pRoot->key << " ";
LNR(pRoot->pRight);
}
}
void LRN(NODE* pRoot)
{
if (pRoot)
{
LRN(pRoot->pLeft);
LRN(pRoot->pRight);
cout << pRoot->key << " ";
}
}
int chieucaoTree(NODE* pRoot)
{
if (!pRoot) return -1;
else return 1 + max(chieucaoTree(pRoot->pLeft), chieucaoTree(pRoot->pRight));
}
int countNode(NODE* pRoot)
{
if (!pRoot) return 0;
return 1 + countNode(pRoot->pLeft) + countNode(pRoot->pRight);
}
int sumNode(NODE* pRoot)
{
if (!pRoot) return 0;
return pRoot->key + sumNode(pRoot->pLeft) + sumNode(pRoot->pRight);
}
NODE* searchNode(NODE* pRoot, int x)
{
if (!pRoot) return NULL;
else
{
if (pRoot->key == x) return pRoot;
else if (pRoot->key > x) return searchNode(pRoot->pLeft, x);
else return searchNode(pRoot->pRight, x);
}
}
void NodeTheMang(NODE*& x, NODE*& y)
{
if (y->pLeft != NULL)
{
NodeTheMang(x, y->pLeft);
}
else
{
x->key = y->key;
x = y;
y = y->pRight;
}
}
void Remove(NODE*& pRoot, int x)
{
if (!pRoot) return;
else
{
if (pRoot->key > x) Remove(pRoot->pLeft, x);
else if (pRoot->key < x) Remove(pRoot->pRight, x);
else
{
NODE* X = pRoot;
if (pRoot->pLeft == NULL) pRoot = pRoot->pRight;
else if (pRoot->pRight == NULL) pRoot = pRoot->pLeft;
else
{
NodeTheMang(X, pRoot->pRight);
}
delete X;
}

}
}
NODE* createTree(int a[], int n)
{
NODE* Tree = NULL;
for (int i = 0; i < n; i++)
{
Insert(Tree, a[i]);
}
return Tree;
}
void removeTree(NODE*& pRoot)
{
if (pRoot)
{
removeTree(pRoot->pLeft);
removeTree(pRoot->pRight);
NODE* X = pRoot;
if (pRoot->pLeft == NULL) pRoot = pRoot->pRight;
else if (pRoot->pRight == NULL) pRoot = pRoot->pLeft;
else
{
NodeTheMang(X, pRoot->pRight);
}
delete X;
}
}
int heightNode(NODE* pRoot, int value)
{
NODE* p = searchNode(pRoot, value);
return chieucaoTree(p);
}
int level(NODE* pRoot, NODE* p)
{
return chieucaoTree(pRoot) - chieucaoTree(p);
}
int countLeaf(NODE* pRoot)
{
if (!pRoot) return 0;
else
{
int dem = 0;
if (pRoot->pLeft == NULL && pRoot->pRight == NULL)
{
dem++;
}
return dem + countLeaf(pRoot->pLeft) + countLeaf(pRoot->pRight);
}
}
int countLess(NODE* pRoot, int x)
{
if (!pRoot) return 0;
else
{
int dem = 0;
if (pRoot->key < x)
{
dem++;
}
return dem + countLess(pRoot->pLeft,x) + countLess(pRoot->pRight,x);
}
}
int countGreater(NODE* pRoot, int x)
{
if (!pRoot) return 0;
else
{
int dem = 0;
if (pRoot->key > x)
{
dem++;
}
return dem + countGreater(pRoot->pLeft,x) + countGreater(pRoot-
>pRight,x);
}
}
bool isBST(NODE* pRoot)
{
if (!pRoot) return true;
else
{
if (pRoot->pLeft != NULL && (pRoot->pLeft)->key >= pRoot->key) return
false;
if (pRoot->pRight != NULL && (pRoot->pRight)->key <= pRoot->key) return
false;
return isBST(pRoot->pLeft) && isBST(pRoot->pRight);

}
}
int main()
{
int n;
int x;
cin >> n;
NODE* Tree = NULL;
for (int i = 0; i < n; i++)
{
cin >> x;
Insert(Tree, x);
}
LNR(Tree);
cout << endl;
cout << isBST(Tree);

return 0;
}

You might also like