/* 二叉树操作集 */
#include<stdio.h>
#include<stdlib.h>
typedef char ElementType;
typedef struct TreeNode *BinTree;
struct TreeNode {
ElementType Data;
BinTree Left;
BinTree Right;
};
BinTree CreateBinTree(); //建立二叉树
void InOrderTraversal(BinTree bt); //输出二叉树
void PreOrderTraversal(BinTree bt);
int TreeHigh(BinTree bt); //求树高度
void PreorderPrintLeaves(BinTree bt); //先序输出叶节点
int main()
{
BinTree BT = NULL;
BT = CreateBinTree();
InOrderTraversal(BT);
putchar('\n');
PreOrderTraversal(BT);
printf("the high of the tree:%d\n", TreeHigh(BT));
PreorderPrintLeaves(BT);
system("pause");
return 0;
}
/*
建立二叉树
先序遍历 根节点-左子树-右子树
输入:A B D H # # I # # E # # C F # J # # G # # #####
树:
A
BC
DEFG
HI###J##
#####################
*/
BinTree CreateBinTree()
{
BinTree bt;
char node;
scanf_s("%c", &node);
getchar();
if (node != '#') {
bt = (BinTree)malloc(sizeof(struct TreeNode));
bt->Data = node;
bt->Left = CreateBinTree();
bt->Right = CreateBinTree();
}
else
bt = NULL;
return bt;
}
/*
输出二叉树
先序遍历(PreOrderTraversal):根-左-右
中序遍历(InOrderTraversal):左-根-右
后序遍历(PostOrderTraversal): 左-右-根
*/
void InOrderTraversal(BinTree bt)
{
if (bt) {
InOrderTraversal(bt->Left);
printf("%c ", bt->Data);
InOrderTraversal(bt->Right);
}
}
void PreOrderTraversal(BinTree bt)
{
if (bt) {
printf("%c ", bt->Data);
PreOrderTraversal(bt->Left);
PreOrderTraversal(bt->Right);
}
}
/*
递归:求左子树的高度,求右子树的高度,
Max(left,rigth)+1;
*/
int TreeHigh(BinTree bt)
{
if(bt==NULL) return 0;
int lefthigh=TreeHigh(bt->Left)+1;
int righthigh=TreeHigh(bt->Right)+1;
return (righthigh>lefthigh)?righthigh:lefthigh;
/*
if(bt==NULL) return 0;
else{
lefthigh=TreeHigh(bt->Left);
righthigh=TreeHigh(bt->Right);
return (righthigh>lefthigh)?righthigh+1:lefthigh+1;
}
*/
}
/*
递归:输出树的叶节点
*/
void PreorderPrintLeaves(BinTree bt)
{
if(bt){
if(bt->Left==NULL&&bt->Right==NULL){
printf("%c ", bt->Data);
}
PreorderPrintLeaves(bt->Left);
PreorderPrintLeaves(bt->Right);
}
}
网友评论