各种基本算法实现小结（三）—— 树与二叉树

各种基本算法实现小结（三）—— 树与二叉树

（均已测试通过）

===================================================================

二叉树——先序

测试环境：VC 6.0 (C)

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct _node
{
    char data;
    struct _node *lchild;
    struct _node *rchild;
};
typedef struct _node node, *pnode;
pnode create_tree()
{
    pnode pt;
    char data;
    scanf("%c", &data);
    getchar();
    if(data==' ')
        pt=NULL;
    else
    {
        pt=(pnode)malloc(sizeof(node));
        pt->data=data;
        pt->lchild=create_tree();
        pt->rchild=create_tree();
    }
    return(pt);
}
void print_pretree(pnode ps)
{
    if(ps != NULL)
    {
        printf("%3c", ps->data);
        print_pretree(ps->lchild);
        print_pretree(ps->rchild);
    }	
}
void main()
{
    pnode ps;
    ps=create_tree();
    print_pretree(ps);
	printf("/n");
}

运行结果：

===========================================================

二叉树——各种操作

测试环境：VC 6.0 (C)

#include <stdio.h>
#include <malloc.h>
struct _node
{
    char data;
    struct _node *lchild;
    struct _node *rchild;
};
typedef struct _node node, *pnode;
int count_l=0;  /* count leaf */
int count_n=0;  /* count node */
pnode create_tree()
{
    pnode pt;
    char data;
    scanf("%c", &data);
    getchar();
    if(data==' ')
        pt=NULL;
    else
    {
        pt=(pnode)malloc(sizeof(node));
        pt->data=data;
        pt->lchild=create_tree();
        pt->rchild=create_tree();
    }
    return(pt);
}
void print_pretree(pnode ps)
{
    if(ps != NULL)
    {
        printf("%3c", ps->data);
        print_pretree(ps->lchild);
        print_pretree(ps->rchild);
    }	
}
void print_midtree(pnode ps)
{
	if(ps != NULL)
	{
		print_midtree(ps->lchild);
	
		printf("%3c", ps->data);
		print_midtree(ps->rchild);	
	}
}
void print_posttree(pnode ps)
{
	if(ps != NULL)
	{
		print_posttree(ps->lchild);
		print_posttree(ps->rchild);
		printf("%3c", ps->data);
	}
}
int count_leaf(pnode ps)
{	
	if(ps != NULL)
	{
		if(ps->lchild == NULL && ps->rchild == NULL)
		count_l++;	
		count_leaf(ps->lchild);
		count_leaf(ps->rchild);
	}
	return count_l;
}
int count_node(pnode ps)
{
	if(ps != NULL)
	{
		count_n++;
		count_node(ps->lchild);
		count_node(ps->rchild);
	}
	return count_n;
}
int count_depth(pnode ps)
{
	int ldep, rdep;
	if(ps == NULL)
		return 0;
	else
	{
		ldep=count_depth(ps->lchild);
		rdep=count_depth(ps->rchild);
		
		return ldep>rdep ? (ldep+1) : (rdep+1);
	}
}
void main()
{
    pnode ps;
    ps=create_tree();
	
	printf("pre order.../n");
    print_pretree(ps);
	printf("/n");
	printf("mid order.../n");
	print_midtree(ps);
	printf("/n");
	printf("post order.../n");
	print_posttree(ps);
	printf("/n");
	printf("number of leaf is: %d/n", count_leaf(ps));
	printf("number of node is: %d/n", count_node(ps));
	printf("max  of  depth is: %d/n", count_depth(ps));
}

运行结果：

===========================================================

二叉树——先序、中序、后序的递归与非递归实现

测试环境：VS2008 (C)

