己知链式二叉树的结点定义如下： typedef char ElemType; typedef struct BitNode { ElemType data; struct BitNode *Ichild,*rchild; }BTNode; 请写出先序、中序、后序遍历的递归算法。void PreOrder(BTNode *T) { } void InOrder(BTNode *t)//中序遍历 } void PostOrder(BTNode *t)//后序遍历

好的，以下是先序、中序、后序遍历的递归算法：

先序遍历：

void PreOrder(BTNode *T) {
if(T) {
printf("%c ", T->data); //先访问根节点
PreOrder(T->Ichild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}

中序遍历：

void InOrder(BTNode *T) {
if(T) {
InOrder(T->Ichild); //递归遍历左子树
printf("%c ", T->data); //访问根节点
InOrder(T->rchild); //递归遍历右子树
}
}

后序遍历：

void PostOrder(BTNode *T) {
if(T) {
PostOrder(T->Ichild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
printf("%c ", T->data); //访问根节点
}
}

相关问题

本题要求实现给定的二叉树的三种遍历。 函数接口定义： void Preorder(BiTree T); void Inorder(BiTree T); void Postorder(BiTree T); T是二叉树树根指针，Preorder、Inorder和Postorder分别输出给定二叉树的先序、中序和后序遍历序列，格式为一个空格跟着一个字符。 其中BinTree结构定义如下： typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 裁判测试程序样例： #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; BiTree Create();/* 细节在此不表 */ void Preorder(BiTree T); void Inorder(BiTree T); void Postorder(BiTree T); int main() { BiTree T = Create(); printf("Preorder:"); Preorder(T); printf("\n"); printf("Inorder:"); Inorder(T); printf("\n"); printf("Postorder:"); Postorder(T); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */ 输入样例： 输入为由字母和'#'组成的字符串，代表二叉树的扩展先序序列。例如对于如下二叉树，输入数据： AB#DF##G##C##

题目描述

给定一个二叉树的先序遍历、中序遍历和后序遍历，请分别输出它们的遍历结果。

样例

输入： AB#DF##G##C##
输出： Preorder: A B D F G C
Inorder: D F G B A C
Postorder: G F D B C A

算法1

(递归) $O(n)$

对于一棵二叉树，有三种基本的遍历方式：

- 先序遍历：从根节点开始，先输出根节点，然后遍历左子树，最后遍历右子树。
- 中序遍历：从根节点开始，先遍历左子树，然后输出根节点，最后遍历右子树。
- 后序遍历：从根节点开始，先遍历左子树，然后遍历右子树，最后输出根节点。

对于一棵二叉树，前序遍历的第一个节点就是这棵树的根节点，而且在中序遍历中，根节点把这个序列分成了左右两个子树的序列，因此可以根据这个性质进行递归求解。假设当前树的前序遍历序列为pre，中序遍历序列为in，那么可以通过查找pre[0]在in中的位置pos，即可确定左右子树的大小，从而分别递归求解左右子树的前序遍历和中序遍历，最后得到整棵树的前序遍历和中序遍历。

后序遍历的求解与前序遍历类似，只不过需要注意递归的顺序。对于一棵树，后序遍历的最后一个节点就是这棵树的根节点，因此可以先递归求解左右子树的后序遍历，再输出根节点。

时间复杂度

对于每个节点，每个节点会被遍历一次，因此时间复杂度为$O(n)$。

C++ 代码

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> s;
s.push(root);
while(!s.empty()) {
auto node = s.top();
s.pop();
res.push_back(node->val);
if(node->right) s.push(node->right);
if(node->left) s.push(node->left);
}
return res;
}

vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
auto node = root;
while(node || !s.empty()) {
while(node) {
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
res.push_back(node->val);
node = node->right;
}
return res;
}

vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> s1, s2;
s1.push(root);
while(!s1.empty()) {
auto node = s1.top();
s1.pop();
s2.push(node);
if(node->left) s1.push(node->left);
if(node->right) s1.push(node->right);
}
while(!s2.empty()) {
res.push_back(s2.top()->val);
s2.pop();
}
return res;
}
};

【问题描述】判断两棵二叉树是否结构相同。结构相同意味着对应的左子树和对应的右子树都 结构相同，不考虑数据内容。若已知两棵二叉树 B1 和 B2 皆为空, 或者皆不空且 B1 的左、右子 树和 B2 的左、右子树分别结构相同, 则称二叉树 B1 和 B2 结构相同。 【实验要求】 二叉树采用二叉链表存储，二叉链表定义如下： typedef char ElemType; typedef struct bitnode{ //定义二叉树节点结构 ElemType data; //数据域 struct bitnode *lchild,*rchild; //左右孩子指针域 }BiTNode,*BiTree; 【测试界面】 请输入（在空子树处添加*）二叉树 A 的先序序列： ABD*F***CE*** 请输入（在空子树处添加*）二叉树 B 的先序序列： MNA*B***FD*** [输出] 结构相同

以下是判断两棵二叉树是否结构相同的C++代码实现：

#include<iostream>
using namespace std;

typedef char ElemType;
typedef struct bitnode{
    ElemType data;
    struct bitnode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T){ //先序遍历创建二叉树
    ElemType ch;
    cin>>ch;
    if(ch == '*')
        T = NULL;
    else{
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

bool isSame(BiTree T1, BiTree T2){ //判断两棵二叉树是否结构相同
    if(T1 == NULL && T2 == NULL)
        return true;
    else if(T1 == NULL || T2 == NULL)
        return false;
    else{
        bool left = isSame(T1->lchild, T2->lchild);
        bool right = isSame(T1->rchild, T2->rchild);
        return left && right;
    }
}

int main(){
    BiTree A, B;
    cout<<"请输入（在空子树处添加*）二叉树 A 的先序序列：";
    CreateBiTree(A);
    cout<<"请输入（在空子树处添加*）二叉树 B 的先序序列：";
    CreateBiTree(B);
    if(isSame(A, B))
        cout<<"结构相同"<<endl;
    else
        cout<<"结构不同"<<endl;
    return 0;
}

输入示例：

请输入（在空子树处添加*）二叉树 A 的先序序列：ABD*F***CE***
请输入（在空子树处添加*）二叉树 B 的先序序列：MNA*B***FD***

输出示例：

结构相同