美文网首页
二叉树前序创建和前序遍历

二叉树前序创建和前序遍历

作者: 动感新势力fan | 来源:发表于2018-05-15 14:18 被阅读16次

只有先序、后序、层序可以用来创建二叉树(且要添加虚空节点),中序是不可以的。
原因很简单,因为即使添加了虚空节点,中序序列仍然不可以唯一确定一棵二叉树。(那何来创建二叉树之说?)
如:设一棵带虚空节点(用'#'表示)的二叉树的中序遍历序列为:#B#A#D#C#
我们可以同时找到至少两棵符合条件的二叉树:

(1)
      A
    B         C
 #    #   D    #
          #   #
(2)
                 C
            A      #
       B      D
     #  #   #  #
#include <iostream>
using namespace std;
struct Node{
    char data;
    Node *left;
    Node *right;
};
typedef Node*  Btree;
void createTree(Btree &T){
    char ch;
    cin >> ch;
    if(ch == '#')  T = NULL;
    else{
        T = (Btree)malloc(sizeof(Btree));
        T->data = ch;
        createTree(T->left);
        createTree(T->right);
    }
}
/*前序遍历*/
void preOrderTraverse(Btree &T){
    if(T == NULL) return;
    cout << T->data << ' '; 
    preOrderTraverse(T->left);
    preOrderTraverse(T->right);
}
int main() {
    cout << "请输入扩展二叉树序列" << endl;
    Btree boot;
    createTree(boot);
    cout << endl;
    /*前序遍历*/
       preOrderTraverse(boot);
    cout << endl; 
    return 0;
}

相关文章

  • 二叉树的遍历

    二叉树的遍历 二叉树遍历 分为前序遍历、中序遍历和后序遍历。 前序遍历 (DLR) 先访问根节点,然后前序遍历左子...

  • 数据结构:树的实现和遍历(c++)

    (一)二叉树的遍历——递归实现 二叉树常见的遍历方式分为前序遍历、中序遍历和后序遍历。 1 前序遍历 前序遍历也叫...

  • leecode刷题(28)-- 二叉树的前序遍历

    leecode刷题(28)-- 二叉树的前序遍历 二叉树的前序遍历 给定一个二叉树,返回它的 前序 遍历。 示例:...

  • 遍历

    前序遍历 前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访...

  • 二叉树 - 前序遍历、中序遍历、后序遍历

    前序遍历 前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访...

  • 二叉树遍历

    二叉树的遍历 1. 前序遍历 1.1 递归前序遍历 1.2 非递归前序遍历 2 中序遍历 2.1递归遍历 2.2非...

  • 二叉树递归与非递归 - 代码实现

    前序遍历,中序遍历,后序遍历,层次遍历,深度遍历 参考深度遍历 本质上就是 前序遍历 C++ 实现 二叉树前序、中...

  • 二叉树递归非递归遍历算法整理

    一、二叉树前序遍历 1 前序递归遍历 2.前序非递归遍历 一、二叉树中序遍历 2.中序递归遍历 1.中序非递归遍历...

  • 数据结构(三):二叉树遍历

    遍历方式 二叉树的常见遍历方式如下几种: 前序遍历: 访问根节点,前序遍历方式访问左子树,前序遍历方式访问右子树;...

  • 二叉树遍历java,非递归、层次。

    /** * 前序遍历 * 递归 */ /*** 前序遍历* 非递归*/ 后续遍历非递归 二叉树层次遍历基于java...

网友评论

      本文标题:二叉树前序创建和前序遍历

      本文链接:https://www.haomeiwen.com/subject/cagedftx.html