#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define DataType char
/**************************************/
/********     树的结构定义     ********/
/**************************************/
struct _tree
{
	DataType data;
	struct _tree *lchild;
	struct _tree *rchild;
};
typedef struct _tree tree, *ptree;
/**************************************/
/********     栈的结构定义     ********/
/**************************************/
struct _node
{
	ptree pt;
	struct _node *next;
};
typedef struct _node node, *pnode;
struct _stack
{
	int size;
	pnode ptop;
};
typedef struct _stack stack, *pstack;
/**************************************/
/********     堆的结构定义     ********/
/**************************************/
struct _queue
{
	pnode front;
	pnode rear;
};
typedef struct _queue queue, *pqueue;
/**************************************/
/********     栈的数据操作     ********/
/**************************************/
pstack init_stack()
{
	pnode pn=NULL;
	pstack ps=NULL;
	pn=(pnode)malloc(sizeof(node));
	ps=(pstack)malloc(sizeof(stack));
	pn->pt=NULL;
	pn->next=NULL;
	ps->ptop=pn;
	return ps;
}
int empty_stack(pstack ps)
{
	if(ps->ptop->next==NULL)
		return 1;
	else
		return 0;
}
void push_stack(pstack ps, ptree pt) /* flag for post tree: 0 for lchild; 1 for rchild */
{
	pnode pn=NULL;
	pn=(pnode)malloc(sizeof(node));
	pn->pt=pt;
	pn->next=ps->ptop;
	ps->ptop=pn;
}
ptree pop_stack(pstack ps)
{
	ptree pt=NULL;
	pnode pn=NULL;
	if(!empty_stack(ps))
	{
		pn=ps->ptop;
		ps->ptop=ps->ptop->next;
		pt=pn->pt;
		free(pn);
	}
	return pt;
}
ptree gettop_stack(pstack ps)
{
	if(!empty_stack(ps))
		return ps->ptop->pt;
}
/**************************************/
/********     堆的数据操作     ********/
/**************************************/
queue init_queue()
{
	pnode pn=NULL;
	queue qu;
	pn=(pnode)malloc(sizeof(node));
	pn->pt=NULL;
	pn->next=NULL;
	qu.front=qu.rear=pn;
	return qu;
}
int empty_queue(queue qu)
{
	if(qu.front==qu.rear)
		return 1;
	else
		return 0;
}
void en_queue(queue qu, ptree pt)
{
	pnode pn=NULL;
	pn=(pnode)malloc(sizeof(node));
	pn->pt;
	pn->next=qu.rear->next;
	qu.rear=pn;
}
ptree de_queue(queue qu)
{
	ptree pt=NULL;
	pnode pn=NULL;
	if(!empty_queue(qu))
	{
		pn=qu.front;
		qu.front=qu.front->next;
		pt=pn->pt;
		free(pn);
	}
	return pt;
}
/**************************************/
/********     堆的数据操作     ********/
/**************************************/
ptree init_tree()
{
	ptree pt=NULL;
	pt=(ptree)malloc(sizeof(tree));
	pt->data='0';
	pt->lchild=NULL;
	pt->rchild=NULL;
	return pt;
}
ptree create_tree()
{
	char ch;
	ptree pt=NULL;
	
	scanf("%c", &ch);
	getchar();	
	if(ch==' ')
		return NULL;
	else
	{
		pt=(ptree)malloc(sizeof(tree));
		pt->data=ch;
		pt->lchild=create_tree();
		pt->rchild=create_tree();
	}
	return pt;
}
void print_pretree(ptree pt)
{
	if(pt!=NULL)
	{
		printf("%3c", pt->data);
		print_pretree(pt->lchild);
		print_pretree(pt->rchild);
	}
}
void print_pretree2(ptree pt)
{
	pstack ps=NULL;
	ptree p=NULL;
	ps=init_stack();
	p=pt;
	while(p!=NULL || !empty_stack(ps))
	{
		while(p!=NULL)
		{
			printf("%3c", p->data);
			push_stack(ps, p);
			p=p->lchild;
		}
		if(!empty_stack(ps))
		{
			p=pop_stack(ps);
			p=p->rchild;
		}
	}
}
void print_midtree(ptree pt)
{
	if(pt!=NULL)
	{
		print_midtree(pt->lchild);
		printf("%3c", pt->data);
		print_midtree(pt->rchild);
	}
}
void print_midtree2(ptree pt)
{
	pstack ps=NULL;
	ptree p=NULL;
	ps=init_stack();
	p=pt;
	while (p!=NULL || !empty_stack(ps))
	{
		while(p!=NULL)
		{
			push_stack(ps, p);
			p=p->lchild;		
		}
		if(!empty_stack(ps))
		{			
			p=pop_stack(ps);
			printf("%3c", p->data);
			p=p->rchild;
		}
	}
}
void print_posttree(ptree pt)
{
	if(pt!=NULL)
	{
		print_posttree(pt->lchild);		
		print_posttree(pt->rchild);	
		printf("%3c", pt->data);
	}
}
void print_posttree2(ptree pt)
{
	pstack ps=NULL;
	ptree p=NULL;
	ptree p2=NULL;
	ptree lastvisit=NULL;
	ps=init_stack();
	p=pt;
	while (p!=NULL || !empty_stack(ps))
	{
		while(p!=NULL)
		{
			push_stack(ps, p);
			p=p->lchild;					
		}
		p2=gettop_stack(ps); /* top: rchild==null or sub_root */
		if(p2->rchild==NULL || p2->rchild==lastvisit)
		{
			printf("%3c", p2->data);
			lastvisit=pop_stack(ps); /* pop */
		}
		else
			p=p2->rchild;
	}	
}
int _tmain(int argc, _TCHAR* argv[])
{
	ptree pt=NULL;
	/*pt=init_tree();*/
	
	printf("Create recursion tree.../n");
	pt=create_tree();
	/************  recursion ************/
	printf("/n/nrecursion...");
	printf("/npre tree.../n");
	print_pretree(pt);
	printf("/nmid tree.../n");
	print_midtree(pt);
	printf("/npost tree.../n");
	print_posttree(pt);
	/************  stack ************/
	printf("/n/nstack, non recursion...");
	printf("/npre tree.../n");
	print_pretree2(pt);
	printf("/nmid tree.../n");
	print_midtree2(pt);
	printf("/npost tree.../n");
	print_posttree2(pt);
	printf("/n");
	return 0;
}

