2.4. 树基础

2.4.1. 什么是树

定义: n（n>=0)个节点构成的有限集合。子树是不想交的，出个根节点，每个节点有且只有一个父节点。

几个概念

  • 节点的度： 节点的子树个数。

  • 树的度： 树的所有节点中最大的度。

  • 节点的层次： 规定根节点在1层，其他任意节点的层数是其父节点+1。

  • 树的深度： 树中所有节点中最大层次是这棵树的深度。

  • 父节点： 有子树的节点是其子树的根节点的父节点。

  • 子节点： 如果a节点是b节点的父节点，则成b是a节点的子节点。

  • 兄弟节点： 具有同一个父亲节点的各节点是兄弟节点。

2.4.2. 什么是二叉树

度为2的树，可以为空。

  • 一个二叉树，第i层的最大节点树为 pow(2,i-1)。

  • 深度为k的二叉树有最大节点树为pow(2,k)-1。

  • 对任何非空二叉树T,若n0表示叶子节点个数，n1表示一个子节点的个数，n2表示2个子节点的个数，则n0=n2+1。

证明如下：

n表示总边树 = 总结点树 -1 = n0 +n1 +n2 -1
总结点 = 0 *n0 + 1 * n1 + 2 *n2
n0 +n1 +n2 -1 = n1 + 2 * n2
n0=n2+1 。

抽象数据结构描述

类型名称： 二叉树
数据对象集： 一个有穷的节点集合
操作集：
    Boolean IsEmpty(BinTree bt): 判断树是否为空。
    void Traversal (BinTree bt): 遍历树，按某种顺序访问每个节点。
    BinTree CreateBinTree(): 创建一个二叉树。

    void PreOrderTraversal(BinTree bt): 先序： 根 左子树 右子树
    void InOrderTraversal(BinTree bt): 中序： 左子树 根 右子树
    void PosOrderTraversal(BinTree bt): 后序： 左子树 右子树 根
    void LevelOrderTraversal(BinTree bt): 先序： 从上到下，从左到右。先第一层遍历完毕，在第二层。每次从左到右。

2.4.3. 二叉树顺序存储实现

完全二叉树： 按照从上到下，从左到右存储。

特点：

  • 非根节点的父节点需要为 [i/2]

  • 节点i的左孩子为2i 如果2i<=n（节点个数） 则表示没有左孩子节点。

  • 节点i的右孩子为2i+1 如果2i+1<=n（节点个数） 则表示没有右孩子节点。

对于一般二叉树，也是可以采用这种方式的， 但是空间浪费是比较严重的。

1
2
3int main(){
4
5}
6
7

