二叉树的所有编程算法

  • a4_308680
    了解作者
  • 2.5KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-06 07:47
    上传日期
二叉树的建立,遍历算法(递归与非递归,基于对列或堆栈)统计二叉树中叶子结点的个数,统计二叉树中结点的总数,求二叉树的深度(后序遍历),求二叉树的宽度(具有结点数最多的层上的结点数,已知二叉树中序遍历和后序遍历序列,求二叉树的二叉链表结构,已知二叉树中序遍历和先序遍历序列,求二叉树的二叉链表结构
二叉树的所有编程算法.rar
  • TowTrees.cpp
    10.4KB
内容介绍
#include <iostream> #include <string> #include <vector> #include <list> #include <cassert> using namespace std; // struct define struct Node { char c; Node* left; Node* right; bool leftVisite; bool rightVisite; Node() { c = 0; left = 0; right = 0; leftVisite = false; rightVisite = false; } }; // 按先序扩展序列建立二叉树 Node* createTree(const string& allNodes); void displayTree(Node* tree); // 先序、中序、后序遍历的递归算法 void firstTravel(Node* tree); void midTravel(Node* tree); void lastTravel(Node* tree); // 先序遍历的非递归算法, 基于堆栈 void _firstTravel(Node* tree); // 中序遍历的非递归算法, 基于堆栈 void _midTravel(Node* tree); // 后序遍历的非递归算法, 基于堆栈 void _lastTravel(Node* tree); // 释放资源 void releaseTravel(Node* tree); // 层次的非递归算法, 基于队列 void levelTravel(Node* tree); // 统计二叉树中叶子结点的个数 int countLeaf(Node* tree); // 统计二叉树中结点的总数 int countNode(Node* tree); // 求二叉树的深度(后序遍历) int treeDepth(Node* tree); // 求二叉树的宽度(具有结点数最多的层上的结点数) unsigned int treeWidth(Node* tree); // 已知二叉树中序遍历和后序遍历序列,求二叉树的二叉链表结构 Node* midLastToTree(const string& midIn, const string& lastIn); // 已知二叉树中序遍历和先序遍历序列,求二叉树的二叉链表结构 Node* firstMidToTree(const string& midIn, const string firstIn); void main() { cout<<"输入先序扩展序列\n"; string inData; getline(cin, inData); Node* tree = createTree(inData); cout<<"树的2叉表示:\n"; displayTree(tree); cout<<"先序遍历:"; firstTravel(tree); cout<<'\n'; cout<<"中序遍历:"; midTravel(tree); cout<<'\n'; cout<<"后序遍历:"; lastTravel(tree); cout<<'\n'; cout<<"非递归先序遍历:"; _firstTravel(tree); cout<<'\n'; cout<<"非递归中序遍历:"; _midTravel(tree); cout<<'\n'; cout<<"非递归后序遍历:"; _lastTravel(tree); cout<<'\n'; cout<<"层次遍历:"; levelTravel(tree); cout<<'\n'; cout<<"叶子节点数目:"<<countLeaf(tree)<<'\n'; cout<<"总节点数目:"<<countNode(tree)<<'\n'; cout<<"树深度:"<<treeDepth(tree)<<'\n'; cout<<"树宽度:"<<treeWidth(tree)<<'\n'; // 中序遍历和后序遍历序列求二叉树 { releaseTravel(tree); cout<<"输入中序和后序遍历序列\n"; string midIn, lastIn; getline(cin, midIn); getline(cin, lastIn); tree = midLastToTree(midIn, lastIn); displayTree(tree); } // 中序遍历和先序遍历序列求二叉树 { releaseTravel(tree); cout<<"输入先序遍历和中序遍历序列\n"; string midIn, firstIn; getline(cin, firstIn); getline(cin, midIn); tree = firstMidToTree(midIn, firstIn); displayTree(tree); } cout<<"press any key to continue\n"; cin>>inData; releaseTravel(tree); } void createChild(Node* &node, string::const_iterator& iter, string::const_iterator& endIter) { if (iter != endIter) { char c = *iter++;//建立字符串 if (' ' == c) { node = 0; } else { node = new Node; node->c = c;//构造根结点 createChild(node->left, iter, endIter);//构造左子树 createChild(node->right, iter, endIter);//构造右子树 } } else { node = 0; } } Node* createTree(const string& allNodes)// 按先序扩展序列建立二叉树 { string::const_iterator curIter = allNodes.begin(); string::const_iterator endIter = allNodes.end(); Node* tree = 0; createChild(tree, curIter, endIter); return tree; } void firstTravel(Node* tree)//先序遍历的递归算法 { if (tree) { cout<<tree->c;//根 firstTravel(tree->left);//左 firstTravel(tree->right);//右 } } void releaseTravel(Node* tree)// 释放资源 { if (tree) { releaseTravel(tree->left); releaseTravel(tree->right); delete tree; tree = 0; } } void midTravel(Node* tree)//中序遍历的递归算法 { if (tree) { midTravel(tree->left); cout<<tree->c; midTravel(tree->right); } } void lastTravel(Node* tree)//后序遍历的递归算法 { if (tree) { lastTravel(tree->left); lastTravel(tree->right); cout<<tree->c; } } void resetTree(Node* tree)//重置二叉树 { if (tree) { tree->leftVisite = false; tree->rightVisite = false; resetTree(tree->left); resetTree(tree->right); } } void _firstTravel(Node* tree)//先序遍历非递归算法 { //assert(tree); resetTree(tree); typedef vector<Node*> NodeStack; NodeStack stack; stack.push_back(tree); // 初始化栈 while (stack.size()) { Node* topNode = stack.back(); if (!topNode->leftVisite && !topNode->rightVisite) { cout<<topNode->c; } if (topNode->left && !topNode->leftVisite) { stack.push_back(topNode->left); topNode->leftVisite = true; }else if (topNode->right && !topNode->rightVisite) { stack.push_back(topNode->right); topNode->rightVisite = true; } else { stack.pop_back(); } } } void _midTravel(Node* tree)//中序遍历的非递归算法 { //assert(tree); resetTree(tree); typedef vector<Node*> NodeStack; NodeStack stack; stack.push_back(tree); // 初始化 while (stack.size()) { Node* topNode = stack.back(); if (topNode->leftVisite && !topNode->rightVisite) { cout<<topNode->c; } if (topNode->left && !topNode->leftVisite) { stack.push_back(topNode->left); topNode->leftVisite = true; }else if (topNode->right && !topNode->rightVisite) { if (!topNode->left && topNode->right) {cout<<topNode->c; }// 单边只有右子节点 stack.push_back(topNode->right); topNode->rightVisite = true; } else { if (!topNode->left && !topNode->right) { cout<<topNode->c; } stack.pop_back(); } } } void _lastTravel(Node* tree)//后序遍历的非递归算法 { //assert(tree); resetTree(tree); typedef vector<Node*> NodeStack; NodeStack stack; stack.push_back(tree); // 初始化 while (stack.size()) { Node* topNode = stack.back(); if (topNode->leftVisite && topNode->rightVisite) { cout<<topNode->c; } if (topNode->left && !topNode->leftVisite) { stack.push_back(topNode->left); topNode->leftVisite = true; }else if (topNode->right && !topNode->rightVisite) { stack.push_back(topNode->right); topNode->rightVisite = true; } else { // 针对叶子节点或者单边子节点的情况 if (!topNode->left || !topNode->right) { cout<<topNode->c; } stack.pop_back(); } } } void levelTravel(Node* tree)// 层次的非递归算法, 基于队列 { //assert(tree); typedef list<Node*> Queue; Queue nodeQueue; nodeQueue.push_back(tree); while (nodeQueue.size())//由上至下,由左至右 { Node* node = nodeQueue.front(); cout<<node->c; if (node->left) { nodeQueue.push_back(node->left); } if (node->right) { nodeQueue.push_back(node->right); } nodeQueue.pop_front(); } } int countLeaf(Node* tree)// 统计二叉树中叶子结点的个数 { if (!tree) { return 0; } if (!tree->left && !tree->right)//孤立点 { return 1; } //递归计算 int sum = 0; sum += countLeaf(tree->left); sum += countLeaf(tree->right); return sum; } int countNode(Node* tree)// 统计二叉树中结点的总数 { int sum = 0; if (tree) { sum = 1; sum += countNode(tree->left); sum += countNode(tree->right); } return sum; } int treeDepth(Node* tree)// 求二叉树的深度(后序遍历) { int leftDepth = 0; int rightDepth = 0; if (tree) { leftDepth = 1; leftDepth += treeDepth(tree->left); rightDepth = 1; rightDepth += treeDepth(tree->right); } return max(leftDepth, rightDepth); } unsigned int treeWidth(Node* tree)// 求二叉树的宽度(具有结点数最多的层上的结点数) { if (!tree) { return 0; } typedef list<Node*> Queue; Queue nodeQueue; unsigned int width = 0; nodeQueue.push_back(tree); while (nodeQueue.size()) { unsigned int size = nodeQueue.size(); // 上一层的节点全部出列,并压入下一层节点 for (unsigned int i=0; i<size; ++i) { Node* node = nodeQueue.front(); if (node->left) { nodeQ
评论
    相关推荐
    • 静态链表算法
      #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0
    • LinkedList:链表算法
      链表算法 链表算法的实现,该算法从stdin读取用户命令并根据用户指令命令在链表上运行特定功能,例如:PUT n,GET n,LIST,FIRST,LAST,SORT,CLEAR,REMOVE n,EXIT,其中: PUT n-将一个整数n插入到链表中。 ...
    • 单双向链表算法
      package 单双向链表; /** * 单向链表增删改查操作 * */ public class LinkTest { public static void main(String[] args) { Link l=new Link(); l.addNode("A"); l.addNode("B"); l.addNode("C"); l....
    • 数据结构中的链表算法
      学习数据结构的朋友,来看看吧,不会后悔的啦!
    • 数据结构的双链表算法
      数据结构的双链表算法:双链表基本运算插入前插入后,循环双链表的基本运算。用C++语言写的控制台程序。
    • 链表算法详细代码
      链表算法详细代码,单链表,双链表,循环链表等等各种链表的代码详细代码
    • 链表相关算法.rar
      链表的相关算法题:很重要:7道 一般面试问的第一个问题,链表反转!
    • 链表倒置算法
      数据结构第二章 3题 给定一个不带头结点的单链表,写出将链表倒置的算法
    • Java有序非循环双向链表算法实例
      Java 有序 非循环 双向 链表 算法 实例