数据结构之二叉树

二叉树的一些概念这里简单说一下

二叉树的遍历有三种，前序，中序和后序，前序即按照DLR（结点->左子树->右子树）的顺序遍历，中序则是LDR，后序则是LRD。完全二叉树，除了最底层，各层节点数均为最大值，同时最下层的节点集中在左侧，且中间不能有间隔。满树即为全满的树。树的存储结构：顺序存储和链式存储。顺序存储即从上到下，从左到右依次存放，完全二叉树可用数组，一层一层放，非完全二叉树先用无效的数据将其补充为完全二叉树，然后再用数组，但是会产生冗余。有序二叉树，对于树中任意节点，若其左子树非空，则左子树中所有的节点的值都小于或等于该节点的值；若其右子树非空，则右子树中所有节点的值都大于或等于该节点的值。，即左小右大的规则。这样可得中序的遍历，可用于排序。也可用于搜索，收缩搜索的范围。时间复杂度：O(logN)。

其他的基本概念这里就不赘述了，下面是编程实现二叉树的一些基本操作。从遍历的逻辑可以看出，二叉树的遍历和递归一模一样，因此，我们的二叉树的操作基本用递归。

树的结构

typedef struct BTree { char data; //数据 struct BTree *lChild; //左孩子 struct BTree *rChild; //右孩子 } BinTree;

创建一棵树

BinTree* CreateTree(BinTree *p) { char ch; scanf("%c", &ch); if(ch == '#') //代表子节点为空 return NULL; p=(BinTree *)malloc(sizeof(BinTree)); p->data=ch; p->lChild=CreateTree(p->lChild); p->rChild=CreateTree(p->rChild); return p; }

销毁树

void BTreeSetNull(BTree *tree) { if(tree==NULL) { return; } BTreeSetNull(tree->lChild); BTreeSetNull(tree->rChild); free(tree); tree = NULL; }

前序遍历

void PreOrder(BinTree *T) { if(T){ printf("%c", T->data); PreOrder(T->lChild); PreOrder(T->rChild ); } }

中序遍历

void ZhongXu(BinTree *T) { if(T) { ZhongXu(T->lChild); printf("%c", T->data); ZhongXu(T->rChild); } }

后序遍历

void HouXu(BinTree *T) { if(T) { HouXu(T->lChild); HouXu(T->rChild ); printf("%c", T->data); } }

树的深度

int Depth(BinTree *T) { int dep=0, dep1, depr; if(!T) dep=0; else{ dep1=Depth(T->lChild); depr=Depth(T->rChild ); dep=1+(dep1>depr?dep1:depr); } return dep; }

复制树

BinTree* copybtree(BinTree* root) { BinTree* newnode; if(root == NULL) { return NULL; } else { newnode = (BinTree*)malloc(sizeof(BinTree)); newnode->data = root->data; newnode->lChild = copybtree(root->lChild); newnode->rChild = copybtree(root->rChild); return newnode; } }

求树的叶子数

int Sumleaf(BinTree *T) { int sum=0; int m = 0; int n = 0; if(T) { if((!T->lChild) && (!T->rChild)) sum++; m = Sumleaf(T->lChild); sum += m; n = Sumleaf(T->rChild ); sum += n; } return sum; }

测试用例这里就不写了，要注意的是我们的输入必须按照树的前序，因为第一个节点一定为树的根节点。

这里举一个例子：

二叉树的操作就到这里。