二叉树——课上练（链式存储结构）_二叉树——课上练(链式存储结构)

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef char DataType;

//二叉树数据结构
struct node
{
    DataType info ; //存放结点数据
    struct node *lchild , *rchild ; //指向左右孩子的指针
};

typedef struct node *BiTree ;

/*创建二叉树
  函数名：createBiTree
  参数：无
  返回值：二叉树根结点指针
  */
BiTree createBiTree(void)
{
    //请在此处填写代码， 完成二叉树和创建，返回值是二叉树的根结点指针
    /********** Begin **********/
    DataType x;
    BiTree node;
    
    scanf("%c",&x);
    
    if(x=='#') return NULL;
    
    node = (BiTree)malloc(sizeof(struct node));
    node->info = x;
    if(node==NULL) return NULL;
    
    node->lchild = createBiTree();
    node->rchild = createBiTree();
    
    return node;
    /********** End *********/
}

void visit(BiTree T) //输出结点T的数据
{
    cout<<T->info ;
}

void inOrder(BiTree root)
{
    if(root == NULL) return ;
    inOrder(root->lchild);
    visit(root);
    inOrder(root->rchild);
}

int main(void)
{
    BiTree root = createBiTree();
    inOrder(root);
}

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

#include <iostream>
using namespace std;

typedef char DataType;

//二叉树数据结构 
struct node
{
	DataType info ; //存放结点数据 
	struct node *lchild , *rchild ; //指向左右孩子的指针 
};

typedef struct node *BiTree ;

/*创建二叉树
  函数名：createBiTree
  参数：无
  返回值：二叉树根结点指针
  */
BiTree createBiTree(void)
{
	char ch ;
	BiTree  root ;
	cin>>ch ;
	if(ch == '#') root = NULL;
	else{
        root = new struct node ;
        root->info = ch ;
        root->lchild = createBiTree() ;
        root->rchild = createBiTree();
	}
	return root ;
}

void visit(BiTree T)
{
	cout<<T->info ;
}



int countLeaf(BiTree root)
{
    //请在此处填写代码， 计算二叉树中树叶的个数
    /********** Begin **********/
    if(root==NULL)return 0;
    
    if(root->lchild==NULL&&root->rchild==NULL)return 1;
    else return countLeaf(root->lchild)+countLeaf(root->rchild);

    /********** End **********/
}

int main(void)
{
	BiTree root = createBiTree();
	cout<<countLeaf(root);
}

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

#include <iostream>
using namespace std;

typedef char DataType;

//二叉树数据结构
struct node
{
    DataType info ; //存放结点数据
    struct node *lchild , *rchild ; //指向左右孩子的指针
};

typedef struct node *BiTree ;

/*创建二叉树
  函数名：createBiTree
  参数：无
  返回值：二叉树根结点指针
  */
BiTree createBiTree(void)
{
    char ch ;
    BiTree  root ;
    cin>>ch ;
    if(ch == '#') root = NULL;
    else{
        root = new struct node ;
        root->info = ch ;
        root->lchild = createBiTree() ;
        root->rchild = createBiTree();
    }
    return root ;
}

void changeLR(BiTree root)
{
    //请在此处填写代码， 完成二叉树左右子树互换
    /********** Begin **********/
    BiTree temp = NULL;
    if(root){
        temp = root-> lchild;
        root -> lchild = root ->rchild;
        root->rchild = temp;
        changeLR(root->lchild);
        changeLR(root->rchild);
    }
    
    /********** End **********/
}

void visit(BiTree T) //输出结点T的数据
{
    cout<<T->info ;
}

void inOrder(BiTree root)
{
    if(root == NULL) return ;
    inOrder(root->lchild);
    visit(root);
    inOrder(root->rchild);
}

int main(void)
{
    BiTree root = createBiTree();
    changeLR(root);
    inOrder(root);
}

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

#include <iostream>
using namespace std;

typedef char DataType;

//二叉树数据结构
struct node
{
    DataType info ; //存放结点数据
    struct node *lchild , *rchild ; //指向左右孩子的指针
};

typedef struct node *BiTree ;

/*创建二叉树
  函数名：createBiTree
  参数：无
  返回值：二叉树根结点指针
  */
BiTree createBiTree(void)
{
    char ch ;
    BiTree  root ;
    cin>>ch ;
    if(ch == '#') root = NULL;
    else{
        root = new struct node ;
        root->info = ch ;
        root->lchild = createBiTree() ;
        root->rchild = createBiTree();
    }
    return root ;
}

void visit(BiTree T)
{
    cout<<T->info ;
}

int countFullNode(BiTree root)
{
    //请在此处填写代码，计算二叉树中满结点的个数
    /********** Begin **********/
    int count = 0;
    
    if(root){
        if(root->lchild&&root->rchild){
            count++;
            count += countFullNode(root->lchild);
            count += countFullNode(root->rchild);
            
        }
    }
    return count;
    
    /*********** End-**********/
}

int main(void)
{
    BiTree root = createBiTree();
    cout<<countFullNode(root) ;
}

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