试写出二叉树的二叉链储存结构描述,并给出求深度算法
时间: 2024-03-28 14:12:26 浏览: 54
写一算法,判断一棵二叉树是否是一棵二叉排序树。
二叉树的二叉链表存储结构定义如下:
```
typedef struct BiTNode {
int data; // 数据域
struct BiTNode *lchild; // 左孩子指针
struct BiTNode *rchild; // 右孩子指针
} BiTNode, *BiTree;
```
求取二叉树深度的算法如下:
```
int GetDepth(BiTree T) {
if(T == NULL) { // 空树深度为0
return 0;
}
int left_depth = GetDepth(T->lchild); // 左子树深度
int right_depth = GetDepth(T->rchild); // 右子树深度
return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}
```
以上算法采用递归方式实现,时间复杂度为O(n),其中n为二叉树中节点数。
阅读全文