更新时间:2015-11-07 23:19:52浏览次数:1+次
二叉树是由n个结点构成的一种树结构。
二叉树中的每个结点最多只有两颗子树并且二叉树中的每个结点都有左右次序之分,即次序不能颠倒。二叉树的基本操作只要有如下几种:(包含在头文件LinkBiTree.h中)
InitBitTree(&T):构造空的二叉树T;
CreateBitTree(&T):创建二叉树T;
DestroyBitTree(&T):如果二叉树存在,则销毁它
InsertLeftChild(p,c):如果二叉树为非空,则将C插入到p所指向的左子树中,使得p结点的左子树变成c的左子树。
InsertRightChild(p,c):如果二叉树为非空,则将C插入到p所指向的右子树中,使得p结点的右子树变成c的右子树。
PreOrderTraverse(T):先序遍历二叉树T。
InOrderTraverse(T):中序遍历二叉树T。
PostOrderTraverse(T):后序遍历二叉树T。
BitTreeDepth:求二叉树的深度。
通常情况下,二叉树采用二叉链表进行表示。二叉链表存储结构的类型定义如下:
typedef struct Node{
DataType data;
struct Node *lchild;
struct Node *rchild;
} *BitTree, BitNode;
二叉树的链表存储结构:
其中数据域存放结点的值,左孩子指针域指向左孩子结点,右孩子指针域指向右孩子结点。
如图,我们写下这棵树的三种遍历方式:
二叉树的先序遍历:
1,访问根节点;
2,先序遍历左子树;
3,先序遍历右子树;
我们看下代码实现:
void PreOrderTraverse(BitTree T)
{
if(T)
{
printf("%2c",T->data;)
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
你应该自己跑一遍程序,其实这就是考验你对递归的理解,很简单的,前提是你理解了递归。
void InOrderTraverse(BitTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%2c",T->data);
InOrderTraverse(T->rchild);
}
}
后序遍历:
void PostOrderTraverse(BitTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%2c",T->data);
}
}
这些是代码实现的原理,也是PreOrderTraverse(T);InOrderTraverse(T):PostOrderTraverse(T):这三个函数的实现原代码。你可以直接调用这三个函数实现遍历,但最好还是要知道实现源代码的原理---递归的理解。
相关资讯