c++数据结构与算法
以中缀表达式创建表达式二叉树(递归算法)，以后根次序遍历计算表达式值。
使用类和对象，不使用结构体
二叉树类名称为BinaryTree
二叉结点类名称为BinaryNode
函数放在二叉树类内，做成头文件BinaryTree.h
结点类做成头文件BinaryNode.h
运行代码单独做源程序
需要添加运行代码即cpp
具体参考代码形式：
template
BinaryTree::BinaryTree(T postlist[], T inlist[], int n)
{
this->root = create(int list, postlist, n - 1, 0, n - 1);
}
template
BinaryNode* BinaryTree::create(T inlist[], T postlist[], int postEnd, int Start, int inEnd)
{
if (inStrat > inEnd) {
return NULL;
}
T x = postlist[inEnd];
BinaryNode* p = new TreeNode(x);
int m = 0; //在中根序列中的位置
for (int i = inStart; i <= inEnd; i++) {
if (x == inorder[i]) {
m = i;
}
}
int rightChildLength = inEnd - m; //右子树长度
p->right = create(inlist, postlist, postEnd - 1, m + 1, inEnd); //先根序列左移1位是右子树根节点
p->left = create(inlist, postlist, postEnd - 1 - rightChildLength, inStart, m - 1);//先跟序列左移右子树长度+1是左子树根节点
return p;
}
好。下午给你找一个
这代码不就套模板,还有抄和不抄的区别?
#include<stdio.h>
#include<stdlib.h>
/*定义树的结点结构*/
typedef struct TreeNode {
char data;/*树中结点的数据是一个字符*/
struct TreeNode* lchild;
struct TreeNode* rchild;
}TREENODE;
int NodeNum = 0;/*统计数的结点数*/
int LeafNum = 0;/*统计数的叶子结点数*/
char ch[] = { 'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' ' };
int inc = 0;
/*建立一颗二叉树*/
int CreateBiTree(TREENODE** T)
/*按先序次序输入二叉树中结点的值,以空字符表示空树*/
{
if (ch[inc++] == ' ')
*T = NULL;
else
{
printf("%c\n", ch[inc - 1]);
if (!(*T = (TREENODE*)malloc(sizeof(TREENODE))))
return -1;
(*T)->data = ch[inc - 1];
printf("%c\n", (*T)->data);
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
return 1;
}
/*先序遍历二叉树*/
int PreOderTraverse(TREENODE* T)
{
if (T)
{
printf("%c ", T->data);
PreOderTraverse(T->lchild);
PreOderTraverse(T->rchild);
}
return 1;
}
/* 中序遍历二叉树*/
int InOderTraverse(TREENODE* T)
{
if (T)
{
InOderTraverse(T->lchild);
printf("%c ", T->data);
InOderTraverse(T->rchild);
}
return 1;
}
/* 后序遍历二叉树*/
int BackOderTraverse(TREENODE* T)
{
if (T)
{
BackOderTraverse(T->lchild);
BackOderTraverse(T->rchild);
printf("%c ", T->data);
}
return 1;
}
/*利用先序遍历来计算树中的结点数*/
void CountNodeNum(TREENODE* T)
{
if (T)
{
NodeNum++;
CountNodeNum(T->lchild);
CountNodeNum(T->rchild);
}
}
/*利用先序遍历计算叶子节点数*/
void CountLeafNum(TREENODE* T)
{
if (T)
{
if ((!(T->lchild)) && (!(T->rchild)))
LeafNum++;
CountLeafNum(T->lchild);
CountLeafNum(T->rchild);
}
}
int main()
{
TREENODE* T;
int i;
CreateBiTree(&T);
do
{
puts("**************************************************");
puts("* 你可以选择: *");
puts("* 1: 按预定顺序遍历二叉树 *");
puts("* 2: 按中序遍历二叉树 *");
puts("* 3: 通过回溯顺序遍历二叉树 *");
puts("* 4: 计算二叉树的节点数 *");
puts("* 5: 计算二叉树的叶子节点数 *");
puts("**************************************************");
puts("请输入您的选择:");
scanf_s("%d", &i);
switch (i)
{
case 1:
PreOderTraverse(T);
break;
case 2:
InOderTraverse(T);
break;
case 3:
BackOderTraverse(T);
break;
case 4:
CountNodeNum(T);
printf("节点数: %d", NodeNum);
break;
case 5:
CountLeafNum(T);
printf("叶子节点数: %d", LeafNum);
break;
}
} while ((i >= 1) && (i < 6));
return 0;
}
node.h
#ifndef BINARYNODE_H
#define BINARYNODE_H
class BinaryNode
{
public:
BinaryNode(int data,BinaryNode *left,BinaryNode*right,BinaryNode *parent);
int getData();
BinaryNode *getLeftNode();
BinaryNode *getRightNode();
BinaryNode *getParentNode();
void setLeftNode(BinaryNode *left);
void setRightNode(BinaryNode *right);
void setParentNode(BinaryNode *parent);
private:
int m_data;
BinaryNode *m_pleft;
BinaryNode *m_pright;
BinaryNode *m_pparent;
};
#endif // BINARYNODE_H
node.cpp
#include "binarynode.h"
BinaryNode::BinaryNode(int data, BinaryNode *left, BinaryNode *right, BinaryNode *parent)
{
m_data=data;
m_pleft=left;
m_pright=right;
m_pparent=parent;
}
int BinaryNode::getData()
{
return m_data;
}
BinaryNode *BinaryNode::getLeftNode()
{
return m_pleft;
}
BinaryNode *BinaryNode::getRightNode()
{
return m_pright;
}
BinaryNode *BinaryNode::getParentNode()
{
return m_pparent;
}
void BinaryNode::setLeftNode(BinaryNode *left)
{
m_pleft=left;
}
void BinaryNode::setRightNode(BinaryNode *right)
{
m_pright=right;
}
void BinaryNode::setParentNode(BinaryNode *parent)
{
m_pparent=parent;
}
tree用于创建node
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include "binarynode.h"
#include <iostream>
class BinaryTree
{
public:
BinaryTree();
void middle_order(BinaryNode *Node);
};
#endif // BINARYTREE_H
tree.cpp
#include "binarytree.h"
#include "binarynode.h"
#include <iostream>
using namespace std;
BinaryTree::BinaryTree()
{
BinaryNode *rootNode=new BinaryNode(1,nullptr,nullptr,nullptr);
BinaryNode *leftNode=new BinaryNode(2,nullptr,nullptr,nullptr);
BinaryNode *rightNode=new BinaryNode(3,nullptr,nullptr,nullptr);
rootNode->setLeftNode(leftNode);
rootNode->setRightNode(rightNode);
//遍历
middle_order(rootNode);
}
void BinaryTree::middle_order(BinaryNode *Node)
{
if(Node != nullptr) {
middle_order(Node->getLeftNode());
cout<<"data = "<<Node->getData();
middle_order(Node->getRightNode());
}
}
main.cpp
#include <QCoreApplication>
#include "binarytree.h"
int main()
{
BinaryTree tree
return 0;
}
/*************************************************************************
> File Name: tree.cpp
> Author: ltf
> Created Time: Fri 25 Mar 2016 09:33:46 AM CST
************************************************************************/
#include
#include
#include
using namespace std;
typedef struct Tree
{
char value;
Tree *left;
Tree *right;
}*pTree;
typedef struct TNode
{
Tree *ptr;
int tag;
}*pTNode;
stack<Tree >opN;
stack opC;
// 辅助函数，返回栈中的操作符的优先级0~6，为了保证从左到右的计算顺序，同一操作符栈内优先级比栈外高1
int isp(char c)
{
int re= 0;
switch(c)
{
case '+':
case '-':
re = 3;
break;
case '':
case '/':
case '%':
re = 5;
break;
case '(':
re = 1;
break;
case ')':
re = 6;
break;
case '#':
re = 0;
break;
}
return re;
}
// 返回操作符在栈外的优先级
int osp(char c)
{
int re= 0;
switch(c)
{
case '+':
case '-':
re = 2;
break;
case '*':
case '/':
case '%':
re = 4;
break;
case '(':
re = 6;
break;
case ')':
re = 1;
break;
case '#':
re = 0;
break;
}
return re;
}
// 递归模式遍历二叉树，根据flag不同，输出不同的序列
void print(Tree *tree,int flag)
{
if(tree != NULL)
{
if(flag == 0)
cout << tree->value;
print(tree->left,flag);
if(flag == 1)
cout << tree->value;
print(tree->right,flag);
if(flag == 2)
cout << tree->value;
}
}
// 释放掉树节点内存块
void freeTree(Tree *tree)
{
if(tree == NULL)
return;
freeTree(tree->left);
freeTree(tree->right);
delete tree;
}
/*
中缀表达式生成二叉树，利用两个栈实现
1、如果输入的是操作数，则直接进栈
2、如果输入为操作符
1）若操作符优先级大于当前栈顶操作符，则进栈
2）若当前操作符优先级小于栈顶优先级，则以栈顶操作符为根构建子树
3）若优先级相等，则直接退出栈顶元素，重新读入字符
*/
void generateTree()
{
char c;
opC.push('#'); // 当输入'#'时，栈可以变为空
cin.get(c);
while(opC.empty() == false)
{
char top = opC.top();
if(isdigit(c))
{
Tree *temp = new Tree();
temp->value = c;
temp->left = NULL;
temp->right = NULL;
opN.push(temp);
cin.get(c);
}
else if(osp(c) > isp(top))
{
opC.push(c);
cin.get(c);
}
else if(osp(c) < isp(top))
{
Tree *root = new Tree();
root->value = opC.top();
opC.pop();
Tree *right = opN.top();
opN.pop();
Tree left = opN.top();
opN.pop();
root->left = left;
root->right = right;
opN.push(root);
}
else
{
opC.pop();
if(c == ')')
cin.get(c);
}
}
}
/
非递归先序遍历，首先访问元素值，然后将右子树压入栈，再将左子树压入栈
*/
void preOrder(Tree *root)
{
stack S;
S.push(root);
while(!S.empty())
{
Tree *tree = S.top();
S.pop();
cout << tree->value;
if(tree->right !=NULL) S.push(tree->right);
if(tree->left !=NULL) S.push(tree->left);
}
cout << endl;
}
/*
非递归中序遍历，
1、首先一直往左走，直到左子树为空
2、然后访问当前元素，回溯一格，以右子树作为子树的根，进入步骤1
直到栈为空结束循环
*/
void inOrder(Tree *root)
{
stack S;
Tree *p;
p = root;
do{
while(p!=NULL)
{
S.push(p);
p = p->left;
}
if(S.empty() == false)
{
p = S.top();
S.pop();
cout << p->value;
p = p->right;
}
}while(p != NULL || !S.empty());
cout << endl;
}
/*非递归统一遍历模型
由于后序遍历需要记住经历的状态，因此将每个节点分为3个状态，类似转移方式
状态为0：刚进入该节点，未访问左右子树
状态为1：该节点的左子树已经遍历
状态为2：该节点左右子树都已经遍历，出栈
*/
void printOrder(Tree *root, int flag)
{
stack S;
TNode node;
node.tag = 0;
node.ptr = root;
S.push(node);
while(!S.empty())
{
switch(S.top().tag)
{
case 0: //left child
S.top().tag = 1;
if(flag == 0)
cout << S.top().ptr->value;
if(S.top().ptr->left != NULL)
{
node.tag = 0;
node.ptr = S.top().ptr->left;
S.push(node);
}
break;
case 1: //right child
S.top().tag = 2;
if(flag == 1)
cout << S.top().ptr->value;
if(S.top().ptr->right != NULL)
{
node.tag = 0;
node.ptr = S.top().ptr->right;
S.push(node);
}
break;
case 2: //pop after l&r search
if(flag == 2)
cout << S.top().ptr->value;
S.pop();
break;
}
}
cout << endl;
}
int main()
{
generateTree();
cout << "Recursive Order" << endl;
print(opN.top(),0);
cout << endl;
print(opN.top(),1);
cout << endl;
print(opN.top(),2);
cout << endl;
cout << "Non-recursive Order" << endl;
printOrder(opN.top(),0);
printOrder(opN.top(),1);
printOrder(opN.top(),2);
cout << "PreOrder" << endl;
preOrder(opN.top());
cout << "InOrder" << endl;
inOrder(opN.top());
freeTree(opN.top());
}
给你个例子参考
#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
typedef struct Tree
{
char value;
Tree *left;
Tree *right;
}*pTree;
typedef struct TNode
{
Tree *ptr;
int tag;
}*pTNode;
stack<Tree *>opN;
stack<char> opC;
// 辅助函数，返回栈中的操作符的优先级0~6，为了保证从左到右的计算顺序，同一操作符栈内优先级比栈外高1
int isp(char c)
{
int re= 0;
switch(c)
{
case '+':
case '-':
re = 3;
break;
case '*':
case '/':
case '%':
re = 5;
break;
case '(':
re = 1;
break;
case ')':
re = 6;
break;
case '#':
re = 0;
break;
}
return re;
}
// 返回操作符在栈外的优先级
int osp(char c)
{
int re= 0;
switch(c)
{
case '+':
case '-':
re = 2;
break;
case '*':
case '/':
case '%':
re = 4;
break;
case '(':
re = 6;
break;
case ')':
re = 1;
break;
case '#':
re = 0;
break;
}
return re;
}
// 递归模式遍历二叉树，根据flag不同，输出不同的序列
void print(Tree *tree,int flag)
{
if(tree != NULL)
{
if(flag == 0)
cout << tree->value;
print(tree->left,flag);
if(flag == 1)
cout << tree->value;
print(tree->right,flag);
if(flag == 2)
cout << tree->value;
}
}
// 释放掉树节点内存块
void freeTree(Tree *tree)
{
if(tree == NULL)
return;
freeTree(tree->left);
freeTree(tree->right);
delete tree;
}
/*
中缀表达式生成二叉树，利用两个栈实现
1、如果输入的是操作数，则直接进栈
2、如果输入为操作符
1）若操作符优先级大于当前栈顶操作符，则进栈
2）若当前操作符优先级小于栈顶优先级，则以栈顶操作符为根构建子树
3）若优先级相等，则直接退出栈顶元素，重新读入字符
*/
void generateTree()
{
char c;
opC.push('#'); // 当输入'#'时，栈可以变为空
cin.get(c);
while(opC.empty() == false)
{
char top = opC.top();
if(isdigit(c))
{
Tree *temp = new Tree();
temp->value = c;
temp->left = NULL;
temp->right = NULL;
opN.push(temp);
cin.get(c);
}
else if(osp(c) > isp(top))
{
opC.push(c);
cin.get(c);
}
else if(osp(c) < isp(top))
{
Tree *root = new Tree();
root->value = opC.top();
opC.pop();
Tree *right = opN.top();
opN.pop();
Tree *left = opN.top();
opN.pop();
root->left = left;
root->right = right;
opN.push(root);
}
else
{
opC.pop();
if(c == ')')
cin.get(c);
}
}
}
/*
非递归先序遍历，首先访问元素值，然后将右子树压入栈，再将左子树压入栈
*/
void preOrder(Tree *root)
{
stack<pTree> S;
S.push(root);
while(!S.empty())
{
Tree *tree = S.top();
S.pop();
cout << tree->value;
if(tree->right !=NULL) S.push(tree->right);
if(tree->left !=NULL) S.push(tree->left);
}
cout << endl;
}
/*
非递归中序遍历，
1、首先一直往左走，直到左子树为空
2、然后访问当前元素，回溯一格，以右子树作为子树的根，进入步骤1
直到栈为空结束循环
*/
void inOrder(Tree *root)
{
stack<pTree> S;
Tree *p;
p = root;
do{
while(p!=NULL)
{
S.push(p);
p = p->left;
}
if(S.empty() == false)
{
p = S.top();
S.pop();
cout << p->value;
p = p->right;
}
}while(p != NULL || !S.empty());
cout << endl;
}
/*非递归统一遍历模型
由于后序遍历需要记住经历的状态，因此将每个节点分为3个状态，类似转移方式
状态为0：刚进入该节点，未访问左右子树
状态为1：该节点的左子树已经遍历
状态为2：该节点左右子树都已经遍历，出栈
*/
void printOrder(Tree *root, int flag)
{
stack<TNode> S;
TNode node;
node.tag = 0;
node.ptr = root;
S.push(node);
while(!S.empty())
{
switch(S.top().tag)
{
case 0: //left child
S.top().tag = 1;
if(flag == 0)
cout << S.top().ptr->value;
if(S.top().ptr->left != NULL)
{
node.tag = 0;
node.ptr = S.top().ptr->left;
S.push(node);
}
break;
case 1: //right child
S.top().tag = 2;
if(flag == 1)
cout << S.top().ptr->value;
if(S.top().ptr->right != NULL)
{
node.tag = 0;
node.ptr = S.top().ptr->right;
S.push(node);
}
break;
case 2: //pop after l&r search
if(flag == 2)
cout << S.top().ptr->value;
S.pop();
break;
}
}
cout << endl;
}
int main()
{
generateTree();
cout << "Recursive Order" << endl;
print(opN.top(),0);
cout << endl;
print(opN.top(),1);
cout << endl;
print(opN.top(),2);
cout << endl;
cout << "Non-recursive Order" << endl;
printOrder(opN.top(),0);
printOrder(opN.top(),1);
printOrder(opN.top(),2);
cout << "PreOrder" << endl;
preOrder(opN.top());
cout << "InOrder" << endl;
inOrder(opN.top());
freeTree(opN.top());
}
C++的熟悉，不过建议，可以通过调试手段一步步执行代码来验证代码的正确性
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
/*---------------------------二叉树的链式存储-----------------------*/
typedef struct BiTNode
{
char data; //结点数据域（符号）
string combine_data; //结点数据域（数值，可大于9）
BiTNode *lchild, *rchild; //左右孩子指针
}*BiTree;
/*------------------------------链式堆栈---------------------------*/
typedef struct StackNode
{
BiTree data_tree; //存储的是二叉树
char data_op; //存储的是符号
StackNode *next;
}*LinkStack;
//栈的初始化
int InitStack(LinkStack &S)
{
S = NULL;
return 1;
}
//二叉树入栈
int Push_tree(LinkStack &S, BiTree e)
{
LinkStack p = new StackNode;
p->data_tree = e;
p->next = S;
S = p;
return 1;
}
//字符（运算符号）入栈
int Push_op(LinkStack &S, char e)
{
LinkStack p = new StackNode;
p->data_op = e;
p->next = S;
S = p;
return 1;
}
//二叉树出栈
int Pop_tree(LinkStack &S, BiTree &T1)
{
if (S == NULL) return 0;
LinkStack p = S;
T1 = p->data_tree;
S = S->next;
delete p;
return 1;
}
//字符（运算符号）出栈
int Pop_op(LinkStack &S, char &ch)
{
if (S == NULL) return 0;
LinkStack p = S;
ch = p->data_op;
S = S->next;
delete p;
return 1;
}
//取栈顶元素
char GetTop_op(LinkStack S)
{
if (S != NULL) return S->data_op;
else return ' ';
}
BiTree GetTop_tree(LinkStack S)
{
if (S != NULL) return S->data_tree;
else return NULL;
}
/*------------------------------表达式树的创建算法------------------------------*/
//创建以T为根结点的二叉树（存储符号）
void CreateExpTree(BiTree &T, BiTree a, BiTree b, char theta)//a是左孩子，b是右孩子,theta是数据域
{
BiTree L = new BiTNode;
L->data = theta;
L->lchild = a;
L->rchild = b;
T = L;
}
//创建以T为根结点的二叉树（存储数值，可大于9）
//a是左孩子，b是右孩子,theta是数据域
void CreateExpTree_str(BiTree &T, BiTree a, BiTree b, string theta)
{
BiTree L = new BiTNode;
L->combine_data = theta;
L->lchild = a;
L->rchild = b;
T = L;
}
//比较运算符的优先级
//top是栈顶元素，ch是需要比较的元素
char Precede(char top, char ch)
{
if (ch == ')'&&top == '(') return '=';
else if (ch == ')') return '>';
if (top == ' ' || top == '(' || ch == '(') return '<';
if (ch == '#') return '>';
if (top == '+' || top == '-') {
if (ch == '+' || ch == '-') return '>';
else if (ch == '/' || ch == '*') return '<';
}
else if (top == '*' || top == '/') return '>';
}
//创建表达式树
//expt栈(根结点)，optr栈(运算符)
void InitExpTree(char ep[], LinkStack &expt, LinkStack &optr)
{
int n = strlen(ep);
int i = 0;
BiTree T = NULL; //树根
BiTree T1 = NULL; //左子树
BiTree T2 = NULL; //右子树
char ch = ' '; //弹出的符号
string combine_str = ""; //存储数值，可大于9
while (i != n)
{
if (ep[i] >= '0' && ep[i] <= '9') { //数值（二叉树），进入expt栈中
combine_str += ep[i];
if (ep[i + 1] >= '0' && ep[i + 1] <= '9') { //下一位仍是数字，需连接
i++;
continue;
}
CreateExpTree_str(T, NULL, NULL, combine_str);
combine_str = ""; //建完数值的二叉树后string要置空
Push_tree(expt, T);
i++;
}
else {
switch (Precede(GetTop_op(optr),ep[i])) //比较优先级
{
case '<':
Push_op(optr, ep[i]);
i++;
break;
case '>':
Pop_op(optr, ch); //弹出上一个字符
Pop_tree(expt, T1); //弹出上两个数值（二叉树）
Pop_tree(expt, T2);
CreateExpTree(T, T2, T1, ch); //以data_tree为根，连接T1和T2两颗子树
Push_tree(expt, T); //最后把T放进expt栈中
break;
case '=':
Pop_op(optr, ch);
i++;
break;
default:
break;
}
}
}
}
//表达式树的后序遍历
void PostOrder(BiTree T)
{
if (T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
if (T->lchild == NULL&&T->rchild == NULL) {
cout << T->combine_data << " ";
}
else cout << T->data << " ";
}
}
/*-----------------------------表达式树的求值-------------------------------*/
//根据当前结点运算符的例子那个进行相应运算
double GetValue(char data, double lvalue, double rvalue)
{
switch (data)
{
case '+':
return lvalue + rvalue;
break;
case '-':
return lvalue - rvalue;
break;
case '*':
return lvalue * rvalue;
break;
case '/':
return lvalue / rvalue;
break;
default:
break;
}
}
//把string字符转换成数值
double change(string str)
{
int n = str.length(), m = str.length();
double sum = 0;
for (int i = 0; i < n; i++)
{
sum += (str[i] - '0') * pow(10, m - 1);
m--;
}
return sum;
}
//遍历表达式树求表达式的值
double EvaluateExpTree(BiTree T)
{
double lvalue =0, rvalue = 0; //存放叶子结点的数据域初始为0
if (T->lchild == NULL&&T->rchild == NULL)
return change(T->combine_data); //return T->data - '0';
else {
lvalue = EvaluateExpTree(T->lchild); //相当于后序遍历二叉树
rvalue = EvaluateExpTree(T->rchild);
return GetValue(T->data, lvalue, rvalue);
}
}
int main()
{
LinkStack expt;
InitStack(expt); //初始化expt栈(根结点)
LinkStack optr;
InitStack(optr); //初始化optr栈(运算符)
char ep[] = "3+4*(6-1)-8/2#"; //"(18-2)*(13-7)+4/2#";
InitExpTree(ep, expt, optr); //构建表达式树
BiTree T = NULL;
Pop_tree(expt, T); //获取最后建好的二叉树
cout << "初始的中缀表达式: " << ep << endl; //初始中缀表达式
cout << "后序遍历: ";
PostOrder(T); //后序遍历结果
cout << endl;
cout << "表达式求值后的结果: " << EvaluateExpTree(T) << endl; //表达式树求值结果
return 0;
}