数据结构实训二:二叉树常用算法

定义一个数据域为字符型的二叉链表，用递归方法编程实现如下功能：
（1）设计一个CreatBiTree函数，实现通过按照扩展的先序遍历序列（#代表空结点）创建二叉链表。
（2）设计一个算法实现输出二叉树的先序遍历结果。
（3）设计一个算法实现输出二叉树的中序遍历结果。
（4）设计一个算法实现输出二叉树的后序遍历结果。
（5）设计一个算法计算二叉树的深度；
（6）设计一个算法统计二叉树的叶结点个数；
（7）设计一个算法统计二叉树的度为1的结点个数；
测试用树:

实现结果:

代码:

#include<iostream>

using namespace std;

typedef struct BiTNode {
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T);//(1)先序创建二叉树
void PreOrderTraverse(BiTree T);//(2)先序遍历 
void InOrderTraverse(BiTree T);//(3)中序遍历
void PostOrderTraverse(BiTree T);//(4)后序遍历
int Depth(BiTree T);//(5)计算二叉树的深度
int Countleaf(BiTree T);//(6)统计二叉树的叶子结点个数
int NodeNumber1(BiTree T);//(7)统计二叉树度为1的结点个数 

int main()
{
	BiTree T;
	BiTree A;

	cout << "(1)先序创建二叉树"<<endl;
	cout<<"请输入二叉树各个结点(结点之间用空格表示,#代表空结点):";
	CreateBiTree(T);
	cout << endl;

	cout << "(2)先序遍历结果:";
	PreOrderTraverse(T);
	cout << endl;

	cout << "(3)中序遍历结果:";
	InOrderTraverse(T);
	cout << endl;

	cout << "(4)后序遍历结果:";
	PostOrderTraverse(T);
	cout << endl;


	cout << "(5)二叉树T的深度为：";
	cout << Depth(T) << endl;
	cout<<"(6)二叉树的叶子结点个数为："<<Countleaf(T) << endl; 
	
	cout<<"(7)二叉树度为1的结点个数为:" ;
	
	cout<<NodeNumber1(T)<<endl<< endl << endl ; 
	
	system("Pause");
	return 0;
}
void CreateBiTree(BiTree &T)
{//(1)先序创建二叉树
	char ch;
	cin >> ch;
	if (ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = new BiTNode;
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

void PreOrderTraverse(BiTree T)
{//(2)先序遍历
	if (T == NULL)
	{
		return;
	}
	else
	{
		cout << T->data<<" ";
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

void InOrderTraverse(BiTree T)
{//(3)中序遍历
	if (T == NULL)
	{
		return;
	}
	else
	{
		InOrderTraverse(T->lchild);
		cout << T->data << " ";
		InOrderTraverse(T->rchild);
	}
}

void PostOrderTraverse(BiTree T)
{//(4)后序遍历
	if (T == NULL)
	{
		return;
	}
	else
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		cout << T->data << " ";
	}
}



int Depth(BiTree T)
{//(5)计算二叉树的深度
	if (T==NULL)
	{
		return 0;
	}
	else
	{
		int m = Depth(T->lchild);
		int n = Depth(T->rchild);
		if (m > n)
		{
			return m + 1;
		}
		else
		{
			return n + 1;	
		}
	}
}

int Countleaf(BiTree T)
{//(6)统计二叉树叶子节点 
    int hl,hr;
    if(T)
    {
   		hl=Countleaf(T->lchild);
   		hr=Countleaf(T->rchild);
	    if(hl==0 && hr==0)
	    {
			return (1);
		}
	    else
	    {
	    	return hl+hr;
		}    	
	}
	else
	{
	 return 0;		
	}
}

int NodeNumber1(BiTree T)
{//(7)计算二叉树度为1的结点个数
	if(T)
	{
		if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL))
		{
			return 1+NodeNumber1(T->lchild)+NodeNumber1(T->rchild);
		}
		else
		{
			return NodeNumber1(T->lchild)+NodeNumber1(T->rchild);
		}
	}
}