二叉树的基础与递归遍历

二叉树的基础与递归遍历

所谓二叉树也就是每个节点最多只能有两个儿子的树，对于二叉树的内容，主要有二叉树的建立以及其遍历问题。

二叉树的定义

特殊二叉树

二叉树的性质

二叉树的抽象数据类型定义

二叉树的存储结构 顺序存储结构

对于完全二叉树，我们可以采用顺序存储结构存储完全二叉树。

对于一般的二叉树也可以采用这种结构，但是会造成空间浪费

链表存储

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};

二叉树的遍历

二叉树有三种遍历方式: 先序遍历、中序遍历、后序遍历。这里的先序、中序和后序针对的是根。

先序遍历

中序遍历

后续遍历

对于这三种遍历方式，特点有：

对于遍历的非递归算法的实现代码如下：

#include
#include

typedef struct TreeNode *BinTree;
struct TreeNode{
     char Data;
     BinTree left;
     BinTree right;
};

BinTree CreateBinTree()
{
     BinTree bt;
     bt = (BinTree)malloc(sizeof(struct TreeNode));
     bt->Data = 'a';
     bt->left = Insert('b');
     bt->right = Insert('c');
     bt->left->left = Insert('d');
     bt->left->right = Insert('f');
     bt->right->left = Insert('g');
     bt->right->right = Insert('i');
     bt->left->right->left = Insert('e');
     bt->right->left->right =Insert('h');
     return bt;
}

//递归实现先序遍历
void PreOrder(BinTree BT)
{
     if(BT){
          printf("%c", BT->Data);
          PreOrder(BT->left);
          PreOrder(BT->right);
     }
}
//递归实现中序遍历
void InOrder(BinTree BT)
{
     if(BT){
          InOrder(BT->left);
          printf("%c", BT->Data);
          InOrder(BT->right);
     }
}
//递归实现后序遍历
void PostOrder(BinTree BT)
{
     if(BT){
          PostOrder(BT->left);
          PostOrder(BT->right);
          printf("%c", BT->Data);
     }
}

int main()
{
     BinTree bt = CreateBinTree();
     PreOrder(bt);
     printf("n");
     InOrder(bt);
     printf("n");
     PostOrder(bt);
     printf("n");
     PreOrder2(bt);
}