数据结构--树的实现

实现内容代码示例binarytree.hbitnaryTree.cpptesetcase.cpp

实现内容

本文实现了树的基本操作：

创建二叉树 (按前序方式递归创建)遍历二叉树： – 前序遍历(递归和非递归方式) – 中序遍历(递归和非递归方式) – 后序遍历(递归和非递归方式) – 层遍历 – 层遍历改编的用于先序遍历寻找叶子结点递归求树的深度销毁树

代码示例

binarytree.h

#pragma once #ifndef BITNARYTREE_H_ #define BITNARYTREE_H_ #include <iostream> #include <stack> #include <queue> typedef struct TreeNode* Bitree; typedef char ElemType; struct TreeNode { ElemType data; TreeNode* lchild; TreeNode* rchild; }; //创建树 void CreateTree(Bitree& T); //销毁树 void DestroyTree(Bitree& T); //递归遍历树 void PreOrderTraverse(Bitree T); void InOrderTraverse(Bitree T); void AftOrderTraverse(Bitree T); //非递归遍历树 void PreOrederTraverseNoRecurse(Bitree T); void InOrderTraverseNoRecurse(Bitree T); void AftOrderTraverseNoRecurse(Bitree T); //层遍历 void LayerTraverseNoRecurse(Bitree T); //层遍历改编的用于先序遍历 void PreorderLrchildTraverse(Bitree T); //输出叶子结点 void TreeLeavesPreOrder(Bitree T); void TreeLeavesInOrder(Bitree T); void TreeLeavesAftOrder(Bitree T); //树的深度 int TreeDepth(Bitree T); #endif // !BITNARYTREE_H_

bitnaryTree.cpp

#include "binarytree.h" using namespace std; //创建树 void CreateTree(Bitree& T) { ElemType ch; cin >> ch; if (ch == '#') { T = nullptr; } else { T = new TreeNode; if (T == nullptr) exit(OVERFLOW); T->data = ch; CreateTree(T->lchild); CreateTree(T->rchild); } } //销毁树 void DestroyTree(Bitree& T) { if (T != nullptr) { DestroyTree(T->lchild); DestroyTree(T->rchild); cout <<"Delete: "<< T->data << endl; delete T; T = nullptr; } } //递归遍历树 void PreOrderTraverse(Bitree T) { if (T != nullptr) { cout << T->data << " "; PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(Bitree T) { if (T != nullptr) { InOrderTraverse(T->lchild); cout << T->data << " "; InOrderTraverse(T->rchild); } } void AftOrderTraverse(Bitree T) { if (T != nullptr) { AftOrderTraverse(T->lchild); AftOrderTraverse(T->rchild); cout << T->data << " "; } } //非递归遍历树 void PreOrederTraverseNoRecurse(Bitree T) { stack<TreeNode*> s; TreeNode* p = T; while (p != nullptr || !s.empty()) { while (p != nullptr) { cout << p->data << " "; s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); s.pop(); p = p->rchild; } } } void InOrderTraverseNoRecurse(Bitree T) { stack<Bitree> s; Bitree p = T; while (p != nullptr || !s.empty()) { while (p != nullptr) { s.push(p); p = p->lchild; } if (!s.empty()) { p = s.top(); cout << p->data << " "; s.pop(); p = p->rchild; } } } void AftOrderTraverseNoRecurse(Bitree T) { stack<Bitree> s; Bitree top = nullptr; Bitree cur = T; Bitree pre = nullptr; if (T != nullptr) { while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->lchild; } top = s.top(); if (top->rchild == nullptr || top->rchild == pre) { cout << top->data << " "; pre = top; s.pop(); } else { cur = top->rchild; } } } } //层遍历树 void LayerTraverseNoRecurse(Bitree T) { //1、根节点入队 2、根节点出队，并将其孩子结点入队 3、出队并将队首元素孩子入队 if (T) { Bitree p = T; queue<Bitree> Que; Que.push(p); while (!Que.empty()) { p = Que.front(); cout << p->data << " "; Que.pop(); if (p->lchild) Que.push(p->lchild); if (p->rchild) Que.push(p->rchild); } } } //左右孩子法实现先序遍历 void PreorderLrchildTraverse(Bitree T) { if (T) { stack<Bitree> s; Bitree p = T; s.push(p); while (!s.empty()) { p = s.top(); cout << p->data << " "; s.pop(); if (p->rchild) s.push(p->rchild); if (p->lchild) s.push(p->lchild); } } } //输出叶子结点 void TreeLeavesPreOrder(Bitree T) { if (T) { if (T->lchild == nullptr && T->rchild == nullptr) { cout << T->data << " "; } TreeLeavesPreOrder(T->lchild); TreeLeavesPreOrder(T->rchild); } } void TreeLeavesInOrder(Bitree T){ if (T) { TreeLeavesPreOrder(T->lchild); if (T->lchild == nullptr && T->rchild == nullptr) { cout << T->data << " "; } TreeLeavesPreOrder(T->rchild); } } void TreeLeavesAftOrder(Bitree T) { if (T) { TreeLeavesPreOrder(T->lchild); TreeLeavesPreOrder(T->rchild); if (T->lchild == nullptr && T->rchild == nullptr) { cout << T->data << " "; } } } //获取树的深度 int TreeDepth(Bitree T) { if (T) { int hl, hr, maxh; hl = TreeDepth(T->lchild); hr = TreeDepth(T->rchild); maxh = (hl > hr) ? hl : hr; return (maxh + 1); } else { return 0; } }

tesetcase.cpp

#include <iostream> #include "binarytree.h" int main() { using namespace std; Bitree Tree; //create tree in pre order cout << "create treee in pre order" << endl; CreateTree(Tree); //traverse trees in recurve way cout << "\npre order traverse: "; PreOrderTraverse(Tree); cout<< "\nin order traverse: "; InOrderTraverse(Tree); cout << "\nAter order traverse: "; AftOrderTraverse(Tree); cout << endl; //traverse tree in non recurse way cout << "\nPreOrederTraverseNoRecurse:"; PreOrederTraverseNoRecurse(Tree); cout << "\nInOrederTraverseNoRecurse:"; InOrderTraverseNoRecurse(Tree); cout << "\nAftOrederTraverseNoRecurse:"; AftOrderTraverseNoRecurse(Tree); cout << endl; cout << "\nLayerTraverseNoRecurse:"; LayerTraverseNoRecurse(Tree); //左右孩子法实现先序遍历 cout << "\nPreorderLrchildTraverse:"; PreorderLrchildTraverse(Tree); cout << endl; //叶子结点 cout << "\nget leaves in preorder:"; TreeLeavesPreOrder(Tree); cout << "\nget leaves in inorder:"; TreeLeavesInOrder(Tree); cout << "\nget leaves in postorder:" ; TreeLeavesAftOrder(Tree); cout << endl; //获取树的深度 cout << "tree depth: "<<TreeDepth(Tree) << endl; //销毁树 DestroyTree(Tree); return 0; }