Scott's world.

第三讲 树(上)

Word count: 1.9kReading time: 8 min
2019/07/04 Share

第三讲 树(上)

3.1 树与树的表示

  • 查找

    根据某个给定关键字K,从集合R中找出关键字与K相同的记录

    • 静态查找

      方法1:顺序查找

      方法2:二分查找(Binary Search)

    • 动态查找

树的定义

  • 子树是不相交的

  • 除了根结点外,每个结点有且仅有一个父节点

  • 一棵N个结点的树有N-1条边

  • 树的一些基本术语

树的表示

儿子兄弟表示法

3.2 二叉树及存储结构

二叉树的定义

  • 特殊二叉树

    斜二叉树(Skewed Binary Tree)

    完美二叉树(Perfect Binary Tree)

    完全二叉树(Complete Binary Tree)

二叉树的性质

二叉树的抽象数据类型定义

二叉树的存储结构

顺序存储结构

完全二叉树:按从上至下,从左到右顺序存储N个结点的完全二叉树的结点父子关系

一般二叉树也可以采用这种结构,但会造成空间的大量浪费

链表存储结构

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
#include <iostream>
#include<string.h>
#include<stack>
usingnamespace std;

typedef struct node
{
char data;
struct node *left,*right;
}BinTree;

typedef struct node1
{
BinTree *btnode;
bool isFirst;
}BTNode;

//创建二叉树,s为形如A(B,C(D,E))形式的字符串
void createBinTree(char * s,BinTree * root)
{
int i=1;
bool isRight=false;
stack<BinTree*> s1; //存放结点
stack<char> s2; //存放分隔符
BinTree *p,*temp;
root->data=s[0];
root->left=NULL;
root->right=NULL;
s1.push(root);
while(i<strlen(s))
{
if(s[i]=='(')
{
s2.push(s[i]);
isRight=false;
}
else if(s[i]==',')
{
isRight=true;
}
else if(s[i]==')')
{
s1.pop();
s2.pop();
}
else if(isalpha(s[i]))
{
p=(BinTree *)malloc(sizeof(BinTree));
p->data=s[i];
p->left=NULL;
p->right=NULL;
temp=s1.top();
if(isRight==true)
{
temp->right=p;
count<<temp->data<<"的右孩子是"<<s[i]<<endl;
}
else
{
temp->left=p;
count<<temp->data<<"的左孩子是"<<s[i]<<endl;
}
if(s[i+1]=="(")
{
s1.push(p);
}
}
i++;
}
}

void display(BinTree * root)
{
if(root!=NULL)
{
cout<<root->data;
if(root->left!=NULL)
{
cout<<"(";
display(root->left);
}
if(root->right!=NULL)
{
cout<<",";
display(root->right);
cout<<")";
}
}
}

二叉树的遍历

先序,中序,后序遍历过程:遍历过程中经过结点的路线一样,只是访问各结点的时机不同

递归遍历
先序遍历

中序遍历

后序遍历

非递归遍历
中序遍历非递归遍历算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InOrderTravelsal(BinTree * root)
{
stack<BinTree*> s;
BinTree * p = root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->left;
}
if(!s.empty())
{
p=s.top();
s.pop();
count<<p->data<<"";
p=p->right;
}
}
}
先序遍历非递归遍历算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void PreOrederTravelsal(BinTree * root)
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL || !s.empty())
{
while(p!=NULL)
{
cout<<p->data<<"";
s.push(p);
p=p->left;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->right;
}
}
}
后序遍历非递归遍历算法

在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。

  • 第一种思路

    • 对于任一结点P,将P入栈,然后沿左子树一直往下搜索直至没有左孩子的结点,此时该结点出现在栈顶,但此时并不能出栈并访问,因为其右孩子还未被访问
    • 按相同规则对该结点右子树进行相同的处理直至访问完该结点的右孩子,该结点又出现在栈顶,此时便可以出栈并访问,这样便保证了正确的访问顺序
    • 在此过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶的时候,才能访问它.因此需要设置一个变量标识该结点是否为第一次出现
    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
    void PostOrderTravelsal(BinTree * root)
    {
    stack<BTNode*> s;
    BinTree *p=root;
    BTNode * temp;
    while(p!=NULL||!s.empty())
    {
    while(p!=NULL)
    {
    BTNode * btn=(BTNode *)malloc(sizeof(BTNode));
    btn->btnNode=p;
    btn->isFirst=true;
    s.push(btn);
    p=p->left;
    }
    if(!s.empty())
    {
    temp=s.top();
    s.pop();
    if(temp->isFirst==true) //表示是第一次出现在栈顶
    {
    temp->isFirst=false;
    s.push(temp);
    p=temp->btnNode->right;
    }
    else //第二次出现在栈顶
    {
    cout<<temp->btnNode->data<<"";
    p=NULL;
    }
    }
    }
    }
  • 第二种思路

    • 要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈
    • 如果P不存在左孩子和右孩子,则可以直接访问它;或者P存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点
    • 若非上述两种情况,则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    void PostOrderTravelsal(BinTree * root)
    {
    stack<BinTree*>s;
    BinTree * cur;
    BinTree * pre=NULL; //前一次结点
    s.push(root);
    while(!s.empty())
    {
    cur=s.top();
    if((cur->left==NULL&&cur->right==NULL)||
    (pre!=NULL&&(pre==cur->left||pre==cur->right)))
    {
    cout<<cur->data<<""; //如果当前结点没有孩子结点或者孩子结点已经被访问过
    s.pop();
    pre=cur;
    }
    else
    {
    if(cur->right!=NULL) s.push(cur->right);
    if(cur->left!=NULL) s.push(cur->left);
    }
    }
    }
