树和二叉树.cpp

（1）输入字符序列

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

#define MAX 100
#define OVERFLOW 0
#define OK 1
typedef char ElemType;
typedef ElemType TElemType;  

typedef struct node{ 
	TElemType data;
	struct node *lchild,*rchild;
}BinTNode;

typedef enum PointerTag{Link,Thread};
typedef struct BiThrNode{
	TElemType data;
	struct BiThrNode *lchild,*rchild;
    PointerTag LTag,RTag;
}BiThrNode;

typedef BinTNode *BinTree;
typedef BiThrNode *BiThrTree;
BiThrTree pre;
int num_leaf=0;
                                                                    
void CreateBinTree(BinTree &T)       //二叉树的建立
{
	char ch;
	cin>>ch;
	
	if(ch=='@')
		T=NULL;
	else
	{
		T=(BinTNode *)malloc(sizeof(BinTNode));
		T->data=ch;
		CreateBinTree(T->lchild);
		CreateBinTree(T->rchild);
	}
}

void Inorder(BinTree T){          //二叉树的中序递归便历
	if(T){
		Inorder(T->lchild);
		printf("%3c",T->data);
		Inorder(T->rchild);
	}
}

void InorderN(BinTree T){         //二叉树的中序非递归便历
	BinTree stack[MAX],p;
    int top=0;
	p=T;
	do
	{
		while(p!=NULL)
		{
			stack[top]=p;
			top++;
			p=p->lchild;
		}
		if(top>0)
		{
			top--;
			p=stack[top];
			printf("%3c",p->data);
			p=p->rchild;
		}
	}while(p!=NULL||top!=0);
}

void print_cengci(BinTree T)//层次遍历二叉树
{
	BinTree stack[MAX],p;
	int top=0,base=0;
	if(T)
	{
		p=T;
		stack[base]=p;
		base++;
		while(top!=base)
		{
			printf("%3c",stack[top]->data);
			if(stack[top]->lchild)
			{
				stack[base]=stack[top]->lchild;
				base++;
			}
			if(stack[top]->rchild)
			{
				stack[base]=stack[top]->rchild;
				base++;
			}
			top++;
		}
	}
}

int PostTreeDepth(BinTree T)  //求二叉树的高度