二叉树遍历

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct TreeNode {
	char data;
	struct TreeNode *lchild;
	struct TreeNode *rchild;
}TreeNode;


// 前序遍历建立二叉树 
void createTree(TreeNode **T, char *data, int *index)
{
	char ch = data[*index];
	*index += 1;
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		createTree(&((*T)->lchild), data, index);
		createTree(&((*T)->rchild), data, index); 
	}	
}

void preOrder(TreeNode* T)
{
	if (T == NULL) 
	{
		return;
	}
	else 
	{
		printf("%c ", T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

void inOrder(TreeNode* T)
{
	if (T == NULL)
	{
		return;
	}
	else
	{
		inOrder(T->lchild);
		printf("%c ", T->data);
		inOrder(T->rchild);
	}
}


int main()
{
	char s[110];
	
	scanf("%s", &s);
	
	TreeNode *T;
	int index = 0;
		
	createTree(&T, s, &index);
		
	inOrder(T);
	printf("\n");
		 
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char*  BTDataType;
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType val;
} BTNode;
//初始化二叉树
BTNode* InitTree()
{
    BTNode* treenode = (BTNode*)malloc(sizeof(BTNode));
    if(treenode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    treenode->right = NULL;
    treenode->left = NULL;
    treenode->val = NULL;
    return treenode;
}
//用前序遍历构建二叉树
void PrevTreePush(char* ch,BTNode** root,int* i,size_t len)
{
    if(*i > len)
    {
        return;
    }
    if(*(ch+(*i)) == '#')
    {
        (*i)++;
        return;
    }
    *root = InitTree();
    (*root)->val = ch+(*i);
    (*i)++;
    PrevTreePush(ch, &(*root)->left,i,len);
    PrevTreePush(ch, &(*root)->right,i,len);

}
void InOrderTraversal(BTNode * root)
{
    if(root == NULL)
        return;
    InOrderTraversal(root->left);
    printf("%c ",*(root->val));
    InOrderTraversal(root->right);
}
int main()
{
    char ch[100] = "\0";
    BTNode *root;
    while (fgets(ch,100,stdin) != NULL)
    {
        int i = 0;
        size_t len = strlen(ch);
        len = len - 1;
        PrevTreePush(ch,&root,&i,len);
        InOrderTraversal(root);
    }

    return 0;
}

#include<stdio.h>
#include<stdlib.h>

typedef struct BTNode
{
    char val;
    struct BTNode* left;
    struct BTNode* right;
}BTNode;

struct BTNode* BinaryTreeCreate(char* p,int* k)
{
    if(p[*k] == '#')
    {
        (*k)++;
        return NULL;
    }
    
    BTNode* tmp=(BTNode*)malloc(sizeof(BTNode));
    if(tmp == NULL)
    {
        exit(-1);
    }
    tmp->val=p[*k];
    (*k)++;

    tmp->left=BinaryTreeCreate(p,k);
    tmp->right=BinaryTreeCreate(p,k);
    
    return tmp;
    
}
void Inorder(struct BTNode* root)
{
    if(root == NULL)
        return;
    Inorder(root->left);
    printf("%c ",root->val);
    Inorder(root->right);
    
}

int main()
{
    char c[101];
    while(scanf("%s",c) != EOF)
    {
        int k=0;
        BTNode* root=BinaryTreeCreate(c,&k);
        Inorder(root);
         
    }
    
    
    return 0;
}

#include<stdio.h>
typedef struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
}TNode;
TNode* CreateTree(char* str,int* i)
{
    if(str[*i]=='#')
    {
        (*i)++;
        return NULL;
    }
    TNode* root=(TNode*)malloc(sizeof(TNode));
    if(root==NULL)
    {
        exit(-1);
    }
    root->val=str[*i];
    (*i)++;
    root->left=CreateTree(str,i);
    root->right=CreateTree(str, i);
    return root;
}
void InOrder(TNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
int main()
{
    char str[100]={0};
    scanf("%s",str);
    int i=0;
    TNode* root=CreateTree(str,&i);//字符串前序遍历二叉树
    InOrder(root);//对二叉树进行中序遍历，输出遍历结果。
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TNode;
TNode* BuildTree(char tree[],int* pi)
{
    if(tree[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    TNode* root = (TNode*)malloc(sizeof(TNode));
    if(root == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    root->val = tree[*pi];
    (*pi)++;
    root->left = BuildTree(tree, pi);
    root->right = BuildTree(tree, pi);
    
    return root ;
}
void InOrder(TNode* root)
{
    if(root == NULL)
        return;
    InOrder(root ->left);
    printf("%c ",root ->val);
    InOrder(root ->right);
}
int main()
{
    char tree[100] = {0};
    scanf("%s",tree);
    int i = 0;
    TNode* node = BuildTree(tree,&i);
    InOrder(node);
    
    return 0;
}

• 中序遍历的访问步骤：
  • （1）沿着根的左孩子，依次入栈，直到左孩子为空。
  • （2）此时，栈顶元素出栈并访问：如果栈顶元素的右孩子为空，继续弹栈；如果右孩子不为空，则将右孩子入栈，继续执行（1）。
• 先序遍历只是在元素入栈时访问，其他步骤与中序遍历相同。
• 于是将先序序列的每个元素入栈，某个元素后面是#号时，表明它的左孩子为空，将其弹栈访问，如果后面还有#号，表明它的右孩子也为空，继续弹栈。整个过程中的弹栈访问序列即中序序列。

#include <cstdio>
#include <cstring>
#include <stack>

char pre[101];

int main()
{
    while (scanf("%s", pre) != EOF)
    {   
        std::stack<char> s;
        for (size_t i = 0; i < strlen(pre); i++)
        {
            if (pre[i] != '#')
                s.push(pre[i]);
            else
            {
                if (!s.empty())
                {
                    printf("%c ", s.top());
                    s.pop();
                }
            }
        }
        printf("\n");
    }   
    return 0;
} 

//参考了题解 
#include<stdio.h>
#include <stdlib.h>
const int N1=1e8+5;
const int N2=1e2+5;
int pos,len,t;//pos记录的是树的编号，t记录的是字符串的位置
char tree[N1];
char str[N2];

void create(int pos){
    char c=str[t++];
    if(c=='#'){
        return ;
    }
    tree[pos]=c;
    create(2*pos);//递归创建左子树
    create(2*pos+1);
}
void order(int root){
    if(tree[root]==0)
        return ;
    order(2*root);
    printf("%c",tree[root]);
    order(2*root+1);
}
int main(){
    while(scanf("%s",str)!=EOF){
        t=0;
        create(1);
        inorder(1);
    }
    return 0;
}
//或者用指针
#include <stdio.h>
#include <stdlib.h>
const int N=1e3+5;
int pos;
char str[N];
typedef struct treenode{
    char data;
    struct treenode* leftchild;
    struct treenode* rightchild;
    //treenode(char c):data(c),leftchild(NULL),rightchild(NULL){};
}treenode;
treenode *create(){
    char c=str[pos++];
    if(c=='#'){
        return NULL;
    }
    treenode *root=(treenode*)malloc(sizeof(treenode));
    root->data=c;
    root->leftchild=create();
    root->rightchild=create();
    return root;
}
void inorder(treenode *root){
    if(root==NULL){
        return ;
    }
    inorder(root->leftchild);
    printf("%c ",root->data);
    inorder(root->rightchild);
}
int main(){
    while(scanf("%s",&str)!=EOF){
        pos=0;
        treenode *root=(treenode*)malloc(sizeof(treenode));
        root=create();
        inorder(root);
    }
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
char string[maxsize];
int i=0;
typedef struct tnode{
	struct tnode*left;
	struct tnode*right;
	char ch;
}tnode;
int build(tnode*Node){
	tnode *node;
	int tag1=0,tag2=0;
	i++;
	if(string[i-1]=='\0')
        exit(0);
	if(string[i-1]!='#'){
		Node->ch=string[i-1];
		Node->left=(tnode*)malloc(sizeof(tnode));
		tag1=build(Node->left);
		if(tag1==-1) Node->left=NULL;
		Node->right=(tnode*)malloc(sizeof(tnode));
		tag2=build(Node->right);
		if(tag2==-1) Node->right=NULL;
        return 0;
	}
	else
		return -1;
}
void midspan(tnode*Node){
	if(Node!=NULL){
		midspan(Node->left);
		printf("%c ",Node->ch);
		midspan(Node->right);
	}
	else return;
}
int main(){
	tnode *Node;
	int j=0,tag;
	char c;
	Node=(tnode*)malloc(sizeof(tnode));
	while(scanf("%c",&c)!=EOF){
		string[j++]=c;
		while((c=getchar())!='\n')
		    string[j++]=c;
	    string[j]='\0';
	    tag=build(Node);
	    midspan(Node);
	    printf("\n");
	}
}

#include<stdio.h>
#include<stdlib.h>

char *g;//全局变量，指针g用来遍历字符串

typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//递归建树，利用指针g读取字符并写入根结点数据域然后返回根结点
BiTree TreeBuild(){
    if(*g=='#'){//读到#返回NULL
        g++;//指针后移
        return NULL;
    }
    else{//读到其它值
        BiTNode *s=(BiTNode*)malloc(sizeof(BiTNode));//创建空节点
        s->data=*g;//写入数据
        g++;//指针后移
        s->lchild=TreeBuild();//创建左子树
        s->rchild=TreeBuild();//创建右子树
        return s;//返回根结点
    }
}
//递归打印中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        printf("%c ",T->data);
        InOrder(T->rchild);
    }
}

int main(){
    char Q[100];
    int n;
    scanf("%s",Q);//输入字符串
    g=Q;//指针归零
    BiTree T=TreeBuild();//建树
    InOrder(T);//遍历输出
    printf("\n");
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
	char val;
	struct TreeNode*left;
	struct TreeNode*right;
}TNode;
void CreateTree(char*a, int* pi,TNode**root)
{
	if (a[*pi] != '#')
	{
		TNode*p = (TNode*)malloc(sizeof(TNode));
		p->val = a[*pi];
        ++(*pi);
		*root = p;
	}
	else
    {
        ++(*pi);
	    *root = NULL;
        return;
    }
	CreateTree(a, pi,&(*root)->left);
	CreateTree(a, pi, &(*root)->right);
}
void Inorder(TNode*root)
{
	if (root == NULL)
		return;
	Inorder(root->left);
	printf("%c ", root->val);
	Inorder(root->right);
}
int main()
{
	char str[100];
	scanf("%s", str);
	int i = 0;
	TNode*root=NULL;
	CreateTree(str, &i, &root);
	Inorder(root);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct TreeNode {
  ElemType data;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *BT;

// =============== function prototype ==============
void CreateTree(BT* bt);
void InOrderTraversal(BT bt, void (*visit) (TreeNode*));
// =============== function prototype ==============

void output(TreeNode* node) {
  fprintf(stdout, "%c ", (*node).data);
}

int main(const int argc, const char** const argv) {
  BT bt = NULL;  
  CreateTree(&bt);
  InOrderTraversal(bt, output);
  return 0;
}

// 只有深入理解二叉树及扩展二叉树, 二级指针和堆栈内存等知识。才能写出这短小精悍的函式！
void CreateTree(BT* bt) {
  char ch;
  fscanf(stdin, "%c", &ch);
  if (ch == '#') {
    *bt = NULL;
    return;
  }
  *bt = (TreeNode*) malloc(sizeof(TreeNode));
  (*bt)->data = ch;
  CreateTree(&(*(*bt)).left);
  CreateTree(&(*(*bt)).right);
}

void InOrderTraversal(BT bt, void (*visit) (TreeNode*)) {
  if (!bt) return;
  InOrderTraversal(bt->left,  visit);
  output(bt);
  InOrderTraversal(bt->right, visit);
}