大二下 数据结构(四)

适用于电商专业大二年级下学期,数据结构专业选修课,不是物联网同学大二上的数据结构哦。
年代久远,仅供参考。

目标:二叉树及其应用。

内容:

(1) 用先序递归过程建立二叉树 (存储结构:二叉链表)
输入数据按先序遍历所得序列输入,当某结点左子树或右子树为空时,输入‘’号,如输入abcde*得到的二叉树为:(图片如课件)
(2) 计算二叉树中叶子结点的数目。

代码

这篇因为我日常得写两份,所以自己的那份干脆用c++,给别人的那份是c,所以建议直接看第二份。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>  
using namespace std;

typedef struct node//建立二叉链表的储存结构
{
struct node *leftChild;
struct node *rightChild;
char data;
}BiTreeNode, *BiTree;

void createBiTree(BiTree &T)
{
char c;
cin >> c; //扫描得到字符
if('*' == c) //如果字符为*,则根节点为空
T = NULL;
else
{
T = new BiTreeNode; //否则建立根节点
T->data = c;
createBiTree(T->leftChild);
createBiTree(T->rightChild);
}
}

//先序遍历
void preOrderTraverse(BiTree T)
{
if(T)
{
cout << T->data << " ";
preOrderTraverse(T->leftChild);
preOrderTraverse(T->rightChild);
}
}

// 中序遍历
void inOrderTraverse(BiTree T)
{
if(T)
{
inOrderTraverse(T->leftChild);
cout << T->data << " ";
inOrderTraverse(T->rightChild);
}
}

// 后序遍历
void postOrderTraverse(BiTree T)
{
if(T)
{
postOrderTraverse(T->leftChild);
postOrderTraverse(T->rightChild);
cout <<T->data << " ";
}
}

int getLeafNode(BiTree T)
{
if(NULL == T)
return 0;

if(NULL == T->leftChild && NULL == T->rightChild)
return 1;

return getLeafNode(T->leftChild) + getLeafNode(T->rightChild);
}

int main()
{
BiTree T;
cout <<"Please input the data of the BiTree in the preorder. Type in \"*\" to represent the NULL."<< endl;
createBiTree(T);

cout << "\nPreorder:" << endl;
preOrderTraverse(T);
cout << endl << endl;

cout << "Inorder:" << endl;
inOrderTraverse(T);
cout << endl << endl;

cout << "Postorder:" << endl;
postOrderTraverse(T);
cout << endl << endl;

cout << "The number of LeafNodes is:" << endl;
cout << getLeafNode(T) << endl;

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>


typedef struct BiTNode{//建立二叉链表的储存结构
char data;
struct BiTNode *lchild,*rchild;
}BiTNode, * BiTree;

int count=0;

void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);//扫描得到字符
if(ch=='*')
T=NULL;//如果字符为空,则根节点为空
else {
if (!(T=(BiTNode *)malloc(sizeof(BiTNode))))//否则建立根节点
exit(-1);
T->data = ch;//根节点数据域
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
}

void PreOrder(BiTree &T){ //先序遍历
if(T != NULL){
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}

void CountLeaf(BiTree T,int& count)//累加和存储于变量count中,其初值为0
{
if(T)//二叉树T如果为空,则什么都不做;不为空时往下执行
{
if((!T->lchild)&&(!T->rchild))//如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点,count加1。
count++;
CountLeaf(T->lchild,count);//遍历左子树叶子节点个数
CountLeaf(T->rchild,count);//遍历右子树叶子节点个数
}

}

int main(){
BiTree T;

printf("Please type in the BiTree data in preorder, type in * to represent NULL:\n");
CreateBiTree(T);

printf("PreOrder:");
PreOrder(T);
CountLeaf(T,count);
printf("\nThe number of leafnodes is: %d\n",count);

system("pause");
}