4.1 树概述
← 内容总览 15 / 24 下一节 → 强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 4.1 树概述
## 4.1.1 思考流程
树和图的题目一般不会特别要求复杂度，如果没有特别要求的话，考试中只要做出来就可以直接写，不用考虑优化问题。一般都会考察树的遍历，除非特别说明，否则遍历就用递归写，不要写非递归。
<!-- page 148 -->
## 4.1.2 考察结构
树和森林
树和森林(孩子兄弟表示法)
firstchild 是指向该结点第一个儿子结点的指针，nextbro 是指向下一个兄弟结点的指针
<!-- verified-by-hand -->
> [!success] 已结合原文第 148 页及 Markdown 上下文人工校对
> 孩子兄弟表示法结构体左花括号丢失。
typedef struct TNode
{
ElemType data ;
struct TNode * firstchild , * nextbro ;
} TNode ;
int father [ MAX_SIZE ]; //保存每个结点的父亲结点在数组中的下标
typedef struct TNode
{
ElemType data ;
struct TNode * father ;
} TNode ;
typedef struct BTNode
{
ElemType data ;
struct BTNode * lchild , * rchild ;
} BTNode ;
typedef struct
{
int SqBiTNode [ MAX_SIZE ];
int ElemNum ;
} SqBiTree ;
3. 调用右 InOrder ( p -& gt ; rchild );
void PreOrder ( BTNode * p )
{
if ( p == NULL ) return ;
visit ( p ); PreOrder ( p -& gt ; lchild ); PreOrder ( p -& gt ; rchild );
}
void InOrder ( BTNode * p )
{
if ( p == NULL ) return ;
InOrder ( p -& gt ; lchild ); visit ( p ); InOrder ( p -& gt ; rchild );
}
void PostOrder ( BTNode * p )
{
if ( p == NULL ) return ;
PostOrder ( p -& gt ; lchild ); PostOrder ( p -& gt ; rchild ); visit ( p );
}
void TreePre0rder ( TNode * T )
{
if ( T == NULL ) return ;
visit ( T ); // 访问当前结点
TreePre0rder ( T -& gt ; firstchild ); // 递归访问第一个孩子
TreePre0rder ( T -& gt ; nextbro ); //递归访问兄弟结点
}
void TreePost0rder ( TNode * T ) // 王進
{
if ( T == NULL ) return ;
TreePostOrder ( T -& gt ; firstchild ); //先访问所有孩子
visit ( T ); // 最后访问根
TreePost0rder ( T -& gt ; nextbro ); //然后访问兄弟结点
}
原资料配图 · 转写内容请回源核验
二叉树结点定义如下：
原资料配图 · 转写内容请回源核验
typedef struct node {
char data [ 10 ]; //存储操作数或操作符
struct node * left , * right ;
} BTree ;
// 需要返回值
int In0rder ( BTNode * p ) //返回类型不—定是int
{
if ( p == NULL ) return 返回值 ;
In0rder ( p -& gt ; lchild ); // 调用根据题目修改
visit ( p ); //是最重要的部分，根据题目要求决定
InOrder ( p -& gt ; rchild );
return xx ;
}
// 不需要返回值
void InOrder ( BTNode * p )
{
if ( p == NULL ) return ;
In0rder ( p -& gt ; lchild ); // 调用根据题目修改
visit ( p ); //是最重要的部分，根据题目要求决定
InOrder ( p -& gt ; rchild );
}
int InOrder ( BTNode * p )
{
if ( p == NULL ) return // 返回值;
In0rder ( p -& gt ; lchild ); // 调用根据题目修改
visit ( p ); //是最重要的部分，根据题目要求决定
InOrder ( p -& gt ; rchild );
return // 返回值;
}
void ans ( BTNode * T )
{
输出InOrder ( T );
完成其他工作
}
void InOrder ( BTNode * p )
{
if ( p == NULL ) return ; // p是空结点
InOrder ( p -& gt ; lchild ); //递归调用左子树
visit ( p );
InOrder ( p -& gt ; rchild ); // 递归调用右子树
}
printf ( & quot ; % s & quot ;, p → & gt ; data ); // 输出操作数
void InOrder ( BTree * p , BTree * root )
{
if ( p == NULL ) return ;
bool needParen = ( p != root ) & amp ; & amp ; ( p -& gt ; left != NULL || p -& gt ; right != NULL );
if ( needParen ) printf ( & quot ;( & quot ;);
InOrder ( p -& gt ; left , root );
printf ( & quot ; % s & quot ;, p -& gt ; data );
InOrder ( p -& gt ; right , root );
if ( needParen ) printf ( & quot ;) & quot ;);
}
void InOrder ( BTree * p , BTree * root ) // root是原二叉树的根
{
if ( p == NULL ) return ; // p是空结点
if (( p -& gt ; left != NULL | l p -& gt ; right != NULL ) & amp ; & amp ; ( p != root ))
printf ( & quot ;( & quot ;);
InOrder ( p -& gt ; left , root ); //递归调用左子树
printf ( & quot ; % s & quot ;, p -& gt ; data ); 11 车 输出操作数
InOrder ( p -& gt ; right , root ); // 递归调用右子树
if (( p -& gt ; left != NULL || p -& gt ; right != NULL ) & amp ; & amp ; ( p != root ))
printf ( & quot ;) & quot ;);
}
int WPL = 0 ; // WPL是全局变量
void PreOrder ( BTNode * p , int depth ) // 当前结点p，深度depth
{
if ( p == NULL ) return ;
//
visit ( p );
// p是叶结点
WPL += depth * p -& gt ; weight ;
Pre0rder ( p -& gt ; left , depth + 1 ); //递归调用左孩子
Pre0rder ( p -& gt ; right , depth + 1 ); // 递归调用右孩子
}
int postOrder ( BTNode * p , int depth )
{
if ( p == NULL ) return 0 ; // p 是空结点
int L_WPL = postOrder ( p -& gt ; left , depth + 1 );
int R_WPL = postOrder ( p -& gt ; right , depth + 1 );
if ( p -& gt ; left == NULL & amp ; & amp ; p -& gt ; right == NULL )
return depth * p -& gt ; weight ;
return L_WPL + R_WPL ;
}
← 内容总览 15 / 24 下一节 →
