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

2018-05-15  本文已影响16人  动感新势力fan

只有先序、后序、层序可以用来创建二叉树(且要添加虚空节点),中序是不可以的。
原因很简单,因为即使添加了虚空节点,中序序列仍然不可以唯一确定一棵二叉树。(那何来创建二叉树之说?)
如:设一棵带虚空节点(用'#'表示)的二叉树的中序遍历序列为:#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;
}
上一篇 下一篇

猜你喜欢

热点阅读