FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

Algorithms/BinaryTree/main.cpp at master · ookcode/Algorithms · GitHub

114 lines (106 loc) · 2.61 KB

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

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

//

// main.cpp

// 二叉树的遍历与线索二叉树

//

// Created by vincent on 2017/10/17.

// Copyright © 2017年 vincent. All rights reserved.

//

#include <iostream>

struct BinaryNode {

char data;

BinaryNode* lchild = nullptr;

BinaryNode* rchild = nullptr;

// 线索化

bool ltag = false; // false表示子节点，true表示前驱

bool rtag = false; // false表示子节点，true表示后继

};

// 先序构造二叉树

void createBinaryTree(BinaryNode *&node) {

char ch;

std::cin >> ch;

if(ch == '#') {

return;

}

if (node == nullptr) {

node = new BinaryNode();

}

node->data = ch;

createBinaryTree(node->lchild);

createBinaryTree(node->rchild);

}

// 先序遍历

void preOrderTraverse(BinaryNode *node) {

if (node == nullptr) {

return;

}

printf("%c\n", node->data);

preOrderTraverse(node->lchild);

preOrderTraverse(node->rchild);

}

// 中序遍历

void inOrderTraverse(BinaryNode *node) {

if (node == nullptr) {

return;

}

inOrderTraverse(node->lchild);

printf("%c\n", node->data);

inOrderTraverse(node->rchild);

}

// 后序遍历

void postOrderTraverse(BinaryNode *node) {

if (node == nullptr) {

return;

}

postOrderTraverse(node->lchild);

postOrderTraverse(node->rchild);

printf("%c\n", node->data);

}

// 中序线索化

BinaryNode *tempPre = nullptr;

void inOrderTreading(BinaryNode *node) {

if (node == nullptr) {

return;

}

inOrderTreading(node->lchild);

if(!node->lchild) {

node->ltag = true;

node->lchild = tempPre;

}

if(tempPre && !tempPre->rchild) {

tempPre->rtag = true;

tempPre->rchild = node;

}

tempPre = node;

inOrderTreading(node->rchild);

}

// 线索化后的中序遍历

void inOrderTreadingTraverse(BinaryNode *node) {

BinaryNode *p = node;

while(p) {

while (p->ltag == false) {

p = p->lchild;

}

printf("%c\n", p->data);

while (p->rtag == true) {

p = p->rchild;

printf("%c\n", p->data);

}

p = p->rchild;

}

}

int main(int argc, const char * argv[]) {

// 输入示例：AB#C##D##

printf("请输入一棵二叉树(#表示无子节点):\n");

BinaryNode *tree = new BinaryNode();

createBinaryTree(tree);

printf("先序遍历:\n");

preOrderTraverse(tree);

printf("中序遍历:\n");

inOrderTraverse(tree);

printf("后序遍历:\n");

postOrderTraverse(tree);

printf("中序线索化遍历:\n");

inOrderTreading(tree);

inOrderTreadingTraverse(tree);

return 0;

}

Back | FazBrowse Home | New Git URL