2.4.4. 二叉树链式存储实现

 1// bitree_link_base.h
 2#pragma once
 3#include <stdio.h>
 4#include <stdlib.h>
 5
 6#define ElementType int
 7typedef struct  TreeNode *BsTree ;
 8typedef BsTree  Position ;
 9struct  TreeNode{
10    ElementType Data ;
11    BsTree  Left;
12    BsTree  Right;
13};

  1// bitree_link_base.c
  2#include <stdio.h>
  3#include <stdlib.h>
  4#include "stack_link_base_for_tree.c"
  5#include "queue_link_base_for_tree.c"
  6#include "bitree_link_base.h"
  7
  8// 判断树是否为空
  9int TreeIsEmpty(BsTree bt){
 10    if( bt == NULL){
 11        return 1 ;
 12    }
 13    return 0;
 14}
 15
 16// 创建树
 17BsTree CreateBsTree(){
 18    BsTree  bt = (BsTree)malloc(sizeof(struct TreeNode));
 19    return bt ;
 20}
 21
 22// 前序递归
 23void PreOrderTraversalByRecursive(BsTree bt){
 24    if (bt){
 25        printf("%d ", bt->Data);
 26        PreOrderTraversalByRecursive(bt->Left);
 27        PreOrderTraversalByRecursive(bt->Right);
 28    }
 29}
 30
 31// 中续递归
 32void InOrderTraversalByRecursive(BsTree bt){
 33    if (bt){
 34        InOrderTraversalByRecursive(bt->Left);
 35        printf("%d ", bt->Data);
 36        InOrderTraversalByRecursive(bt->Right);
 37    }
 38}
 39
 40// 后续递归
 41void PosOrderTraversalByRecursive(BsTree bt){
 42    if (bt){
 43        PosOrderTraversalByRecursive(bt->Left);
 44        PosOrderTraversalByRecursive(bt->Right);
 45        printf("%d ", bt->Data);
 46    }
 47}
 48
 49// 前序迭代
 50void PreOrderTraversalByIterate(BsTree bt){
 51    Stack s = CreateStack();
 52    BsTree  t = bt;
 53    while( t || !StackIsEmpty(s)){
 54        while(t){
 55            printf("%d ",t->Data);
 56            Push(s,  t);
 57            t= t->Left;
 58        }
 59        if (!StackIsEmpty(s)){
 60            t= (BsTree) Pop(s);
 61            t=t->Right;
 62        }
 63    }
 64}
 65
 66// 中序迭代
 67void InOrderTraversalByIterate(BsTree bt){
 68    Stack s = CreateStack();
 69    BsTree  t = bt;
 70    while( t || !StackIsEmpty(s)){
 71        while(t){
 72            Push(s,  t);
 73            t= t->Left;
 74        }
 75        if (!StackIsEmpty(s)){
 76            t= (BsTree) Pop(s);
 77            printf("%d ",t->Data);
 78            t=t->Right;
 79        }
 80    }
 81}
 82
 83// 后序迭代
 84void PostOrderTraversalByIterate(BsTree bt){
 85    Stack s = CreateStack();
 86    BsTree  t = bt;
 87    BsTree  prev= NULL ;
 88    while( t || !StackIsEmpty(s)){
 89        while(t){
 90            Push(s,  t);
 91            t= t->Left;
 92        }
 93        t = (BsTree)Pop(s);
 94        if (t->Right == NULL || t->Right == prev){
 95            printf("%d ",t->Data);
 96            prev = t ;
 97            t = NULL;
 98
 99        }else{
100            Push(s,t);
101            t= t->Right;
102        }
103
104    }
105}
106
107
108// 层次遍历
109void LevelOrderTraversal(BsTree bt){
110
111    Queue  q = CreateQueue();
112    BsTree  t = bt ;
113    if (bt == NULL){
114        return ;
115    }
116    AddQ(q,t);
117    while(!IsEmptyQ(q)){
118
119        t= DeleteQ(q);
120        printf("%d ",t->Data);
121        if (t->Left){
122            AddQ(q,t->Left);
123        }
124        if (t->Right){
125            AddQ(q,t->Right);
126        }
127
128    }
129
130}
131BsTree CreateDemoTree(){
132    /*
133            1
134         2      3
135       5   4   6
136
137
138    * */
139    BsTree  bt1 = CreateBsTree();
140    bt1->Data = 1 ;
141    BsTree  bt2 = CreateBsTree();
142    bt2->Data = 2 ;
143    BsTree  bt3 = CreateBsTree();
144    bt3->Data = 3 ;
145    BsTree  bt4 = CreateBsTree();
146    bt4->Data = 4 ;
147    BsTree  bt5 = CreateBsTree();
148    bt5->Data = 5 ;
149    BsTree  bt6 = CreateBsTree();
150    bt6->Data = 6 ;
151
152    bt1->Left = bt2 ;
153    bt1->Right =bt3 ;
154
155    bt2->Left = bt5 ;
156    bt2->Right=bt4 ;
157
158    bt3->Left = bt6 ;
159    return  bt1 ;
160}
161
162int main(){
163
164    BsTree  bt =CreateDemoTree();
165    printf("PreOrderTraversal\n");
166    PreOrderTraversalByRecursive(bt);
167    printf("\n");
168
169    printf("InOrderTraversalByRecursive\n");
170    InOrderTraversalByRecursive(bt);
171    printf("\n");
172
173    printf("PosOrderTraversalByRecursive\n");
174    PosOrderTraversalByRecursive(bt);
175    printf("\n");
176
177
178    printf("PreOrderTraversalByIterate\n");
179    PreOrderTraversalByIterate(bt);
180    printf("\n");
181
182    printf("InOrderTraversalByIterate\n");
183    InOrderTraversalByIterate(bt);
184    printf("\n");
185
186    printf("PostOrderTraversalByIterate\n");
187    PostOrderTraversalByIterate(bt);
188    printf("\n");
189
190    printf("LevelOrderTraversal\n");
191    LevelOrderTraversal(bt);
192    printf("\n");
193}