二叉树的基本操作

常用的二叉树的链式存储结构有二叉链表和三叉链表来表示，其数据结构的C语言定义以及示意图如下：

本来介绍基于二叉链表的存储结构上的二叉树的几个常用的操作：

  1.二叉树的创建，

  2.使用递归算法进行二叉树的先序，中序和后序遍历。

  3.使用非递归算法进行二叉树的中序遍历（u需要借助于栈）

  4.借助于数据结构队列实现二叉树的层序遍历。

  5.一些其他的函数，求取叶子节点的数目等等。

---

---

1二叉树的创建

使用对树的先序遍历进行输入，叶子节点的左右孩子（其实为空）使用#来代替：

例如对于下图的二叉树，在创建时，其正确的输入应该是+A##/*B##C##D##

Tree createBinaryTree()
{
ElementType c;
Tree new;
scanf("%c", &c);
if( '#' == c )
return NULL;
else
{
if( !(new = (Tree)malloc(sizeof(struct TreeNode))) )
{
printf("malloc error");
exit(0);
}
new->value = c;
new->left = createBinaryTree();
new->right = createBinaryTree();
}
}</span>

---

2 递归算法对二叉树进行遍历(先序，中序，后序)

  1.先序

void inOrder(Tree tree)
{
if( NULL == tree )
return ;
else
{
inOrder(tree->left);
printf("%c ", tree->value);
inOrder(tree->right);
}
}</span>

  2 中序

void preOrder(Tree tree)
{
if( NULL == tree )
return ;
else
{
printf("%c ",tree->value);
preOrder(tree->left);
preOrder(tree->right);
}
}</span>

  3 后序

void postOrder(Tree tree)
{
if( NULL == tree )
return ;
else
{
postOrder(tree->left);
postOrder(tree->right);
printf("%c ", tree->value);
}
}</span>

---

3.使用非递归算法进行二叉树的中序遍历（需要借助于栈）

   首先给出栈的实现，包括栈的定义，建栈，出栈，入栈。

1栈的定义

struct Stack;
typedef struct Stack* PtrToStack;
struct Stack
{
int capacity;
int topPosition;
Tree* array;
};</span>

2 相关的栈的操作

PtrToStack createStack()
{
PtrToStack ptrToStack;
if(!(ptrToStack = (PtrToStack)malloc(sizeof(struct Stack))))
{
printf("malloc error");
exit(0);
}
ptrToStack->capacity = INIT_STACK_SIZE;
ptrToStack->topPosition = 0;
if( !(ptrToStack->array = (PtrToTreeNode*)malloc(sizeof(PtrToTreeNode) * INIT_STACK_SIZE)) )
{
printf("malloc error");
exit(0);
}
return ptrToStack;
}
int push(PtrToStack ptrToStack, Tree tree)
{
if( ptrToStack->capacity - 1 == ptrToStack->topPosition )
return 0;
ptrToStack->array[ptrToStack->topPosition++] = tree;
return 1;
}
Tree pop(PtrToStack ptrToStack)
{
if( ptrToStack->topPosition == 0 )
return 0;
ptrToStack->topPosition--;
return ptrToStack->array[ptrToStack->topPosition];
}</span>

3非递归的中序遍历

void iteration_inOrder(Tree tree)
{
PtrToTreeNode node = tree;
PtrToStack stack;
stack = createStack();
for(;;)
{
for( ;node;node = node->left)
{
push(stack, node);
}
node = pop(stack);
if(!node)break;
printf("%c ",node->value);
node = node->right;
}
}</span>

---

4.借助于数据结构队列实现二叉树的层序遍历。

1 队列的定义

struct QueueNode;
struct QueueLink;
typedef struct QueueNode* PtrQueueNode;
typedef struct QueueLink* PtrQueueLink;
struct QueueNode
{
Tree treeNode;
PtrQueueNode next;
};
struct QueueLink
{
PtrQueueNode front;
PtrQueueNode rear;
};</span>

2 队列的基本操作

