ZEROCATH

身无长物江湖远,胸有沟壑天地宽

0%

二叉树:遍历

遍历顺序:

规定从左到右

  • 前序:
  • 中序
  • 后序

    树的结构

  • 定义如下:SS
1
2
3
4
5
6
struct BiTree{
int data;
struct BiTree *left,*right;
};
typedef BiTree BTNode;
typedef BiTree *BT;

递归算法

前序递归遍历

思路

若根节点为空,直接返回空,不为空则输出根节点后递归遍历根的左子结点,再递归遍历根的右子节点。

代码实现

1
2
3
4
5
6
7
8
9
void preOrderTravase(BT root)
{
if(!root) return;
else{
printf("%d",root->data);
preOrderTravase(root->left);
preOrderTravase(root->right);
}
}

中序递归遍历

1
2
3
4
5
6
7
8
9
10
void inOrderTravase(BT root)
{
if(!root) return;
else
{
inOrderTravase(root->left);
printf("%d",root->data);
inOrderTravase(root->right);
}
}

后序递归遍历

1
2
3
4
5
6
7
8
9
10
void postOrderTravase(BT root)
{
if(!root) return;
else
{
postOrderTravase(root->left);
postOrderTravase(root->right);
printf("%d",BT->data);
}
}

非递归遍历

前序

思路

栈实现:根结点非空则先入栈,循环结构中,当栈非空时栈顶出栈,且将出栈结点的右结点和左节点(如果存在)分别入栈

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrderTravase(BT root)
{
BT stack[MaxLeng],temp;
int top=0;
if(!root) return;
stack[top++]=root;
while(top)
{
temp=stack[--top];
printf("%d ",temp->data);
if(temp->right)
stack[top++]=temp->right;
if(temp->left)
stack[top++]=temp->left;
}
}

中序

思路

栈实现:根结点非空则先入栈,循环体中,先将左子结点依次入栈至其无左节点;若栈非空,弹出栈顶结点并访问该结点,接着将其右子树作为根遍历

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void inOrderTravase(BT root)
{
BT stack[MaxLeng];
int top=0;
if(root)
{
temp=root;
do
{
while(temp)
{
stack[top++]=temp;
temp=temp->left;
}//终止循环时,temp=NULL,栈顶的下一个才指向栈顶结点;
if(top)//栈非空
{
temp=stack[--top];
printf("%d ",temp->data);
temp=temp->right;
}//if
}while(top||temp)//do
}
}

后序

思路

将根结点入栈,循环体中:将左子树依次入栈至无左子树,出栈,若有右兄弟结点同样出栈

二叉树高度

  • 递归实现

返回1+左右子树中最高的高度