运行结果：

===========================================================

二叉树——学习交流与修正改进

在网上看到了好多人转载这段代码，我也复制、粘贴下来学习

但在VC6.0编译器上运行并未通过，于是调试修正了几个小bug

测试运行通过后的代码粘贴如下，希望对大家学习有所帮助，谢谢！

本算法源码引用网址：http://www.ccrun.com/article.asp?i=292&d=y6y12h （二叉树实现源代码）

测试环境：VC 6.0 (C)

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
typedef int status;
typedef struct BiNode
{
    char Data;
    struct BiNode* lChild;
    struct BiNode* rChild;
}BiNode,*pBiNode;
status CreateTree(BiNode** pTree);
status PreOrderTraval(BiNode* pTree);
status InOrderTraval(BiNode* pTree);
status PostOrderTraval(BiNode* pTree);
status Visit(char Data);
status ShowLeaves(BiNode* pTree);
status DelTree(BiNode* pTree);
status Display(BiNode* pTree,int Level);
status Clear(BiNode* pTree);
BiNode *pRoot=NULL;
void main()
{
    CreateTree(&pRoot);
    printf("/nPreOrder:");
    PreOrderTraval(pRoot);
    printf("/n");
    printf("/nInOrder:");
    InOrderTraval(pRoot);
    printf("/n");
    printf("/nPostOrder:");
    PostOrderTraval(pRoot);
    printf("/n");
    printf("/nShowLeaves:");
    ShowLeaves(pRoot);
    printf("/n-----------------------/n");
    printf("/n");
    Display(pRoot,0);
    printf("/n");
    printf("/nDeleting Tree:/n");
    DelTree(pRoot);
    printf("BiTree Deleted.");
}
status CreateTree(BiNode** pTree) 
{
    char ch;
    scanf("%c",&ch);
	getchar();
	
    if(ch==' ')  /* NOTE: enter space, example: [ab  cd  e  ] */
    {
        (*pTree)=NULL;
    }
    else
    {
        if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode))))
        {
            exit(OVERFLOW);
        }
        (*pTree)->Data=ch;
        CreateTree(&((*pTree)->lChild));
        CreateTree(&((*pTree)->rChild));
    }
