以前的关于树的笔记
关于二叉树之前有用php实现过,但是感觉并不能通过代码来进行很好的理解,所以打算把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
typedef struct TNode* Position;
typedef struct SNode* PtrToSNode;
typedef Position BinTree;
typedef PtrToSNode Stack;
typedef int ElementType;
typedef int StackPosition;
typedef enum { true=1, false} bool;
struct TNode{
ElementType Data;
BinTree Left; //左子树
BinTree Right; //右子树
};
struct SNode{
ElementType *Data;
StackPosition Top;
int MaxSize;
};
```
#### 二叉树的遍历
1. 先序遍历
```c
/* 先序遍历
* 访问根节点
* 先序遍历左子树
* 先序遍历右子树
* */
void PerOrderTraversal(BinTree BT)
{
if (BT){
printf("%d", BT->Data);
Traversal(BT->Left);
Traversal(BT->Right);
}
}
```
<img src="https://images2017.cnblogs.com/blog/1245009/201709/1245009-20170930181417528-285365280.png">
2. 中序遍历
```c
/*中序遍历
* 中序遍历左子树
* 访问根节点
* 中序遍历右子树
* */
void InOrderTraval(BinTree BT)
{
if (BT){
PerOrderTraversal(BT->Left);
printf("%d", BT->Data);
PerOrderTraversal(BT->Right);
}
}
```
<img src="https://images2017.cnblogs.com/blog/1245009/201709/1245009-20170930190826044-71863116.png">
3. 后序遍历
```c
/*后序遍历
* 后序遍历左子树
* 后序遍历右子树
* 访问根节点
* */
void PostOrderTraval(BinTree BT)
{
if (BT){
PerOrderTraversal(BT->Left);
PerOrderTraversal(BT->Right);
printf("%d", BT->Data);
}
}
```
<img src="https://images2017.cnblogs.com/blog/1245009/201709/1245009-20170930190522794-2031675538.png">
- 求树的高度

```c
int PostOrderGetHeight(BinTree BT)
{
int HL, HR, MaxH;
if(BT){
HL = PostOrderGetHeight(BT->Left); //左子树深度
HR = PostOrderGetHeight(BT->Right); //右子树深度
MaxH = (HL>HR)?HL:HR; //取较大的深度
return (MaxH + 1); //返回树的深度
}
else return 0; //空树深度为0
}
  1. 中序遍历的非递归算法
    我个人感觉采用堆栈这种非递归思想,可以更好的理解树的遍历这个过程
    遇到第一个结点,将其压栈,然后遍历它的左子树,左子树遍历结束后,从栈顶弹出结点然后访问它,再去中序遍历右子树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void InOrderTravalWithStack(BinTree BT)
    {
    int MaxSize = 100;
    Stack S = CreateStack(MaxSize);
    while(BT || !StackIsEmpty(S)){
    while(BT){
    Push(S, BT);
    BT = BT->Left;
    }
    if(!StackIsEmpty(S)){
    BT = Pop(S);
    printf("%5d", BT->Data);
    BT = BT->Right;
    }
    }
    }