c++树的相关操作

用c++实现树的相关操作

今天总算是完成了二叉树的基本操作,在这留个底,方便自己以后需要的时候看一下. 基本操作包括:

创建二叉树先根遍历后根遍历中根遍历删除树非递归中根遍历非递归后根遍历非递归先根遍历层次遍历表达式求值复制二叉树查找指定值的节点查找父节点插入节点(作为左儿子)删除节点创建表达式树 #include<iostream> #include<stack> #include<queue> using namespace std; struct TNode { char data; TNode* Left,* Right; }; struct TNodeInt { TNode* p; int i; TNodeInt(TNode* p0, int i0) :i(i0), p(p0) {} }; class Tree { public: Tree(char item) { root = Create_Expression_Tree(); } Tree() { root = Create(root); } Tree(TNode* bt) { root = CopyTree(bt); } ~Tree() { Del(root); } void PreOrder() { PreOrder(root); } //前序遍历 void PostOrder() { PostOrder(root); } //后序遍历 void InOrder() { InOrder(root); } //中序遍历 void NorecInOrder() { NorecInOrder(root); }//非递归中根遍历 void NorecPostOrder() { NorecPostOrder(root); } //非递归后根遍历 void NorecPreOrder() { NorecPreOrder(root); } //非递归先根遍历 void LevelOrder() { LevelOrder(root); } //层次遍历 void GetValue() { GetValue(root); } //表达式求值 // TNode* CopyTree() { return CopyTree(root); } //复制二叉树 //private: TNode* root; void Del(TNode* bt); //删除树 void PreOrder(TNode* bt); void InOrder(TNode* bt); void PostOrder(TNode* bt); void NorecPostOrder(TNode* bt); void NorecInOrder(TNode* bt); void NorecPreOrder(TNode* bt); void LevelOrder(TNode* bt); TNode* Create(TNode* bt); TNode* CopyTree(TNode* bt); //复制二叉树 TNode* Find(TNode* bt, char item); //查找指定值的节点 TNode* Father(TNode* bt, TNode* p); //找父节点 void InsertLL(TNode* p, TNode* s); //插入节点,作为左儿子,如果原来有左儿子,原左儿子作为插入节点的左儿子 void DelSubTree(TNode* bt); //删除节点 TNode* Create_Expression_Tree(); void GetValue(TNode* bt,int value=0); };

1.创建二叉树

TNode* Tree::Create(TNode* bt) { char ch; cin >> ch; if (ch == '#') bt = NULL; else { bt = new TNode; bt->data = ch; bt->Left = Create(bt->Left); bt->Right = Create(bt->Right); } return bt; }

2.先根遍历

void Tree::PreOrder(TNode* bt) { if (bt == NULL) { return; } else { cout << bt->data << " "; PreOrder(bt->Left); PreOrder(bt->Right); } }

3.中根遍历

void Tree::InOrder(TNode* bt) { if (bt == NULL) return; else { InOrder(bt->Left); cout << bt->data << " "; InOrder(bt->Right); } }

4.后根遍历

void Tree::PostOrder(TNode* bt) { if (bt == NULL) return; else { PostOrder(bt->Left); PostOrder(bt->Right); cout << bt->data << " "; } }

5.删除树

void Tree::Del(TNode* bt) { if (bt == NULL) return; else { Del(bt->Left); Del(bt->Right); delete bt; } }

6.非递归中根遍历

void Tree::NorecInOrder(TNode* bt) { stack<TNode*> S; TNode* p = bt; while (p||!S.empty()) { while (p != NULL) { S.push(p); p = p->Left; } if (S.empty()) return; else { p = S.top(); S.pop(); cout << p->data << " "; p = p->Right; } } }

7.递归后根遍历

void Tree::NorecPostOrder(TNode* bt) { if (bt == NULL) return; stack<TNodeInt> S; TNodeInt k(bt, 0); S.push(k); while (!S.empty()) { TNodeInt p = S.top(); S.pop(); if (p.i == 0) { p.i = 1; S.push(p); if (p.p->Left != NULL) { TNodeInt temp0(p.p->Left, 0); S.push(temp0); } } else if (p.i == 1) { p.i = 2; S.push(p); if (p.p->Right != NULL) { TNodeInt temp1(p.p->Right, 0); S.push(temp1); } } else if (p.i == 2) { cout << p.p->data << " "; } } }

8.递归先根遍历

