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 treeRoot = CreateTree();
   scanTree(treeRoot);
  }
  private static void scanTree(Node treeRoot)
  {
   List<Node> list = new List<Node>();
   list.Add(treeRoot);
   Node point = treeRoot;
   Write(treeRoot);
   while (true)
   {
    if (!list.Contains(point))
    { //上一轮是移除的操作
     if (treeRoot.leftSon == point)
     {//移除的是左结点
      if (treeRoot.rightSon != null)
      {
       treeRoot = treeRoot.rightSon;
       list.Add(treeRoot);
       Write(treeRoot);
       point = treeRoot;
       continue;
      }
      list.Remove(treeRoot);
      if (list.Count == 0)
      {
       break;
      }
      point = treeRoot;
      treeRoot = list[list.Count - 1];
     }
     else
     {//移除的是右结点
      list.Remove(treeRoot);
      if (list.Count == 0)
      {
       break;
      }
      point = treeRoot;
      treeRoot = list[list.Count - 1];
     }
     continue;
    }
    if (treeRoot.leftSon != null)
    {
     treeRoot = treeRoot.leftSon;
     Write(treeRoot);
     list.Add(treeRoot);
     point = treeRoot;
     continue;
    }
    if (treeRoot.rightSon != null)
    {
     treeRoot = treeRoot.rightSon;
     Write(treeRoot);
     point = treeRoot;
     list.Add(treeRoot);
     continue;
    }
    if (treeRoot.leftSon == null && treeRoot.rightSon == null)
    {
     list.Remove(treeRoot);
     if (list.Count == 0)
     {
      break;
     }
     point = treeRoot;
     treeRoot = list[list.Count - 1];
    }
   }
  }
  public static void Write(Node node)
  {
   Console.WriteLine(node.Data);
  }
  private static Node CreateTree()
  {
   Node a = new Node("A");
   a.leftSon = new Node("B");
   a.rightSon = new Node("C");
   a.leftSon.leftSon = new Node("D");
   a.leftSon.rightSon = new Node("E");
   a.rightSon.leftSon = new Node("F");
   a.rightSon.rightSon = new Node("G");
   a.leftSon.leftSon.leftSon = new Node("H");
   a.leftSon.leftSon.rightSon = new Node("I");
   return a;
  }
 }
 class Node
 {
  public string Data { get; set; }
  public Node leftSon { get; set; }
  public Node rightSon { get; set; }
  public Node(string data)
  {
   Data = data;
  }
 }
}

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

(0)

相关推荐

  • 二叉树先根(先序)遍历的改进

    二叉树的特点:每个结点的度最大不能超过2,并且左右子树不能颠倒 二叉树的存储结构:下面采用链式存储进行阐述,堆排序算法(快速排序改进)采用的顺序存储结构的二叉树,先看如下结构体的存储方式 顺序存储: 复制代码 代码如下: /*二叉树的顺序存储*/#define  MAX_TREE_SIZE 100typedef  TElemType  SqBiTree[MAX_TREE_SIZE]; 链式存储: 复制代码 代码如下: /*二叉树的链式存储*/typedef struct BiTNode{ TEl

  • C++基于先序、中序遍历结果重建二叉树的方法

    本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

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

  • 通过先序遍历和中序遍历后的序列还原二叉树(实现方法)

    当我们有一个 先序遍历序列:1,3,7,9,5,11 中序遍历序列:9,7,3,1,5,11 我们可以很轻松的用笔写出对应的二叉树.但是用代码又该如何实现? 下面我们来简单谈谈基本思想. 首先,先序遍历的顺序是根据 根-左孩子-右孩子 的顺序遍历的,那么我们可以率先确认的是先序遍历序列的第一个数就是根节点,然后中序遍历是根据 左孩子-根-右孩子 的顺序遍历的.我们通过先序遍历确认了根节点,那么我们只需要在中序遍历中找到根节点的位置,然后就可以很好地区分出,那些属于左子树的节点,那些是属于右子树的

  • C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法

    本文实例讲述了C#使用前序遍历.中序遍历和后序遍历打印二叉树的方法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data;

  • 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

  • C语言非递归后序遍历二叉树

    本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下 法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;

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

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

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

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

  • C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解 2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法: (1)前序遍历(2)中序遍历(3)后续遍历 以下是经典示例: #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode

  • 先序遍历二叉树的递归实现与非递归实现深入解析

    1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点:2)先序遍历左子树:3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visit(root->data); // visit the data    PreOrder(ro

  • PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

  • python先序遍历二叉树问题

    问题 如何遍历一个二叉树 遍历二叉树就是访问二叉树的每一个节点 二叉树父结点下先左访问,先序遍历(根左右) 例如:遍历以下的二叉树 遍历结果:ABDECF Python代码示例 # !/usr/bin/env python # -*-encoding: utf-8-*- # author:LiYanwei # version:0.1 class TreeNode(object): ''' 二叉树类 ''' def __init__ (self, data, left = None, right

  • C++树之遍历二叉树实例详解

    在讲遍历之前,我们要先创建一个树: #include <iostream> using namespace std; typedef struct node; typedef node *tree; struct node{ int data; // 结点数值 tree left,right; // 左子树和右子树 }; tree bt; 遍历二叉树有三种方式: 先序遍历 先序遍历的操作如下: 访问根结点 先序遍历左子树(递归) 先序遍历右子树(递归) 二叉树bt的先序遍历结果:1234753

随机推荐