C++实现二叉树基本操作详解

2024-11-28 16:13:23

树是一种重要的非线性数据结构，二叉树是树型结构的一种重要类型。本学年论文介绍了二叉树的定义，二叉树的存储结构，二叉树的相关术语，以此引入二叉树这一概念，为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块：二叉树的遍历方法，计算二叉树的结点个数，计算二叉树的叶子结点个数，二叉树深度的求解等内容。

前序遍历（递归&非递归）

访问根节点
前序访问左子树
前序访问右子树

//前序非递归
  void PrevOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        cout << cur->_data << " ";
        s.push(cur);
        cur = cur->_left;
      }
      //此时当前节点的左子树已遍历完毕
      Node *tmp = s.top();
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //前序递归
  void PrevOrderR()
  {
    _PrevOrder(_root);

    cout << endl;
  }

  void _PrevOrder(Node *root)
  {
    if (root == NULL) //必须有递归出口！！！
      return;

    cout << root->_data << " ";
    _PrevOrder(root->_left);
    _PrevOrder(root->_right);
  }

中序遍历（递归&非递归）

中序访问左子树
访问根节点
中序访问右子树

//中序非递归
  void InOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      //此时当前节点的左子树已遍历完毕
      Node *tmp = s.top();
      cout << tmp->_data << " ";
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //中序递归
  void InOrderR()
  {
    _InOrder(_root);

    cout << endl;
  }

  void _InOrder(Node *root)
  {
    if (root == NULL)
      return;

    _InOrder(root->_left);
    cout << root->_data << " ";
    _InOrder(root->_right);
  }

后序遍历（递归&非递归）

  //后序非递归
  //后序遍历可能会出现死循环，所以要记录下前一个访问的节点
  void PostOrder()
  {
    stack<Node*> s;
    Node *cur = _root;
    Node *prev = NULL;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      Node *tmp = s.top();
      if (tmp->_right && tmp->_right != prev)
      {
        cur = tmp->_right;
      }
      else
      {
        cout << tmp->_data << " ";
        prev = tmp;
        s.pop();
      }
    }
    cout << endl;
  }

  //后序递归
  void PostOrderR()
  {
    _PostOrder(_root);

    cout << endl;
  }

  void _PostOrder(Node *root)
  {
    if (root == NULL)
      return;

    _PostOrder(root->_left);
    _PostOrder(root->_right);
    cout << root->_data << " ";
  }

层序遍历

从根节点开始，依次访问每层结点。
利用队列先进先出的特性，把每层结点从左至右依次放入队列。

 void LevelOrder() //利用队列！！！
  {
    queue<Node*> q;
    Node *front = NULL;

    //1.push根节点
    if (_root)
    {
      q.push(_root);
    }
    //2.遍历当前节点，push当前节点的左右孩子，pop当前节点
    //3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空
    while (!q.empty())
    {

      front = q.front();
      cout << front->_data << " ";

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);

      q.pop();
    }

    cout << endl;
  }

求二叉树的高度

  size_t Depth()
  {
    return _Depth(_root);
  }

  size_t _Depth(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
    {
      size_t leftDepth = _Depth(root->_left) + 1;
      size_t rightDepth = _Depth(root->_right) + 1;
      return leftDepth > rightDepth ? leftDepth : rightDepth;
    }
  }

求叶子节点的个数

size_t LeafSize()
  {
    return _LeafSize(_root);
  }

  size_t _LeafSize(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
      return _LeafSize(root->_left) + _LeafSize(root->_right);
  }

求二叉树第k层的节点个数

size_t GetKLevel(int k)
  {
    return _GetKLevel(_root, k);
  }

  size_t _GetKLevel(Node *root, int k)
  {
    if (root == NULL)
      return 0;
    else if (k == 1)
      return 1;
    else
      return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
  }

完整代码如下：

template<class T>
struct BinaryTreeNode
{
  T _data;
  BinaryTreeNode *_left;
  BinaryTreeNode *_right;

  BinaryTreeNode(const T& d)
    :_data(d)
    , _left(NULL)
    , _right(NULL)
  {}
};

template<class T>
class BinaryTree
{
public:
  typedef BinaryTreeNode<T> Node;

  BinaryTree()
    :_root(NULL)
  {}

  BinaryTree(T *arr, size_t n, const T& invalid)
  {
    size_t index = 0;
    _root = _CreateBinaryTree(arr, n, invalid, index);
  }

  BinaryTree(const BinaryTree<T>& t)
    :_root(NULL)
  {
    _root = _CopyTree(t._root);
  }

  BinaryTree<T>& operator=(const BinaryTree<T>& t)
  {
    if (this != t)
    {
      Node *tmp = new Node(t._root);
      if (tmp != NULL)
      {
        delete _root;
        _root = tmp;
      }
    }
    return *this;
  }

  ~BinaryTree()
  {
    _DestroyTree(_root);
    cout << endl;
  }

