赞
踩
使用补空法创建了一棵二叉树,并且实现了先序遍历、中序遍历、后序遍历、层次遍历功能。
1、定义结点类:
要创建二叉树首先要定义二叉树的结点类,二叉树上每一个结点有3个成员变量,一个存放当前结点的值,其余两个是指针类型,分别指向此节点的左孩子和右孩子;
- class Node
- {
- public:
- char data;
- Node* lchild; //指向左孩子
- Node* rchild; //指向右孩子
- };
-
- using Tree = Node*;
2、使用补空法创建二叉树
补空法是指:如果结点没有孩子,在写遍历序列时,在其孩子的位置补‘#’(也可是别的有特殊定义的字符)。
使用先序序列创建二叉树时,先判断字符是否为'#':如果是,说明此处没有结点,指针空指;如果不是,说明有结点,先动态创建一个新结点,给数据域赋值,然后递归创建左子树、递归创建右子树。
- void CreateTree(Tree& t)
- {
- char c;
- cin >> c;
- if (c == '#')
- {
- t = nullptr; //没有结点就空指
- }
- else //创建新结点
- {
- t = new Node;
- t->data = c;
- CreateTree(t->lchild);
- CreateTree(t->rchild);
- }
- }
3、先序遍历
非常简单,分为三步:打印当前结点数据、递归左孩子、递归右孩子(根左右)
递归前要确保左|右孩子存在(左|右孩子的指针不空)
- void DLR(const Tree& t)
- {
- cout << t->data << " ";
- if (t->lchild)
- {
- DLR(t->lchild);
- }
- if (t->rchild)
- {
- DLR(t->rchild);
- }
- }
4、中序遍历
(左根右)
- void LDR(const Tree& t)
- {
- if (t->lchild)
- {
- LDR(t->lchild);
- }
- cout << t->data << " ";
- if (t->rchild)
- {
- LDR(t->rchild);
- }
- }
5、后序遍历
(左右根)
- void LRD(const Tree& t)
- {
- if (t->lchild)
- {
- LRD(t->lchild);
- }
- if (t->rchild)
- {
- LRD(t->rchild);
- }
- cout << t->data << " ";
- }
6、层次遍历
层次遍历是从根开始按照辈分大小向下逐层输出,具有先来先服务特性,适合用队列
队列里存的是指向各个结点的指针,先把根节点的指针放进队列;若队列不空,取走并打印队头结点,然后此结点的左右孩子入队,循环遍历即可。
- void Gradation(const Tree& t)
- {
- queue<Node*> q; //存的是指针不是结点
- q.push(t); //先把树根的指针入队
- Node* temp = nullptr;
- while (!q.empty())
- {
- temp = q.front();
- q.pop();
- cout << temp->data << " ";
- if (temp->lchild)
- {
- q.push(temp->lchild);
- }
- if (temp->rchild)
- {
- q.push(temp->rchild);
- }
- }
- }
总体代码实现:
- #include <iostream>
- using namespace std;
- #include <queue>
-
- class Node
- {
- public:
- char data;
- Node* lchild; //指向左孩子
- Node* rchild; //指向右孩子
- };
-
- using Tree = Node*;
-
- void CreateTree(Tree& t)
- {
- char c;
- cin >> c;
- if (c == '#')
- {
- t = nullptr; //没有结点就空指
- }
- else //创建新结点
- {
- t = new Node;
- t->data = c;
- CreateTree(t->lchild);
- CreateTree(t->rchild);
- }
- }
-
- //先序遍历
- void DLR(const Tree& t)
- {
- cout << t->data << " ";
- if (t->lchild)
- {
- DLR(t->lchild);
- }
- if (t->rchild)
- {
- DLR(t->rchild);
- }
- }
-
- //中序遍历
- void LDR(const Tree& t)
- {
- if (t->lchild)
- {
- LDR(t->lchild);
- }
- cout << t->data << " ";
- if (t->rchild)
- {
- LDR(t->rchild);
- }
- }
-
- //后序遍历
- void LRD(const Tree& t)
- {
- if (t->lchild)
- {
- LRD(t->lchild);
- }
- if (t->rchild)
- {
- LRD(t->rchild);
- }
- cout << t->data << " ";
- }
-
- //层次遍历
- void Gradation(const Tree& t)
- {
- queue<Node*> q; //存的是指针不是结点
- q.push(t); //先把树根的指针入队
- Node* temp = nullptr;
- while (!q.empty())
- {
- temp = q.front();
- q.pop();
- cout << temp->data << " ";
- if (temp->lchild)
- {
- q.push(temp->lchild);
- }
- if (temp->rchild)
- {
- q.push(temp->rchild);
- }
- }
-
- }
-
- int main()
- {
- Tree my_tree;
- int choose = 0;
- cout << "请选择要执行的操作" << endl;
- cout << "1、创建二叉树" << endl;
- cout << "2、先序遍历" << endl;
- cout << "3、中序遍历" << endl;
- cout << "4、后序遍历" << endl;
- cout << "5、层次遍历" << endl;
- cout << "0、退出" << endl;
- while (cin >> choose)
- {
- switch (choose)
- {
- case 1:
- cout << "请输入要创建树的先序序列,结点没有孩子的位置用#代替:" << endl;
- CreateTree(my_tree);
- cout << endl;
- break;
- case 2:
- cout << "先序遍历:" << endl;
- DLR(my_tree);
- cout << endl;
- break;
- case 3:
- cout << "中序遍历:" << endl;
- LDR(my_tree);
- cout << endl;
- break;
- case 4:
- cout << "后序遍历:" << endl;
- LRD(my_tree);
- cout << endl;
- break;
- case 5:
- cout << "层次遍历:" << endl;
- Gradation(my_tree);
- cout << endl;
- break;
- case 0:
- cout << "Bye-Bye" << endl;
- return 0;
- default:
- break;
- }
- cout << "请输入下一个指令" << endl;
- }
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。