第三讲 树(上)
3.1 树与树的表示
树的定义
子树是不相交的
除了根结点外,每个结点有且仅有一个父节点
一棵N个结点的树有N-1条边
树的一些基本术语
树的表示
儿子兄弟表示法
3.2 二叉树及存储结构
二叉树的定义
二叉树的性质
二叉树的抽象数据类型定义
二叉树的存储结构
顺序存储结构
完全二叉树:按从上至下,从左到右顺序存储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;
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;
}
}
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;
struct node *root = newNode(rootVal);
root->left = buildInorderPostorder(post, i, offset);
root->right = buildInorderPostorder(post+i, n-i-1, offset+i+1);
return root;
}
|
