树的一些基本用法

痛定思痛。 2022-05-03 09:28 242阅读 0赞

我们用先序创建树，算出它的先序，中序和后序，然后计算他的结点和叶子结点

最后计算树的深度。

**目录**

##                                                                       *** 树的基本用法*** ##

*  先序
 *  中序
 *  后序

先序遍历就是先遍历根结点再遍历左右孩子，所以这课树的先序遍历就是

ABC\#\#D\#E\#G\#\#F\#\#\#

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 20
    typedef struct BTNode{
    	char data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }*BiTree;
    
    void createBiTree( BiTree *t ) {
    	char s;
    	BiTree q;
    	s = getchar();
    	if ( s == '#') {
    		*t = NULL;
    		return;
    	}
    	q = ( BiTree )malloc( sizeof( struct BTNode ) );
    	if ( q == NULL ) {
    		printf("Memony alloc failure!");
    		exit(0);
    	}
    	q->data = s;
    	*t = q;
    	createBiTree( &q->lchild );
    	createBiTree( &q->rchild );
    }
    
    void preOrder( BiTree p ) {		//先序遍历二叉树
    	if ( p != NULL ) {
    		printf("%c", p->data );
    		preOrder( p->lchild );
    		preOrder ( p->rchild );
    	}
    }
    
    void InOrder( BiTree p ) {//中序遍历二叉树
    	if ( p != NULL ) {
    		InOrder ( p->lchild );
    		printf("%c", p->data );
    		InOrder( p->rchild );
    	}
    }
    
    //后序遍历二叉树
    void PostOrder( BiTree p ) {
    	if ( p != NULL ) {
    		PostOrder( p->lchild );
    		PostOrder( p->rchild );
    		printf("%c", p->data );
    	}
    }
    
    //先序遍历的非递归算法
    void preOrder_n( BiTree p ) {
    	BiTree stack[MAX],q;
    	int top = 0,i;
    	for ( i = 0; i < MAX; i++ )
    		stack[i] = NULL;
    	q = p;
    	while ( q != NULL ) {
    		printf("%c",q->data );
    		if ( q->rchild != NULL )
    			stack[top++] = q->rchild;
    		if ( q->lchild != NULL )
    			q = q->lchild;
    		else
    			if ( top > 0 )
    				q = stack[--top];
    			else
    				q = NULL;
    	}
    }
    
    //释放二叉树
    void release( BiTree t ) {
    	if ( t != NULL ) {
    		release( t->lchild );
    		release( t->rchild );
    		free(t);
    	}
    }
    
    //结点个数
    int NodeCount( BiTree t ) {
    	if ( t == NULL )
    		return 0;
    	else
    		return NodeCount( t->lchild ) + NodeCount( t->rchild ) + 1;
    }
    
    //叶子结点
    int LeafNode( BiTree t ) {
    	if ( t == NULL )
    		return 0;
    	if ( t->lchild == NULL && t->rchild == NULL )
    		return 1;
    	return ( LeafNode( t->lchild ) + LeafNode( t->rchild ) );
    }
    
    //计算树的深度
    int Depth( BiTree t ) {
    	int n = 0, m = 0;
    	if ( t == NULL )
    		return 0;
    	else {
    		m = Depth( t->lchild );
    		n = Depth ( t->rchild );
    		if ( m > n )	return ( m + 1 );
    		else	return ( n + 1 );
    	}
    }
    
    int main()
    {
    	BiTree t = NULL;
    	printf("\nplease input data:(exit for #)\n");
    	createBiTree( &t );
    	int ret = 0;
    	ret = NodeCount( t );
    	printf("\n\nthe tree number is: %d", ret );
    	int ret2 = 0;
    	ret2 = LeafNode( t );
    	printf("\n\nthe Leaf Node is: %d ", ret2 );
    	int ret3 = 0;
    	ret3 = Depth( t );
    	printf("\n\nthe tree depth is: %d", ret3 );
    	printf("\n\nPreOrder the tree is:");
    	preOrder( t );
    	printf("\n\nInOrder the tree is:");
    	InOrder( t );
    	printf("\n\nPostOrder the tree is:");
    	PostOrder( t );
    	printf("\n\n先序遍历序列（非递归) :");
    	preOrder_n( t );
    	release( t );
    
    	return 0;
    }

--------------------