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