return OK;
}
status PreOrderTraval(BiNode* pTree)
{
    if(pTree)
    {
        if(Visit(pTree->Data))
        {
            if(PreOrderTraval(pTree->lChild))
            {
                if(PreOrderTraval(pTree->rChild))
                {
                    return OK;
                }
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}
status InOrderTraval(BiNode* pTree)
{
    if(pTree)
    {
        if(InOrderTraval(pTree->lChild))
        {
            if(Visit(pTree->Data))
            {
                if(InOrderTraval(pTree->rChild))
                {
                    return OK;
                }
            }
            return ERROR;
        }
        return ERROR;
    }
    else
        return OK;
}
status PostOrderTraval(BiNode* pTree)
{
    if(pTree)
    {
        if(PostOrderTraval(pTree->lChild))     
        {
            if(PostOrderTraval(pTree->rChild)) 
            {
                if(Visit(pTree->Data))
                {
                    return OK;
                }
                return ERROR;
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}
status Visit(char Data)
{
    printf("%c",Data);
    return OK;
}
status Display(BiNode* pTree,int Level)
{
    int i;
    if(pTree==NULL) 
		return FALSE;
    Display(pTree->lChild,Level+1);
    for(i=0;i<Level-1;i++)
    {
        printf(" ");
    }
    if(Level>=1)
    {
        printf("--");
    }
    printf("%c/n",pTree->Data);
    Display(pTree->rChild,Level+1);
	return TRUE;
}
status ShowLeaves(BiNode* pTree)
{
    if(pTree)
    {
        if(ShowLeaves(pTree->lChild))
        {
            if(ShowLeaves(pTree->rChild))
            {
                if((pTree->lChild==NULL)&&(pTree->rChild==NULL))
                {
                    if(!Visit(pTree->Data))
                    {
                        return ERROR;
                    }
                } 
                return OK;
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}
status DelTree(BiNode* pTree)
{
    if(pTree)
    {
        if(DelTree(pTree->lChild))
        {
            if(DelTree(pTree->rChild))
            {
                printf("Deleting %c/n",pTree->Data);
                free((void*)pTree);
                return OK;
            }
        }
        return ERROR;
    }
    else
        return OK;
} 

运行结果：

===========================================================

上述代码改进后，逻辑更清晰，并添加了计算二叉树层次的函数 ShowDepth(BiNode* pTree)

具体代码如下：

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
typedef int status;
typedef struct BiNode
{
    char Data;
    struct BiNode* lChild;
    struct BiNode* rChild;
}BiNode,*pBiNode;
status CreateTree(BiNode** pTree);
status PreOrderTraval(BiNode* pTree);
status InOrderTraval(BiNode* pTree);
status PostOrderTraval(BiNode* pTree);
status Visit(char Data);
status ShowLeaves(BiNode* pTree);
status ShowDepth(BiNode* pTree);
status DelTree(BiNode* pTree);
status Display(BiNode* pTree,int Level);
status Clear(BiNode* pTree);
BiNode *pRoot=NULL;
void main()
{
    CreateTree(&pRoot);
    printf("/nPreOrder:");
    PreOrderTraval(pRoot);
    printf("/n");
    printf("/nInOrder:");
    InOrderTraval(pRoot);
    printf("/n");
    printf("/nPostOrder:");
    PostOrderTraval(pRoot);
    printf("/n");
    printf("/nShowLeaves:");
    ShowLeaves(pRoot);
	printf("/nShowDepth:%d/n", ShowDepth(pRoot));
    printf("/n------------------/n");
    printf("/n");
    Display(pRoot,0);
    printf("/n");
    printf("/nDeleting Tree:/n");
    DelTree(pRoot);
    printf("BiTree Deleted.");
}
status CreateTree(BiNode** pTree) 
{
    char ch;
    scanf("%c",&ch);
	getchar();
	
    if(ch==' ')  /* NOTE: enter space, example: [ab  cd  e  ] */
        (*pTree)=NULL;
    else
    {
        if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode))))
            exit(OVERFLOW);
        (*pTree)->Data=ch;
        CreateTree(&((*pTree)->lChild));
        CreateTree(&((*pTree)->rChild));
    }
	return OK;
}
status PreOrderTraval(BiNode* pTree)
{
    if(pTree)
    {
		Visit(pTree->Data);
		PreOrderTraval(pTree->lChild);
		PreOrderTraval(pTree->rChild);
    }
    return OK;
}
status InOrderTraval(BiNode* pTree)
{
    if(pTree)
    {
		InOrderTraval(pTree->lChild);
		Visit(pTree->Data);
		InOrderTraval(pTree->rChild);
    }
    
	return OK;
}
status PostOrderTraval(BiNode* pTree)
{
    if(pTree)
    {
		PostOrderTraval(pTree->lChild);    
		PostOrderTraval(pTree->rChild);   
		Visit(pTree->Data);
    }
    
	return OK;
}
status Visit(char Data)
{
    printf("%c",Data);
    return OK;
}
status Display(BiNode* pTree,int Level)
{
    int i;
    if(pTree==NULL) 
		return FALSE;
    Display(pTree->lChild,Level+1);
    for(i=0;i<Level-1;i++)
    {
        printf(" ");
    }
    if(Level>=1)
    {
        printf("--");
    }
    printf("%c/n",pTree->Data);
    Display(pTree->rChild,Level+1);
	return TRUE;
}
status ShowLeaves(BiNode* pTree)
{
    if(pTree)
    {
		ShowLeaves(pTree->lChild);
		ShowLeaves(pTree->rChild);
        if((pTree->lChild==NULL)&&(pTree->rChild==NULL))
			Visit(pTree->Data);
	}
    
	return OK;
}
status ShowDepth(BiNode* pTree)
{
	int ldep=0, rdep=0;
	
	if(!pTree)
		return 0;
	else
	{
		ldep=ShowDepth(pTree->lChild);
		rdep=ShowDepth(pTree->rChild);
		return ldep>rdep ? (ldep+1) : (rdep+1);
	}
}
status DelTree(BiNode* pTree)
{
    if(pTree)
    {
		DelTree(pTree->lChild);
		DelTree(pTree->rChild);
        printf("Deleting %c/n",pTree->Data);
        free((void*)pTree);
	}
    return OK;
} 

运行结果：

===========================================================

参考推荐：

学习算法之路

各种基本算法实现小结（一）—— 链 表

各种基本算法实现小结（二）—— 堆 栈

各种基本算法实现小结（三）—— 树与二叉树

各种基本算法实现小结（四）—— 图及其遍历

各种基本算法实现小结（五）—— 排序算法

各种基本算法实现小结（六）—— 查找算法

各种基本算法实现小结（七）—— 常用算法

12个有趣的C语言面试题