分类： IT业界
2011-06-09 15:17:29
1、 数据结构
struct BiTree
{
char data;
struct BiTree *leftchild;
struct BiTree *rightchild;
};
2、先序构造树
struct BiTree *CreateBiTree(struct BiTree *T)
{
char ch;
ch = getchar();
getchar();
if (ch == '#')
{
T = NULL;
return T;
}
T = new struct BiTree;
T->data = ch;
T->leftchild = CreateBiTree(T->leftchild);
T->rightchild = CreateBiTree(T->rightchild);
return T;
}
2、递归先序遍历树
void PreVisit(struct BiTree *T)
{
if (T == NULL)
{
return;
}
else
{
printf("%c ", T->data);
PreVisit(T->leftchild);
PreVisit(T->rightchild);
}
}
3、递归中序遍历树
void MidVisit(struct BiTree *T)
{
if (T == NULL)
{
return;
}
else
{
MidVisit(T->leftchild);
printf("%c ", T->data);
MidVisit(T->rightchild);
}
}
4、递归后序遍历树
void AfterVisit(struct BiTree *T)
{
if (T == NULL)
{
return;
}
else
{
AfterVisit(T->leftchild);
AfterVisit(T->rightchild);
printf("%c ", T->data);
}
}
5、递归删除树
void DelBiTree(struct BiTree *T)
{
if (T == NULL)
{
return;
}
else
{
if (T->leftchild != NULL)
{
DelBiTree(T->leftchild);
}
if (T->rightchild != NULL)
{
DelBiTree(T->rightchild);
}
delete T;
}
}
6、二叉树节点插入，value小于等于root->data，则插入到左子树，否则插入到右子树
struct BiTree *InsertBiTree(struct BiTree *root, int value)
{
struct BiTree *newNode;
if (root == NULL)
{
newNode = new struct BiTree;
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (value <= root->data)
{
root->left = InsertBiTree(root->left, value);
}
else
{
root->right = InsertBiTree(root->right, value);
}
return root;
}
7、中序非递归遍历二叉树
void MidVisit(struct BiTree *T)
{
struct BiTree *p;
struct Stack S;
S = CreateStack();
S = Push(S, T);
while (!EmptyStack(S))
{
while ((p = GetTop(S)) && p)
{
S = Push(S, p->leftchild);
}
S = Pop(S, p);
if (!EmptyStack(S))
{
S = Pop(S, p);
printf("%c ", p->data);
S = Push(S, p->rightchild);
}
}
printf("\n");
DelStack(S);
}
8、先序非递归遍历二叉树
void PreVisit(struct BiTree *T)
{
struct BiTree *p;
struct Stack S;
S = CreateStack();
S = Push(S, T);
while (!EmptyStack(S))
{
while ((p = GetTop(S)) && p)
{
printf("%c ", p->data);
S = Push(S, p->leftchild);
}
S = Pop(S, p);
if (!EmptyStack(S))
{
S = Pop(S, p);
S = Push(S, p->rightchild);
}
}
printf("\n");
DelStack(S);
}
