- 一、二叉树的定义
- 二、二叉树的建立
- 三、二叉树的遍历
- 1.先序遍历
- 2.中序遍历
- 3.后序遍历
- 4.层序遍历
- 四、二叉树的叶、节点、深度
- 1、求叶子数目
- 2、求节点数目
- 3、求二叉树深度
- 五、辅助函数
- 六、完整代码
提示：以下是本篇文章正文内容，下面案例可供参考
一、二叉树的定义图例：
二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。结构体定义二叉树节点：
typedef struct BTNode
{
char element;
struct BTNode* left;
struct BTNode* right;
}BTNode,*BTNodePtr;
二、二叉树的建立
BTNodePtr constructBTNode(char paraChar)
{
BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(struct BTNode));
resultPtr->element = paraChar;
resultPtr->left = NULL;
resultPtr->right = NULL;
return resultPtr;
}
三、二叉树的遍历
1.先序遍历
先序遍历的过程是首先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。
代码如下（示例）：
void preorder(BTNodePtr tempPtr)//先序遍历
{
if (tempPtr == NULL)
{
return;
}
printf("%c", tempPtr->element);
preorder(tempPtr->left);
preorder(tempPtr->right);
}
2.中序遍历
中序遍历的过程是首先中序遍历左子树，然后访问根结点，最后中序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。
代码如下（示例）：
void inorder(BTNodePtr tempPtr)//中序遍历
{
if (tempPtr == NULL)
{
return;
}
inorder(tempPtr->left);
printf("%c", tempPtr->element);
inorder(tempPtr->right);
}
3.后序遍历
后序遍历的过程是首先后序遍历左子树，然后后序遍历根的右子树，最后访问根结点。
void postorder(BTNodePtr tempPtr)//后序遍历
{
if (tempPtr == NULL)
{
return;
}
postorder(tempPtr->left);
postorder(tempPtr->right);
printf("%c", tempPtr->element);
}
4.层序遍历
在进行层次遍历时，对一层结点访问完后再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层地进行，先遇到的结点先访问，先上到下，先左到右。实现层次遍历用队列比较方便，因为是先进先出（FIFO）。首先把队首元素入队，然后再输出队首元素，并且把队首元素的左结点和右结点入队（如果有的话），以此类推，输出的序列就是层次遍历。
void levelwise(BTNodePtr paraTreePtr)
{
char tempString[100];
int i = 0;
QueuePtr tempQueuePtr = initQueue();
BTNodePtr tempNodePtr;
enqueue(tempQueuePtr, paraTreePtr);
while(!isQueueEmpty(tempQueuePtr))
{
tempNodePtr = dequeue(tempQueuePtr);
tempString[i] = tempNodePtr->element;
i ++;
if (tempNodePtr->left != NULL)
{
enqueue(tempQueuePtr, tempNodePtr->left);
}
if (tempNodePtr->right != NULL)
{
enqueue(tempQueuePtr, tempNodePtr->right);
}
}
tempString[i] = ' ';
printf("Levelwise: %srn", tempString);
}
四、二叉树的叶、节点、深度
1、求叶子数目
int LeafCount(BTNodePtr tempPtr)
{
if(tempPtr == NULL)
{
return 0;
}
else if(tempPtr->left == NULL && tempPtr->right == NULL)
{
return 1;
}
else
{
return LeafCount(tempPtr->left)+LeafCount(tempPtr->right);
}
}
2、求节点数目
int Nodecount(BTNodePtr tempPtr)
{
if(tempPtr == NULL)
{
return 0;
}
else
{
return Nodecount(tempPtr->left)+Nodecount(tempPtr->right)+1;
}
}
3、求二叉树深度
int Depth(BTNodePtr tempPtr)
{
int m,n;
if(tempPtr == NULL)
{
return 0;
}
else
{
m=Depth(tempPtr->left);
n=Depth(tempPtr->right);
if(m>n)
{
return m+1;
}
else
{
return n+1;
}
}
}
五、辅助函数
typedef struct BTNodePtrQueue
{
BTNodePtr* nodePtr;
int front;
int rear;
}BTNodePtrQueue,*QueuePtr;//队列结构体
QueuePtr initQueue()
{
QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
resultQueuePtr->front = 0;
resultQueuePtr->rear = 1;
resultQueuePtr->nodePtr = (BTNodePtr*)malloc(sizeof(struct BTNode)*QUEUE_SIZE);
return resultQueuePtr;
}//初始化队列
BTNodePtr stringToBTree(char* paraString)
{
int i;
char ch;
QueuePtr tempQueuePtr = initQueue();
BTNodePtr resultHeader;
BTNodePtr tempParent, tempLeftChild, tempRightChild;
i = 0;
ch = paraString[i];
resultHeader = constructBTNode(ch);
enqueue(tempQueuePtr, resultHeader);
while(!isQueueEmpty(tempQueuePtr))
{
tempParent = dequeue(tempQueuePtr);
i ++;
ch = paraString[i];
if (ch == '#')
{
tempParent->left = NULL;
}
else
{
tempLeftChild = constructBTNode(ch);
enqueue(tempQueuePtr, tempLeftChild);
tempParent->left = tempLeftChild;
}
i ++;
ch = paraString[i];
if (ch == '#')
{
tempParent->right = NULL;
}
else
{
tempRightChild = constructBTNode(ch);
enqueue(tempQueuePtr, tempRightChild);
tempParent->right = tempRightChild;
}
}
return resultHeader;
}//二叉树赋值
void enqueue(QueuePtr paraQueueptr,BTNodePtr paraBTNodePtr)
{
printf("front=%d ,rear=%d.rn",paraQueueptr->front,paraQueueptr->rear);
if((paraQueueptr->rear + 1) % QUEUE_SIZE == paraQueueptr->front % QUEUE_SIZE)
{
printf("Error, trying to enqueue %c. queue full.rn", paraBTNodePtr->element);
return;
}
paraQueueptr->nodePtr[paraQueueptr->rear] = paraBTNodePtr;
paraQueueptr->rear = (paraQueueptr->rear + 1) % QUEUE_SIZE;
printf("enqueue %c ends.rn", paraBTNodePtr->element);
}//进队
BTNodePtr dequeue(QueuePtr paraQueuePtr)
{
if (isQueueEmpty(paraQueuePtr))
{
printf("Error, empty queuern");
return NULL;
}
paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;
printf("dequeue %c ends.rn", paraQueuePtr->nodePtr[paraQueuePtr->front]->element);
return paraQueuePtr->nodePtr[paraQueuePtr->front];
}//出队
bool isQueueEmpty(QueuePtr paraQueueptr)
{
if((paraQueueptr->front + 1) % QUEUE_SIZE == paraQueueptr->rear)
{
return true;
}
return false;
}//队列判空
六、完整代码
#include#include #include #define QUEUE_SIZE 5 typedef struct BTNode { char element; struct BTNode* left; struct BTNode* right; }BTNode,*BTNodePtr; typedef struct BTNodePtrQueue { BTNodePtr* nodePtr; int front; int rear; }BTNodePtrQueue,*QueuePtr; QueuePtr initQueue() { QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue)); resultQueuePtr->front = 0; resultQueuePtr->rear = 1; resultQueuePtr->nodePtr = (BTNodePtr*)malloc(sizeof(struct BTNode)*QUEUE_SIZE); return resultQueuePtr; } bool isQueueEmpty(QueuePtr paraQueueptr) { if((paraQueueptr->front + 1) % QUEUE_SIZE == paraQueueptr->rear) { return true; } return false; } void enqueue(QueuePtr paraQueueptr,BTNodePtr paraBTNodePtr) { printf("front=%d ,rear=%d.rn",paraQueueptr->front,paraQueueptr->rear); if((paraQueueptr->rear + 1) % QUEUE_SIZE == paraQueueptr->front % QUEUE_SIZE) { printf("Error, trying to enqueue %c. queue full.rn", paraBTNodePtr->element); return; } paraQueueptr->nodePtr[paraQueueptr->rear] = paraBTNodePtr; paraQueueptr->rear = (paraQueueptr->rear + 1) % QUEUE_SIZE; printf("enqueue %c ends.rn", paraBTNodePtr->element); } BTNodePtr dequeue(QueuePtr paraQueuePtr) { if (isQueueEmpty(paraQueuePtr)) { printf("Error, empty queuern"); return NULL; } paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE; printf("dequeue %c ends.rn", paraQueuePtr->nodePtr[paraQueuePtr->front]->element); return paraQueuePtr->nodePtr[paraQueuePtr->front]; } BTNodePtr constructBTNode(char paraChar) { BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(struct BTNode)); resultPtr->element = paraChar; resultPtr->left = NULL; resultPtr->right = NULL; return resultPtr; } BTNodePtr stringToBTree(char* paraString) { int i; char ch; QueuePtr tempQueuePtr = initQueue(); BTNodePtr resultHeader; BTNodePtr tempParent, tempLeftChild, tempRightChild; i = 0; ch = paraString[i]; resultHeader = constructBTNode(ch); enqueue(tempQueuePtr, resultHeader); while(!isQueueEmpty(tempQueuePtr)) { tempParent = dequeue(tempQueuePtr); i ++; ch = paraString[i]; if (ch == '#') { tempParent->left = NULL; } else { tempLeftChild = constructBTNode(ch); enqueue(tempQueuePtr, tempLeftChild); tempParent->left = tempLeftChild; } i ++; ch = paraString[i]; if (ch == '#') { tempParent->right = NULL; } else { tempRightChild = constructBTNode(ch); enqueue(tempQueuePtr, tempRightChild); tempParent->right = tempRightChild; } } return resultHeader; } void levelwise(BTNodePtr paraTreePtr) { char tempString[100]; int i = 0; QueuePtr tempQueuePtr = initQueue(); BTNodePtr tempNodePtr; enqueue(tempQueuePtr, paraTreePtr); while(!isQueueEmpty(tempQueuePtr)) { tempNodePtr = dequeue(tempQueuePtr); tempString[i] = tempNodePtr->element; i ++; if (tempNodePtr->left != NULL) { enqueue(tempQueuePtr, tempNodePtr->left); } if (tempNodePtr->right != NULL) { enqueue(tempQueuePtr, tempNodePtr->right); } } tempString[i] = ' '; printf("Levelwise: %srn", tempString); } void preorder(BTNodePtr tempPtr)//先序遍历 { if (tempPtr == NULL) { return; } printf("%c", tempPtr->element); preorder(tempPtr->left); preorder(tempPtr->right); } void inorder(BTNodePtr tempPtr)//中序遍历 { if (tempPtr == NULL) { return; } inorder(tempPtr->left); printf("%c", tempPtr->element); inorder(tempPtr->right); } void postorder(BTNodePtr tempPtr)//后序遍历 { if (tempPtr == NULL) { return; } postorder(tempPtr->left); postorder(tempPtr->right); printf("%c", tempPtr->element); } int LeafCount(BTNodePtr tempPtr) { if(tempPtr == NULL) { return 0; } else if(tempPtr->left == NULL && tempPtr->right == NULL) { return 1; } else { return LeafCount(tempPtr->left)+LeafCount(tempPtr->right); } } int Depth(BTNodePtr tempPtr) { int m,n; if(tempPtr == NULL) { return 0; } else { m=Depth(tempPtr->left); n=Depth(tempPtr->right); if(m>n) { return m+1; } else { return n+1; } } } int Nodecount(BTNodePtr tempPtr) { if(tempPtr == NULL) { return 0; } else { return Nodecount(tempPtr->left)+Nodecount(tempPtr->right)+1; } } int main() { BTNodePtr tempHeader; tempHeader = constructBTNode('c'); printf("There is only one node. Preorder visit: "); preorder(tempHeader); printf("rnn"); char* tempString = "acde#bf######"; tempHeader = stringToBTree(tempString); printf("先序: "); preorder(tempHeader);//先序：中左右 printf("rnn"); printf("中序: "); inorder(tempHeader);//中序：左中右 printf("rnn"); printf("后序: "); postorder(tempHeader);//后序：左右中 printf("rnn"); printf("Lvelwise: "); levelwise(tempHeader);//层序 printf("rnn"); int k; k = LeafCount(tempHeader); printf("树的叶子有：%d",k); printf("rnn"); int l; l = Depth(tempHeader); printf("树的深度：%d",l); printf("rnn"); int n; n = Nodecount(tempHeader); printf("树的节点数：%d",n); return 0; }
运行结果：
There is only one node. Preorder visit: c front=0 ,rear=1. enqueue a ends. dequeue a ends. front=1 ,rear=2. enqueue c ends. front=1 ,rear=3. enqueue d ends. dequeue c ends. front=2 ,rear=4. enqueue e ends. dequeue d ends. front=3 ,rear=0. enqueue b ends. front=3 ,rear=1. enqueue f ends. dequeue e ends. dequeue b ends. dequeue f ends. 先序: acedbf 中序: ecabdf 后序: ecbfda Lvelwise: front=0 ,rear=1. enqueue a ends. dequeue a ends. front=1 ,rear=2. enqueue c ends. front=1 ,rear=3. enqueue d ends. dequeue c ends. front=2 ,rear=4. enqueue e ends. dequeue d ends. front=3 ,rear=0. enqueue b ends. front=3 ,rear=1. enqueue f ends. dequeue e ends. dequeue b ends. dequeue f ends. Levelwise: acdebf 树的叶子有：3 树的深度：3 树的节点数：6
