C++非递归建立二叉树实例

本文实例讲述了C++非递归建立二叉树的方法。分享给大家供大家参考。具体分析如下：

思路：

设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子，2表示需要创建右孩子，3则表示当前结点的左右孩子都已经创建完毕，需要执行出栈操作，直到当前结点不是父结点的右孩子为止。

以先序创建如图所示二杈树：

实现代码：

PBTree create()
{
 char ch[20];
 scanf("%s",ch);
 int len = strlen(ch);
 PBTree stack[20];
 /* 用来存储结点地址的栈 */
 int top = 0;
 /* 栈顶指针 */
 int flag = 1;
 /* 1表示现在需要创建左孩子，
 2表示需要创建右孩子，
 3表示左右孩子都已经创建完成 */
 int i = 0;
 PBTree temp;
 PBTree root = (PBTree)malloc(sizeof(BTree));
 root->data = ch[i++];
 root->lchild = NULL;
 root->rchild = NULL;
 stack[top ++] = root;
 while(i < len)
 {
  PBTree pNew = NULL;
  if(1 == flag) /* 创建左孩子 */
  {
   if('#' == ch[i])
    flag = 2;
   else
   {
    pNew = (PBTree)malloc(sizeof(BTree));
    pNew->lchild = NULL;
    pNew->rchild = NULL;
    pNew->data = ch[i];
    temp = stack[top - 1];
    temp->lchild = pNew;
    stack[top++] = pNew;
    flag = 1;
   }
  }
  else if(2 == flag)
  /* 创建右孩子 */
  {
   if('#' == ch[i])
    flag = 3;
   else
   {
    pNew = (PBTree)malloc(sizeof(BTree));
    pNew->lchild = NULL;
    pNew->rchild = NULL;
    pNew->data = ch[i];
    temp = stack[top - 1];
    temp->rchild = pNew;
    stack[top++] = pNew;
    flag = 1;
   }
  }
  else
  /* 左右孩子已经创建完成，需要出栈*/
  {
   temp = stack[--top];
   while(top > 1 && stack[top - 1]->rchild == temp)
    --top;
   flag = 2;
   --i;
  }
  ++i;
 }
 return root;
}

希望本文所述对大家的C++程序设计有所帮助。

赞 (0)

相关推荐

  • C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

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

  • 数据结构 二叉树的递归与非递归

    数据结构 二叉树的递归与非递归 实例代码: #include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T

  • C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

    本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同.分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • C++基于递归和非递归算法求二叉树镜像的方法

    本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

  • 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++非递归建立二叉树实例

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

  • Java编程二项分布的递归和非递归实现代码实例

    Java编程二项分布的递归和非递归实现代码实例

    本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k

  • C++ 非递归实现二叉树的前中后序遍历

    C++ 非递归实现二叉树的前中后序遍历

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 二叉树的前序遍历 在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制.二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可. 具体步骤如下: 将左路结点入栈,入栈的同时访问左路结点. 取出栈顶结点top. 准备访问top结点的右子树. struct Tre

  • C++实现二叉树非递归遍历方法实例总结

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

  • 二叉树遍历 非递归 C++实现代码

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

  • java二叉树的非递归遍历

    二叉树的递归遍历比较简单,这里就不聊了.今天主要聊聊二叉树的非递归遍历,主要借助于"栈"后进先出的特性来保存节点的顺序,先序遍历和中序遍历相对来说比较简单,重点理解后序遍历. 1. 先看看节点类型: //二叉树的节点类型 private class Node{ int data; //节点值 Node leftChild; //左孩子 Node rightChild; //右孩子 public Node(int data) { this.data=data; } } 2.先序遍历. 非

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • C#非递归先序遍历二叉树实例

    本文实例讲述了C#非递归先序遍历二叉树的方法.分享给大家供大家参考.具体如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication5 { class Program { static void Main(string[] args) { Node treeRoo

  • 二叉树的非递归后序遍历算法实例详解

    前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中.方法有很多,这里只举一种,先定义栈结点的数据结构 复制代码 代码如下: typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,往左下方走,一直走到头,将路径上

随机推荐