C ++程序使用链接列表实现二进制搜索树
这是一个使用链接列表实现二进制搜索树的C++程序。
函数和伪代码
算法
Begin
Take the nodes of the tree as input.
Create a structure nod to take the data d, a left pointer l and a right r as input.
Create a function create() to insert nodes into the tree:
Initialize c = 0 as number of nodes.
Perform while loop till c < 6:
Enter the root.
Enter the value of the node, if it is greater than root then entered as right otherwise left.
Create a function inorder() to traverse the node as inorder as:
Left – Root – Right.
Create a function preorder() to traverse the node as preorder as:
Root – Left – Right.
Create a function postorder() to traverse the node as preorder as:
Left – Right – Root
From main(), call the functions and print the result.
End范例程式码
#include <iostream>
using namespace std;
struct nod {
nod *l, *r;
int d;
}*r = NULL, *p = NULL, *np = NULL, *q;
void create() {
int v,c = 0;
while (c < 6) {
if (r == NULL) {
r = new nod;
cout<<"enter value of root node\n";
cin>>r->d;
r->r = NULL;
r->l = NULL;
} else {
p = r;
cout<<"enter value of node\n";
cin>>v;
while(true) {
if (v< p->d) {
if (p->l == NULL) {
p->l = new nod;
p = p->l;
p->d = v;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left\n";
break;
} else if (p->l != NULL) {
p = p->l;
}
} else if (v >p->d) {
if (p->r == NULL) {
p->r = new nod;
p = p->r;
p->d = v;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right\n";
break;
} else if (p->r != NULL) {
p = p->r;
}
}
}
}
c++;
}
}
void inorder(nod *p) {
if (p != NULL) {
inorder(p->l);
cout<<p->d<<endl;
inorder(p->r);
}
}
void preorder(nod *p) {
if (p != NULL) {
cout<<p->d<<endl;
preorder(p->l);
preorder(p->r);
}
}
void postorder(nod *p) {
if (p != NULL) {
postorder(p->l);
postorder(p->r);
cout<<p->d<<endl;
}
}
int main() {
create();
cout<<" traversal in inorder\n";
inorder(r);
cout<<" traversal in preorder\n";
preorder(r);
cout<<" traversal in postorder\n";
postorder(r);
}输出结果
enter value of root node 7 enter value of node 6 value entered in left enter value of node 4 value entered in left enter value of node 3 value entered in left enter value of node 2 value entered in left enter value of node 1 value entered in left traversal in inorder 1 2 3 4 6 7 traversal in preorder 7 6 4 3 2 1 traversal in postorder 1 2 3 4 6 7