void Tree::NorecPreOrder(TNode* bt) { stack<TNode*> S; TNode* p = bt; while (p || !S.empty()) { while (p != NULL) { S.push(p); cout << p->data << " "; p = p->Left; } if (S.empty()) return; else { // cout << "*size:" << S.size() << "*" << endl; p = S.top(); // cout << "***" << p->data << "*** "; S.pop(); p = p->Right; } } cout << endl; }

9.层次遍历

void Tree::LevelOrder(TNode* bt) { queue<TNode*> Q; TNode* p = bt; if (p != NULL) Q.push(p); while (!Q.empty()) { p = Q.front(); Q.pop(); cout << p->data << " "; if (p->Left != NULL) Q.push(p->Left); if (p->Right != NULL) Q.push(p->Right); } }

10.表达式求值

void Tree::GetValue(TNode* bt,int value) //利用辅助堆栈S求表达式的值,利用堆栈calculator存放操作数和计算结果 { if (bt == NULL) return ; stack<TNodeInt> S; stack<char> calculator; TNodeInt k(bt, 0); S.push(k); int result = 0; char resultc; while (!S.empty()) { TNodeInt p = S.top(); S.pop(); if (p.i == 0) { p.i = 1; S.push(p); if (p.p->Left != NULL) { // cout << "0: " << S.top().p->data << endl; // cout << "***********" << endl; // cout << p.p->Left->data << endl; // cout << "***********" << endl; TNodeInt temp0(p.p->Left, 0); S.push(temp0); } } else if (p.i == 1) { p.i = 2; S.push(p); if (p.p->Right != NULL) { // cout << "1: " << S.top().p->data << endl; // cout << "***********" << endl; // cout << p.p->Right->data << endl; // cout << "***********" << endl; TNodeInt temp1(p.p->Right, 0); S.push(temp1); } } else if (p.i == 2) { if (p.p->Left == NULL || p.p->Right == NULL) calculator.push(p.p->data); else { char operand2 = calculator.top(); calculator.pop(); char operand1 = calculator.top(); calculator.pop(); char op = p.p->data; if (op == '+') { int oprand1 = operand1 - '0',oprand2 = operand2 - '0'; result = oprand1 + oprand2; resultc = result + '0'; } if (op == '-') { int oprand1 = operand1 - '0', oprand2 = operand2 - '0'; result = oprand1 - oprand2; resultc = result + '0'; } if (op == '*') { int oprand1 = operand1 - '0', oprand2 = operand2 - '0'; result = oprand1 * oprand2; resultc = result + '0'; } if (op == '/') { int oprand1 = operand1 - '0', oprand2 = operand2 - '0'; if(oprand2 != 0) result = oprand1 / oprand2; resultc = result + '0'; } calculator.push(resultc); } } } value = calculator.top() - '0'; cout << "表达式的值为: " << value << endl; }

11.复制二叉树

TNode* Tree::CopyTree(TNode* bt) { TNode* p= new TNode, * newlp = NULL, * newrp = NULL; if (bt == NULL) { p = NULL; return NULL; } if (bt->Left != NULL) newlp = CopyTree(bt->Left); else newlp = NULL; if (bt->Right != NULL) newrp = CopyTree(bt->Right); else newrp = NULL; p->data = bt->data; p->Left = newlp; p->Right = newrp; return p; }

12.查找指定值的节点

TNode* Tree::Find(TNode* bt,char item) { TNode* q = NULL; if (bt == NULL) return bt; if (bt->data == item) return bt; if ((q = Find(bt->Left, item)) != NULL) return q; else return Find(bt->Right, item); }

13.查找父节点

TNode* Tree::Father(TNode* bt, TNode* p) { TNode* q; if (bt == NULL || p == NULL || p == bt) { q = NULL; return NULL; } if (bt->Left == p || bt->Right == p) return bt; if ((q = Father(bt->Left, p)) != NULL) return q; else return Father(bt->Right, p); }

14.插入节点(作为左儿子)

void Tree::InsertLL(TNode* p, TNode* s) { if (s == NULL || p == NULL) return ; p->Left = s->Left; s->Left = p; }

15.删除节点

void Tree::DelSubTree(TNode* bt) { if (bt == NULL) return; if (bt == root) { Del(bt); root = NULL; return; } TNode* p = bt,*q = Father(root,p); if (q->Left == p) q->Left = NULL; if (q->Right == p) q->Right = NULL; Del(p); }

16.创建表达式树

TNode* Tree::Create_Expression_Tree() { cout << "请输入你想输入的表达式: " << endl; stack<TNode*> S; char op; cin >> op; // int i = 0,j =0; while (op != '#') { if (op == '+' || op == '-' || op == '*' || op == '/') { // i++; // cout << i << endl; TNode* lpr = NULL, * rpr = NULL; rpr = S.top(); S.pop(); lpr = S.top(); S.pop(); TNode* p = new TNode; p->data = op; p->Left = lpr; p->Right = rpr; S.push(p); } else { // j++; // cout << j << endl; TNode* p = new TNode; p->data = op; p->Left = NULL; p->Right = NULL; S.push(p); } cin >> op; } TNode* root = S.top(); S.pop(); return root; }

主函数

int main() { Tree t3('#'); cout << "InOrder: " << endl; t3.InOrder(); cout << endl; t3.GetValue(); return 0; // Tree t1; // cout << "PostOrder: " << endl; // t1.PostOrder(); // cout << endl; // cout << "t1层次遍历: " << endl; // t1.LevelOrder(); // cout << endl; // cout << "请输入你想删除节点的内容:" << endl; // char ch; // cin >> ch; // TNode* temp = t1.Find(t1.root, ch); // t1.DelSubTree(temp); // cout << "新t1层次遍历: " << endl; // t1.LevelOrder(); // cout << endl; // Tree t2(t1.root); // cout << "PreOrder: " << endl; // t1.PreOrder(); // cout << endl; // cout << "InOrder: " << endl; // t1.InOrder(); // cout << endl; // cout << "非递归中根遍历: " << endl; // t1.NorecInOrder(); // cout << endl; // cout << "非递归先根遍历: " << endl; // t1.NorecPreOrder(); // cout << "非递归后根遍历: " << endl; // t1.NorecPostOrder(); // cout << endl; // cout << "t2层次遍历: " << endl; // t2.LevelOrder(); // cout << endl; //Tree t3('#'); //cout << "InOrder: " << endl; //t3.InOrder(); //cout << endl; }