PtrQueueLink createQueue()
{
PtrQueueLink ptrQueueLink;
if( !(ptrQueueLink = (PtrQueueLink)malloc(sizeof(struct QueueLink))) )
{
printf("malloc error");
exit(0);
}
if( !(ptrQueueLink->front = (PtrQueueNode)malloc(sizeof(struct QueueNode))) )
{
printf("malloc error");
exit(0);
}
ptrQueueLink->rear = ptrQueueLink->front;
ptrQueueLink->front->treeNode = NULL;
ptrQueueLink->front->next = NULL;

return ptrQueueLink;
}
void enterQueue(PtrQueueLink queue, Tree tree)
{
PtrQueueNode new;
if( !(new = (PtrQueueNode)malloc(sizeof(struct QueueNode))) )
{
printf("malloc error");
exit(0);
}
new->treeNode = tree;
new->next = queue->rear->next;
queue->rear->next = new;
queue->rear = new;
}
Tree deleteQueue(PtrQueueLink queue)
{
if( queue->front == queue->rear )
return NULL;
PtrQueueNode del = queue->front->next;
queue->front->next = del->next;
if( del == queue->rear )
queue->rear = queue->front;
return del->treeNode;
}</span>

3 层序遍历

<span style="font-family:Courier New;font-size:14px;">void levelTraverse(Tree tree)
{
PtrQueueLink queue;
queue = createQueue();
Tree node = tree;
enterQueue(queue, node);
while( queue->front != queue->rear )
{
node = deleteQueue(queue);
printf("%c ", node->value);
if( node->left )
enterQueue(queue, node->left);
if( node->right )
enterQueue(queue, node->right);
}
}</span>

---

5.一些其他的函数，求取叶子节点的数目等等。

1 求叶子节点数

int leafs(Tree tree)
{
if( !tree )
return 0;
else if( tree->left == NULL && tree->right == NULL )
return 1;
else
return leafs(tree->left) + leafs(tree->right);
}</span>

2 求数的高度

int depth(Tree tree)
{
int left, right;
if( !tree )
return 0;
else
{
left = depth(tree->left);
right = depth(tree->right);
return left > right ? left + 1 : right + 1; 
}
}</span>

源码

---

---

#include<stdio.h>
#include<stdlib.h>

#define INIT_STACK_SIZE 10

struct TreeNode;
typedef struct TreeNode* PtrToTreeNode;
typedef PtrToTreeNode Tree;
typedef char ElementType;
struct TreeNode
{
ElementType value;
Tree left,right;
};

struct Stack;
typedef struct Stack* PtrToStack;
struct Stack
{
int capacity;
int topPosition;
Tree* array;
};

struct QueueNode;
struct QueueLink;
typedef struct QueueNode* PtrQueueNode;
typedef struct QueueLink* PtrQueueLink;
struct QueueNode
{
Tree treeNode;
PtrQueueNode next;
};
struct QueueLink
{
PtrQueueNode front;
PtrQueueNode rear;
};

Tree createBinaryTree();
void inOrder(Tree tree);
void preOrder(Tree tree);
void postOrder(Tree tree);
PtrToStack createStack();
int push(PtrToStack ptrToStack, Tree tree);
Tree pop(PtrToStack ptrToStack);
void iteration_inOrder(Tree tree);
int leafs(Tree tree);
int depth(Tree tree);
PtrQueueLink createQueue();
void enterQueue(PtrQueueLink queue, Tree tree);
Tree deleteQueue(PtrQueueLink queue);
void levelTraverse(Tree tree);
//+A##/*B##C##D##

int main(int argc, char** argv)
{
Tree tree;
printf("please enter binary tree(by preorder):\n");
tree = createBinaryTree();
printf("recursive inorder:");
inOrder(tree);
printf("\nrecursive preorder:");
preOrder(tree);
printf("\nrecursive postorder:");
postOrder(tree);
printf("\niteration inorder:");
iteration_inOrder(tree);
printf("\nthe number of leafs is %d\n", leafs(tree));
printf("the depth of tree is %d\n", depth(tree));
printf("level:");
levelTraverse(tree);
return 0;
}

/*
 * 创建二叉树,要求先序输入二叉树
 * */
