C ++程序实现二叉树的双阶遍历
这是一个C++程序，用于实现二叉树的双阶遍历。
在“双顺序遍历”中，子树的根将遍历两次。
算法
Begin
class BST has following functions:
insert() = to insert items in the tree:
Enter the root.
Enter the value of the node, if it is greater than root then entered as right otherwise left.
doubleOrder() = To perform inorder:
If root = null
Print tree is empty
Otherwise perform:
Visit root of (sub)tree.
Visit left sub-tree.
Revisit root of (sub)tree.
Visit right sub-tree.
End范例程式码
# include <iostream>
# include <cstdlib>
using namespace std;
struct nod//node declaration {
int info;
struct nod *l;
struct nod *r;
}*r;
class BST {
public://declaration of functions
void insert(nod *, nod *);
void doubleOrder(nod *);
void show(nod *, int);
BST() {
r = NULL;
}
};
void BST::insert(nod *tree, nod *newnode) {
if (r == NULL) {
r = new nod;
r->info = newnode->info;
r->l = NULL;
r->r = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info) {
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info >newnode->info) {
if (tree->l != NULL) {
insert(tree->l, newnode);
} else {
tree->l= newnode;
(tree->l)->l = NULL;
(tree->l)->r= NULL;
cout<<"Node Added To Left"<<endl;
return;
}
} else {
if (tree->r != NULL) {
insert(tree->r, newnode);
} else {
tree->r = newnode;
(tree->r)->l= NULL;
(tree->r)->r = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BST::doubleOrder(nod *ptr) {
if (r == NULL) {
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL) {
cout << ptr->info << " ";
doubleOrder(ptr->l);
cout << ptr->info << " ";
doubleOrder(ptr->r);
}
}
void BST::show(nod *ptr, int level)// print the tree {
int i;
if (ptr != NULL) {
show(ptr->r, level + 1);
cout << endl;
if (ptr == r)
cout << "Root->: ";
else {
for (i = 0; i < level; i++)
cout << " ";
}
cout << ptr->info;
show(ptr->l, level + 1);
}
}
int main() {
int c, n;
BST bst;
nod *t;
while (1)//perform switch operation {
cout << "1.Insert Element " << endl;
cout << "2.Double-Order Traversal" << endl;
cout << "3.Show" << endl;
cout << "4.Quit" << endl;
cout << "Enter your choice : ";
cin >>c;
switch (c)//perform switch operation {
case 1:
t = new nod;
cout << "Enter the number to be inserted : ";
cin >>t->info;
bst.insert(r, t);
break;
case 2:
cout << "Double-Order Traversal of BST:" << endl;
bst.doubleOrder(r);
cout << endl;
break;
case 3:
cout << "打印BST：" << endl;
bst.show(r, 1);
cout << endl;
break;
case 4:
exit(1);
default:
cout << "Wrong choice" << endl;
}
}
}输出结果
1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 7 Root Node is Added 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 6 Node Added To Left 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 4 Node Added To Left 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 2 Node Added To Left 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 1 Enter the number to be inserted : 10 Node Added To Right 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 3 打印BST： 10 Root->: 7 6 4 2 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 2 Double-Order Traversal of BST: 7 6 4 2 2 4 6 7 10 10 1.Insert Element 2.Double-Order Traversal 3.Show 4.Quit Enter your choice : 4