层序遍历

二维结构的线性化

  • 队列实现

    遍历从根结点开始,首先将根结点入队,然后开始执行循环:

    结点出队,访问该结点,其左右儿子入队

遍历二叉树的应用

例1 输出二叉树中的叶子结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//加入判断左右子树是否都为空
void PreOrderPrintLeaves(BinTree* BT)
{
BinTree * p=BT;
if(p)
{
if(!p->left&&!p->right)
{
count<<p->data<<"";
PreOrderPrintLeaves(p->left);
PreOrderPrintLeaves(p->right);
}
}
}

例2 求二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//根据后序遍历的框架来实现
int PostOrderGetHeight(BinTree * root)
{
int HL,HR,MAXH;
if(root)
{
HL=PostOrderGetHeight(root->left);
HR=PostOrderGetHeight(root->right);
MaxH=(HL>HR)?HL:HR;
return (MaxH+1);
}
else
return 0;
}

例3 二元运算表达式树及其遍历

例4 先or序和中序遍历序列确定一棵二叉树

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
//使用哈希表来存储与查找点在中序遍历中的位置
//这里的二叉树结点值不能有相同的值
int mapIndex[256];
void mapToIndices(int inorder[],int n)
{
int i;
for(i=0;i<n;i++)
{
mapIndex[inorder[i]]=i;
}
}
//在此之前需要调用mapToIndices方法,pre数组为先序遍历序列,注意
//递归过程中pre起始位置是变化的.n为结点数目,offset为子树开始位置
struct node * buildInorderPreorder(int pre[],int n,int offset)
{
if(n==0)return NULL;
int rootVal=pre[0];
int i=mapIndex[rootVal]-offset;
struct node * root=newNode(rootVal);
root->left=buildInorderPreorder(pre+1,i,offset);
root->right=buildInorderPreorder(pre+i+1,n-i-1,offset+i+1);
return root;
}
//与前面原理相似,后序遍历是从后往前;
struct node *buildInorderPostorder(int post[], int n, int offset)
{
assert(n >= 0);
if (n == 0) return NULL;
int rootVal = post[n-1];
int i = mapIndex[rootVal]-offset; // the divider's index
struct node *root = newNode(rootVal);
root->left = buildInorderPostorder(post, i, offset);
root->right = buildInorderPostorder(post+i, n-i-1, offset+i+1);
return root;
}
CATALOG
  1. 1. 第三讲 树(上)
    1. 1.1. 3.1 树与树的表示
      1. 1.1.1. 树的定义
      2. 1.1.2. 树的表示
        1. 1.1.2.1. 儿子兄弟表示法
    2. 1.2. 3.2 二叉树及存储结构
      1. 1.2.1. 二叉树的定义
      2. 1.2.2. 二叉树的性质
      3. 1.2.3. 二叉树的抽象数据类型定义
      4. 1.2.4. 二叉树的存储结构
        1. 1.2.4.1. 顺序存储结构
        2. 1.2.4.2. 链表存储结构
      5. 1.2.5. 二叉树的遍历
        1. 1.2.5.1. 递归遍历
          1. 1.2.5.1.1. 先序遍历
          2. 1.2.5.1.2. 中序遍历
          3. 1.2.5.1.3. 后序遍历
        2. 1.2.5.2. 非递归遍历
          1. 1.2.5.2.1. 中序遍历非递归遍历算法
          2. 1.2.5.2.2. 先序遍历非递归遍历算法
          3. 1.2.5.2.3. 后序遍历非递归遍历算法
        3. 1.2.5.3. 层序遍历
        4. 1.2.5.4. 遍历二叉树的应用