  //前序非递归
  void PrevOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        cout << cur->_data << " ";
        s.push(cur);
        cur = cur->_left;
      }
      //此时当前节点的左子树已遍历完毕
      Node *tmp = s.top();
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //前序递归
  void PrevOrderR()
  {
    _PrevOrder(_root);

    cout << endl;
  }

  //中序非递归
  void InOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      //此时当前节点的左子树已遍历完毕
      Node *tmp = s.top();
      cout << tmp->_data << " ";
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //中序递归
  void InOrderR()
  {
    _InOrder(_root);

    cout << endl;
  }

  //后序非递归
  //后序遍历可能会出现死循环，所以要记录下前一个访问的节点
  void PostOrder()
  {
    stack<Node*> s;
    Node *cur = _root;
    Node *prev = NULL;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      Node *tmp = s.top();
      if (tmp->_right && tmp->_right != prev)
      {
        cur = tmp->_right;
      }
      else
      {
        cout << tmp->_data << " ";
        prev = tmp;
        s.pop();
      }
    }
    cout << endl;
  }

  //后序递归
  void PostOrderR()
  {
    _PostOrder(_root);

    cout << endl;
  }

  void LevelOrder() //利用队列！！！
  {
    queue<Node*> q;
    Node *front = NULL;

    //1.push根节点
    if (_root)
    {
      q.push(_root);
    }
    //2.遍历当前节点，push当前节点的左右孩子，pop当前节点
    //3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空
    while (!q.empty())
    {

      front = q.front();
      cout << front->_data << " ";

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);

      q.pop();
    }

    cout << endl;
  }

  size_t Size()
  {
    return _Size(_root);
  }

  size_t LeafSize()
  {
    return _LeafSize(_root);
  }

  size_t GetKLevel(int k)
  {
    return _GetKLevel(_root, k);
  }

  size_t Depth()
  {
    return _Depth(_root);
  }

  Node* Find(const T& d)
  {
    return _Find(_root, d);
  }

protected:
  Node* _CreateBinaryTree(T *arr, size_t n, const T& invalid, size_t& index)
  {
    Node *root = NULL;
    if (index < n && arr[index] != invalid)
    {
      root = new Node(arr[index]);
      index++;
      root->_left = _CreateBinaryTree(arr, n, invalid, index);
      index++;
      root->_right = _CreateBinaryTree(arr, n, invalid, index);
    }
    return root;
  }

  Node* _CopyTree(Node *root)
  {
    Node *newRoot = NULL;

    if (root)
    {
      newRoot = new Node(root->_data);
      newRoot->_left = _CopyTree(root->_left);
      newRoot->_right = _CopyTree(root->_right);
    }

    return newRoot;
  }

  void _DestroyTree(Node *root)
  {
    if (root)
    {
      _Destroy(root->_left);
      _Destroy(root->_right);
      delete root;
    }
  }

  void _PrevOrder(Node *root)
  {
    if (root == NULL) //必须有递归出口！！！
      return;

    cout << root->_data << " ";
    _PrevOrder(root->_left);
    _PrevOrder(root->_right);
  }

  void _InOrder(Node *root)
  {
    if (root == NULL)
      return;

    _InOrder(root->_left);
    cout << root->_data << " ";
    _InOrder(root->_right);
  }

  void _PostOrder(Node *root)
  {
    if (root == NULL)
      return;

    _PostOrder(root->_left);
    _PostOrder(root->_right);
    cout << root->_data << " ";
  }

  size_t _Size(Node *root)
  {
    if (root == NULL)
      return 0;
    else
      return _Size(root->_left) + _Size(root->_right) + 1;
  }

  size_t _LeafSize(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
      return _LeafSize(root->_left) + _LeafSize(root->_right);
  }

  size_t _GetKLevel(Node *root, int k)
  {
    if (root == NULL)
      return 0;
    else if (k == 1)
      return 1;
    else
      return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
  }

  size_t _Depth(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
    {
      size_t leftDepth = _Depth(root->_left) + 1;
      size_t rightDepth = _Depth(root->_right) + 1;
      return leftDepth > rightDepth ? leftDepth : rightDepth;
    }
  }

  Node* _Find(Node *root, const T& d)
  {
    if (root == NULL)
      return NULL;
    else if (root->_data == d)
      return root;
    else if (Node *ret = _Find(root->_left, d))
      return ret;
    else
      _Find(root->_right, d);
  }

protected:
  Node *_root;
};

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C++实现二叉树遍历序列的求解方法

本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序
C++实现二叉树非递归遍历方法实例总结

一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的.现举一个非递归遍历的方法如下,供大家参考. 具体代码如下: class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> out; stack<TreeNode*> s; s.push(root); while(!s.empty()
C++非递归队列实现二叉树的广度优先遍历

本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu
C++非递归建立二叉树实例

本文实例讲述了C++非递归建立二叉树的方法.分享给大家供大家参考.具体分析如下: 思路: 设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子,2表示需要创建右孩子,3则表示当前结点的左右孩子都已经创建完毕,需要执行出栈操作,直到当前结点不是父结点的右孩子为止. 以先序创建如图所示二杈树: 实现代码: PBTree create() { char ch[20]; scanf("%s",ch); int len = strlen(ch); PBTree
c++二叉树的几种遍历算法

1. 前序/中序/后序遍历(递归实现) 复制代码代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode) return; visit(pNode); BT_PreOrder(pNode->left); BT_PreOrder(pNode->right); }// 中序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode) return; BT_PreOrder(
C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/
二叉树遍历非递归 C++实现代码

二叉树的非递归遍历二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点. 一.前序遍历前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问. 1.递归实现复制代码代码
C++二叉树结构的建立与基本操作

准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码代码如下: #define MAXLEN 20 //最大长度typedef char DATA; //定义元素类型struct CBTType //定义二叉树结点类型 { DATA data; //元素数据 CBTType * left; //左子树结点指针 CBTType * right; //右子树结点指针 }; 定义二叉树结构数据元素的类型DA
探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

如有不足之处,还望指正! 复制代码代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data;
C++实现查找二叉树中和为某一值的所有路径的示例

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径. 打印出和与输入整数相等的所有路径. 例如输入整数22和如下二元树则打印出两条路径:10, 12和10, 5, 7. 先序遍历树即可得到结果. 算法: FindPath(BTree * root,int sum,int target,Stack * s) 用来计算,sum为栈中的元素的和,target为目标值. 到达一个节点之后计算当前节点和sum的和,如果为target,输出路径返回,如果大于target,则直接返回,如果小

C++实现二叉树基本操作详解

相关推荐

随机推荐