4、树、二叉树代码
- 格式：docx
- 大小：23.18 KB
- 文档页数：7
#include
#include
usingnamespace std;
#include
#include
typedefcharDataType;
typedefstructNode
{
DataType data;
structNode *LChild;
structNode *RChild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree *bt)
{
char ch;
ch = getchar();
if (ch == '.') *bt = NULL;
else
{
*bt = (BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
(*bt)->data = ch;
CreateBiTree(&((*bt)->LChild)); //生成左子树
CreateBiTree(&((*bt)->RChild)); //生成右子树
}
}
void Visit(charch)
{
printf("%c ", ch);
}
void PreOrder(BiTreeroot)
/*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
{
if (root != NULL)
{
Visit(root->data); /*访问根结点*/
PreOrder(root->LChild);
/*先序遍历左子树*/
PreOrder(root->RChild); /*先序遍历右子树*/
}
}
void InOrder(BiTreeroot)
/*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
{
if (root != NULL)
{
InOrder(root->LChild); /*中序遍历左子树*/
Visit(root->data); /*访问根结点*/
InOrder(root->RChild); /*中序遍历右子树*/
}
}
void PostOrder(BiTreeroot) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/
{
if (root != NULL)
{
PostOrder(root->LChild); /*后序遍历左子树*/
PostOrder(root->RChild); /*后序遍历右子树*/
Visit(root->data); /*访问根结点*/
}
}
int PostTreeDepth(BiTreebt) /* 后序遍历求二叉树的高度递归算法 */
{
int hl, hr, max;
if (bt != NULL)
{
hl = PostTreeDepth(bt->LChild); /*求左子树的深度 */
hr = PostTreeDepth(bt->RChild); /*求右子树的深度 */
max = hl>hr ? hl : hr; /*得到左、右子树深度较大者*/
return(max + 1); /*返回树的深度 */
}
elsereturn(0);
/*如果是空树，则返回0 */
}
/* LeafCount保存叶子结点的数目的全局变量,调用之前初始化值为0 */
int LeafCount = 0;
void leaf_a(BiTreeroot)
{
if (root != NULL)
{
leaf_a(root->LChild);
leaf_a(root->RChild);
if (root->LChild == NULL&&root->RChild == NULL)
LeafCount++;
}
}
int leaf_b(BiTreeroot)
{
int LeafCount2;
if (root == NULL)
LeafCount2 = 0;
else
if ((root->LChild == NULL) && (root->RChild == NULL))
LeafCount2 = 1;
else
LeafCount2 = leaf_b(root->LChild) + leaf_b(root->RChild);
/* 叶子数为左右子树的叶子数目之和 */
return LeafCount2;
}
void PrintTree(BiTreeBoot, intnLayer) /* 按竖向树状打印的二叉树 */
{
if (Boot == NULL) return;
PrintTree(Boot->RChild, nLayer + 1); for (int i = 0; i
printf(" ");
printf("%c\n", Boot->data);
PrintTree(Boot->LChild, nLayer + 1);
}
//非递归先序遍历
void _PreOrder(BiTreeroot)
{
stack s;
BiTree p = root;
cout <<"非递归先序遍历：";
while (p || !s.empty())
{
while (p != NULL)
{
cout << p->data <<" ";
s.push(p);
p = p->LChild;
}
p = s.top();
s.pop();
p = p->RChild;
}
cout << endl;
}
//非递归中序遍历
void _InOrder(BiTreeroot)
{
stack s;
BiTree p = root;
cout <<"非递归中序遍历：";
while (p || !s.empty())
{
while (p != NULL)
{
s.push(p);
p = p->LChild;
}
p = s.top();
cout << p->data <<" ";
s.pop();
p = p->RChild;
}
cout << endl;
}
//"非递归后序遍历
void _PostOrder(BiTreeroot)
{
BiTree p = root, q = NULL;
stack s;
cout <<"非递归后序遍历：";
while (p != NULL || !s.empty())
{
while (p != NULL)
{
s.push(p); p = p->LChild;
}
if (!s.empty())
{
p = s.top();
//无右孩子或右孩子已遍历过
if (p->RChild == NULL || p->RChild == q)
{
cout << p->data <<" ";
//保存到q，为下一次已处理结点前驱
q = p;
p = NULL;
s.pop();
}
else
{
p = p->RChild;
}
}
}
cout << endl;
}
void main()
{
BiTree T;
printf("请以先序遍历输入将要创建的二叉树，'.'代表空结点，如\n" );
CreateBiTree(&T);
printf("先序遍历序列为:");
PreOrder(T);
printf("\n中序遍历序列为:");
InOrder(T);
printf("\n后序遍历序列为:");
PostOrder(T);
//深度
int h = PostTreeDepth(T);
printf("\nThe depth of this tree is:%d\n",h);
//叶子数目
printf("treeleaf=%d\n", leaf_b(T));
//竖向树状打印的二叉树
int layer = 0;
printf("按竖向树状打印的二叉树\n");
PrintTree(T,layer);
printf("非递归先序遍历序列为:");
_PreOrder(T);
printf("非递归中序遍历序列为:");
_InOrder(T);
printf("非递归后序遍历序列为:");
_PostOrder(T);
putchar(10);
}
