php实现二叉树遍历
一、总结
关注输入输出
二、php实现二叉树遍历
题目描述
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入描述:
输入包括1行字符串,长度不超过100。
输出描述:
可能有多组测试数据,对于每组数据,输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。每个输出结果占一行。
示例1
输入
abc##de#g##f###
输出
c b e g d f a
三、代码
代码一:java,教科书般
1 #include2 #include 3 using namespace std; 4 string str; 5 int i; 6 struct TreeNode 7 { 8 char val; 9 struct TreeNode *lchild, *rchild;10 TreeNode(char c) :val(c), lchild(NULL), rchild(NULL) {}11 };12 TreeNode* createTree() {13 char c = str[i++];14 if (c == '#') return NULL;15 TreeNode *root = new TreeNode(c);16 root->lchild = createTree();17 root->rchild = createTree();18 return root;19 }20 void inOrderTraversal(TreeNode* root) {21 if (!root) return;22 inOrderTraversal(root->lchild);23 cout << root->val << " ";24 inOrderTraversal(root->rchild);25 }26 int main() {27 while (cin >> str) {28 i = 0;29 TreeNode *root = createTree();30 inOrderTraversal(root);31 cout << endl;32 }33 return 0;34 }
代码二:php
百度一下php中的var
1 val=$val; 8 } 9 }10 $tree=new treeNode(3);11 echo $tree->val;12 ?>