Tree createBinaryTree()
{
ElementType c;
Tree new;
scanf("%c", &c);
if( '#' == c )
return NULL;
else
{
if( !(new = (Tree)malloc(sizeof(struct TreeNode))) )
{
printf("malloc error");
exit(0);
}
new->value = c;
new->left = createBinaryTree();
new->right = createBinaryTree();
}
}
/*
 * 线序遍历二叉树（递归）
 * */
void inOrder(Tree tree)
{
if( NULL == tree )
return ;
else
{
inOrder(tree->left);
printf("%c ", tree->value);
inOrder(tree->right);
}
}
void preOrder(Tree tree)
{
if( NULL == tree )
return ;
else
{
printf("%c ",tree->value);
preOrder(tree->left);
preOrder(tree->right);
}
}
void postOrder(Tree tree)
{
if( NULL == tree )
return ;
else
{
postOrder(tree->left);
postOrder(tree->right);
printf("%c ", tree->value);
}
}
void iteration_inOrder(Tree tree)
{
PtrToTreeNode node = tree;
PtrToStack stack;
stack = createStack();
for(;;)
{
for( ;node;node = node->left)
{
push(stack, node);
}
node = pop(stack);
if(!node)break;
printf("%c ",node->value);
node = node->right;
}
}

PtrToStack createStack()
{
PtrToStack ptrToStack;
if(!(ptrToStack = (PtrToStack)malloc(sizeof(struct Stack))))
{
printf("malloc error");
exit(0);
}
ptrToStack->capacity = INIT_STACK_SIZE;
ptrToStack->topPosition = 0;
if( !(ptrToStack->array = (PtrToTreeNode*)malloc(sizeof(PtrToTreeNode) * INIT_STACK_SIZE)) )
{
printf("malloc error");
exit(0);
}
return ptrToStack;
}
int push(PtrToStack ptrToStack, Tree tree)
{
if( ptrToStack->capacity - 1 == ptrToStack->topPosition )
return 0;
ptrToStack->array[ptrToStack->topPosition++] = tree;
return 1;
}
Tree pop(PtrToStack ptrToStack)
{
if( ptrToStack->topPosition == 0 )
return 0;
ptrToStack->topPosition--;
return ptrToStack->array[ptrToStack->topPosition];
}

int leafs(Tree tree)
{
if( !tree )
return 0;
else if( tree->left == NULL && tree->right == NULL )
return 1;
else
return leafs(tree->left) + leafs(tree->right);
}
int depth(Tree tree)
{
int left, right;
if( !tree )
return 0;
else
{
left = depth(tree->left);
right = depth(tree->right);
return left > right ? left + 1 : right + 1; 
}
}

PtrQueueLink createQueue()
{
PtrQueueLink ptrQueueLink;
if( !(ptrQueueLink = (PtrQueueLink)malloc(sizeof(struct QueueLink))) )
{
printf("malloc error");
exit(0);
}
if( !(ptrQueueLink->front = (PtrQueueNode)malloc(sizeof(struct QueueNode))) )
{
printf("malloc error");
exit(0);
}
ptrQueueLink->rear = ptrQueueLink->front;
ptrQueueLink->front->treeNode = NULL;
ptrQueueLink->front->next = NULL;

return ptrQueueLink;
}
void enterQueue(PtrQueueLink queue, Tree tree)
{
PtrQueueNode new;
if( !(new = (PtrQueueNode)malloc(sizeof(struct QueueNode))) )
{
printf("malloc error");
exit(0);
}
new->treeNode = tree;
new->next = queue->rear->next;
queue->rear->next = new;
queue->rear = new;
}
Tree deleteQueue(PtrQueueLink queue)
{
if( queue->front == queue->rear )
return NULL;
PtrQueueNode del = queue->front->next;
queue->front->next = del->next;
if( del == queue->rear )
queue->rear = queue->front;
return del->treeNode;
}
/*
 * 层次遍历
 * */
void levelTraverse(Tree tree)
{
PtrQueueLink queue;
queue = createQueue();
Tree node = tree;
enterQueue(queue, node);
while( queue->front != queue->rear )
{
node = deleteQueue(queue);
printf("%c ", node->value);
if( node->left )
enterQueue(queue, node->left);
if( node->right )
enterQueue(queue, node->right);
}
}
</span>