樹的特點(diǎn)：
1. 每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)
2. 每一個(gè)子結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)
3. 沒有前驅(qū)的結(jié)點(diǎn)為根結(jié)點(diǎn)
4. 除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為m個(gè)不相交的子樹
樹相關(guān)的術(shù)語(yǔ):
節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度
葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)
非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)
雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)
樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度
節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推
樹的高度或深度：樹中節(jié)點(diǎn)的最大層次
堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟
節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)
子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫
森林：由m（m>=0）棵互不相交的樹的集合稱為森林
二叉樹 是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)，如上圖。
/**
* <!--
* File : binarytree.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Element char
#define format "%c"
typedef struct Node {
Element data;
struct Node *lchild;
struct Node *rchild;
} *Tree;
int index = 0; //全局索引變量
//二叉樹構(gòu)造器,按先序遍歷順序構(gòu)造二叉樹
//無(wú)左子樹或右子樹用'#'表示
void treeNodeConstructor(Tree &root, Element data[]){
Element e = data[index++];
if(e == '#'){
root = NULL;
}else{
root = (Node *)malloc(sizeof(Node));
root->data = e;
treeNodeConstructor(root->lchild, data); //遞歸構(gòu)建左子樹
treeNodeConstructor(root->rchild, data); //遞歸構(gòu)建右子樹
}
}
//先序遍歷二叉樹
void preorderTraversal(Tree root){
if(root){
printf(format, root->data);
preorderTraversal(root->lchild);
preorderTraversal(root->rchild);
}
}
//中序遍歷二叉樹
void inorderTraversal(Tree root){
if(root){
inorderTraversal(root->lchild);
printf(format, root->data);
inorderTraversal(root->rchild);
}
}
//后序遍歷二叉樹
void postorderTraversal(Tree root){
if(root){
postorderTraversal(root->lchild);
postorderTraversal(root->rchild);
printf(format, root->data);
}
}
/**
* <!--
* File : BinaryTree.cpp
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include "binarytree.h"
int main() {
//上圖所示的二叉樹先序遍歷序列,其中用'#'表示結(jié)點(diǎn)無(wú)左子樹或無(wú)右子樹
Element data[23] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c',
'#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#'};
Tree tree;
treeNodeConstructor(tree, data);
printf("------------------------------------\n");
printf("\nCreate binary tree successfully!\n");
printf("\n------------------------------------");
printf("\n\n先序遍歷二叉樹結(jié)果: ");
preorderTraversal(tree);
printf("\n\n中序遍歷二叉樹結(jié)果: ");
inorderTraversal(tree);
printf("\n\n后序遍歷二叉樹結(jié)果: ");
postorderTraversal(tree);
system("pause");
return 0;
}
posted on 2013-02-03 11:11
fancydeepin 閱讀(1893)
評(píng)論(0) 編輯 收藏