数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究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 << "Print 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 Print 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
更新于: 30-07-2019
154 次查看
广告